Хранение очень больших графов на дисках / алгоритмы разделения потокового графа?

Ни один алгоритм действительно не должен «помещаться в память» - вы всегда можете загружать и выгружать вещи по мере необходимости. Но вы не хотите, чтобы вычисления занимали неоправданно долго - а глобальное разбиение графа в общем случае является NP-полной проблемой, которая является «неоправданно долгой» для большинства задач, которые даже не помещаются в память.

К счастью, вы хотите выполнять поиск в ширину, а это значит, что вам нужен формат, в котором вычисление в ширину является простым. Я не знаю ни одного алгоритма, который бы это делал, но вы можете создать свой собственный макет в ширину, если хотите выделить немного дополнительного дискового пространства.

Если ребра не смещены в сторону локальных взаимодействий, распутать граф будет сложно. Если они предвзято относятся к локальным взаимодействиям, я предлагаю следующий алгоритм:

• Выберите случайный набор вершин в качестве отправных точек из всего набора данных.
• Для каждой вершины собрать все соседние вершины (требуется один проход по набору данных).
• Для каждого набора соседних вершин соберите набор соседей-соседей и ранжируйте их по количеству ребер, соединенных с ними. Если у вас нет места на странице для их всех, оставьте самые связанные вершины. Если у вас есть место для их сохранения, вы можете выбросить наименее полезные из них (например, если доля ребер, находящихся в пределах страницы / доля вершин, нуждающихся в хранении, падает «слишком низко» - где «слишком низко» будет зависеть от того, насколько широта вашего поиска действительно нужна, можете ли вы выполнить обрезку и т. д. - тогда не включайте тех, кто находится поблизости.
• Повторяйте процесс сбора и ранжирования соседей, пока ваш район не заполнится (например, не заполнит какой-либо размер страницы, который вам подходит). Затем проверьте наличие повторов среди случайно выбранных запусков. Если у вас небольшое количество вершин появляется в обоих, удалите их с одной или другой, в зависимости от того, что сломает меньше ребер. Если у вас есть большое количество вершин, появляющихся в обеих, оставьте соседство с наилучшим соотношением (вершины в окрестности / сломанное ребро) и выбросьте другую.

Теперь у вас есть несколько локальных районов, которые являются приблизительно оптимальными с точки зрения локального поиска, поэтому поиск в ширину имеет тенденцию попадать внутрь. Если ваш поиск в ширину довольно эффективно отсекает непродуктивные ветви, то этого, вероятно, достаточно. В противном случае вы, вероятно, захотите объединить соседние районы в кластер.

Если вам не нужно слишком много кластеризовать соседние окрестности, вы откладываете вершины, сгруппированные в окрестности, и повторяете процесс с оставшимися данными, пока не будут учтены все вершины. Вы меняете идентификатор каждой вершины на (вершина, окрестность), и все готово: следуя за ребрами, вы точно знаете, какую страницу захватить, и большинство из них будут рядом с данной конструкцией.

Если вам действительно нужны соседние районы, вам нужно следить за своими растущими районами. Вы повторяете предыдущий процесс (выбираете случайным образом, увеличиваете окрестности), но теперь ранжируете соседей по количеству ребер, которым они удовлетворяют в пределах окрестности , и, какая часть их ребер, выходящих из соседства, находится в существующей группе . Вам могут понадобиться весовые коэффициенты, но что-то вроде

score = (# edges within) - (# neighborhoods outside) - (# neighborhoodless edges outside)

вероятно, добился бы цели.

Теперь это не глобально или даже локально оптимально, но это или что-то очень похожее на него должно дать хорошо локально связанную структуру и позволить вам создать покрывающий набор окрестностей, которые имеют относительно высокую взаимосвязь. .

Опять же, это зависит от того, обрезает ли ваш поиск в ширину ветки или нет. Если это так, то недорогой вариант - это максимизировать локальную взаимосвязь. Если это не так, то нужно свести к минимуму внешнее подключение - и в этом случае я бы предложил просто собирать наборы в ширину до определенного размера и сохранять их (с дублированием по краям наборов - вы Вы ведь не сильно ограничены пространством на жестком диске?).

Вы можете посмотреть HDF5. Несмотря на то, что H означает «Иерархический», он может хранить графики, проверьте документацию по ключевому слову «Группы», и он предназначен для очень больших наборов данных. Если я правильно понимаю, «файлы» HDF5 могут быть распределены по нескольким «файлам». Теперь HDF5 - это только структура данных плюс набор библиотек для низко- и высокоуровневых манипуляций со структурой данных. Я не имею ни малейшего понятия о потоковых алгоритмах разбиения графов, но я придерживаюсь мнения, что если вы получите правильную структуру данных, алгоритмы станет проще реализовать.

Что вы уже знаете о мегаграфе? Разделяется ли он естественным образом на плотные подграфы, которые сами по себе слабо связны? Будет ли топологическая сортировка графа лучшей основой для хранения на диске, чем существующая пространственная сортировка?

Не имея четких ответов на такие вопросы, возможно, вам просто нужно укусить пулю и прочитать график несколько раз, чтобы построить разделы, и в этом случае вам просто нужен самый быстрый ввод-вывод, которым вы можете управлять, а сложная компоновка разделов на узлах хороша но не так важно. Если вы можете разделить граф на подграфы, которые сами по себе имеют единственные ребра по отношению к другим подграфам, вы, возможно, сможете сделать проблему более решаемой.

Вам нужен макет, подходящий для BFS, но BFS обычно применяется к деревьям. Есть ли у вашего графа уникальный корень, из которого можно запускать все BFS? В противном случае раскладка для BFS из одной вершины будет неоптимальной для BFS из другой вершины.