Ни один алгоритм действительно не должен «вписываться в память» - вы всегда можете перемещать объекты по мере необходимости. Но вы не хотите, чтобы вычисление занимало неоправданно много времени - а глобальное разбиение графа в общем случае - это NP-полная проблема, которая «неоправданно длинна» для большинства задач, которые даже не помещаются в память.
К счастью, вы хотите выполнить поиск в ширину, что означает, что вам нужен формат, в котором ширина в первую очередь является простым вычислением. Я не знаю ни одного алгоритма, который бы так делал, но вы можете создать свой собственный макет в ширину, если хотите выделить немного дополнительного дискового пространства.
Если края не смещены в сторону локальных взаимодействий, то распутывание графика будет затруднено. Если они смещены в сторону локальных взаимодействий, то я предлагаю алгоритм, подобный следующему:
- Выберите случайный набор вершин в качестве отправных точек для всего набора данных.
- Для каждой вершины собрать все соседние вершины (выполняется один проход по набору данных).
- Для каждого набора соседних вершин собрать набор соседей и ранжировать их в соответствии с тем, сколько ребер соединяется с ними. Если на странице нет места для их хранения, оставьте наиболее связанные вершины. Если у вас есть место для их сохранения, вы можете отказаться от наименее полезных (например, если доля ребер, находящихся в пределах страницы / фракции вершин, для которых требуется коэффициент хранения, падает «слишком низко» - где «слишком низко») будет зависеть от того, насколько шире ваши поиски, а также от того, сможете ли вы выполнить обрезку и т. д., а затем не включайте их в окрестности.
- Повторяйте процесс сбора и ранжирования соседей, пока ваше соседство не будет заполнено (например, заполнит какой-то размер страницы, который вам подходит). Затем проверьте повторы среди случайно выбранных запусков. Если у вас есть небольшое количество вершин, появляющихся в обеих, удалите их из одной или другой, в зависимости от того, что ломает меньше ребер. Если у вас есть большое количество вершин, появляющихся в обеих, сохраняйте соседство с наилучшим соотношением (вершины в окрестности / разбитое ребро) и отбрасывайте остальные.
Теперь у вас есть некоторые локальные окрестности, которые являются приблизительно локально оптимальными в этом поиске шириной, как правило, попадают внутрь. Если ваш поиск в ширину довольно эффективно удаляет непродуктивные ветви, то, вероятно, этого достаточно. Если нет, то вы, вероятно, хотите, чтобы соседние районы были объединены.
Если вам не нужны соседние окрестности для слишком большого скопления, вы откладываете вершины, которые вы сгруппировали в окрестности, и повторяете процесс для остальных данных, пока все вершины не будут учтены. Вы изменяете каждый идентификатор вершины на (вершина, окрестность), и все готово: когда вы следуете за ребрами, вы точно знаете, какую страницу захватить, и большинство из них будут близки, учитывая конструкцию.
Если вам нужны соседние районы, вам нужно будет отслеживать ваши растущие окрестности. Вы повторяете предыдущий процесс (выбираете случайным образом, увеличиваете окрестности), но теперь ранжируете соседей по тому, сколько ребер они удовлетворяют в окрестности и , какая доля их ребер, покидающих окрестность, находится в существующей группе. Вам могут понадобиться весовые коэффициенты, но что-то вроде
score = (# edges within) - (# neighborhoods outside) - (# neighborhoodless edges outside)
вероятно, добьется цели.
Теперь, это не глобально или даже локально оптимально, но это или что-то очень похожее должно дать хорошо локально связанную структуру и позволить вам создать покрывающий набор окрестностей, которые имеют относительно высокая взаимосвязанность.
Опять же, это зависит от того, обрезает ли ваш поиск в ширину ветки или нет. Если это произойдет, недорогая вещь, которую нужно сделать, это максимизировать локальную взаимосвязанность. Если это не то, что нужно сделать, это минимизировать внешнее подключение - и в этом случае я бы предложил просто собрать наборы в ширину до некоторого размера и сохранить их (с дублированием по краям наборов - вы Вы не сильно ограничены местом на жестком диске, не так ли?).