Классификация больших графов

Классификация больших графов (Classification of large graphs) основана на их размере [math]\displaystyle{ n }[/math], где [math]\displaystyle{ n }[/math] - количество вершин в графе. Следует отметить, что реальные графы обычно чрезвычайно разрежены, например, в среднем имеют приблизительно от десяти до нескольких сотен ребер на вершину, и таким образом, число вершин и количество ребер у них равно [math]\displaystyle{ O(n) }[/math].

Небольшие графы (до 10 тыс. вершин). При таком размере графа стандартные алгоритмы хорошо работают. Например, для вычисления всех пар кратчайших путей требуется [math]\displaystyle{ O(n^3) }[/math] времени и [math]\displaystyle{ O(n^2) }[/math] памяти, что не является проблемой для любого современного компьютера.

Большие маленькие графы (от 10 тыс. до 1 миллиона вершин). Это графы, для которых алгоритмы с временной сложностью [math]\displaystyle{ O(n^2) }[/math] возможны, но алгоритмы с емкостной сложностью [math]\displaystyle{ O(n^2) }[/math] становятся недопустимыми или невозможными. Эти графы весьма близки к небольшим графам, потому что есть много задач, таких как вычисление диаметра, которые могут быть решены для этих графах за небольшое дополнительное время. Однако есть два различия: (1) наиболее важные свойства графов этого (и большего) размера сильно отличаются от свойств малых графов, и (2) даже если квадратичные по времени вычисления возможны, они могут усложняться и даже стать недопустимым, если будут использоваться в режиме анализа исследовательских данных или как часть большого взаимно проверяемого вычисления.

Маленькие большие графы (от 1 миллиона до 100 миллионов вершин). Во многих отношениях переход между небольшими и большими графами происходит на графах, содержащих около миллиона вершин. Например, для графов с пятью миллионами вершин применение алгоритмов, которые требуют [math]\displaystyle{ O(n^2) }[/math] времени, обычно невозможно без специализированных вычислительных ресурсов. Тем не менее, с учетом соответствующих соображений, касающихся вычислительных проблем, графы с вершинами от 1 до 100 миллионов достаточно легко обрабатывать с помощью довольно сложных методов, учитывающих современные вычислительные ресурсы. Основной причиной этого является крайняя разреженность реальных сетей. Графы реального мира этого диапазона размеров обычно имеют среднюю степень вершин от 5 до 100. Таким образом, даже большой такой реальный граф будет иметь не более нескольких миллиардов ребер. Он потребует нескольких гигабайт памяти и может быть легко обработан на современном ноутбуке или настольном компьютере с 32 ГБ памяти. Например, вычисление вектора PageRank (ранг страницы) на графе с 60M вершинами занимает несколько минут на современном ноутбуке.

Громадные графы (от 100 миллионов до 10 миллиардов вершин). Для графов с несколькими сотнями миллионов или даже несколькими миллиардами вершин возрастает сложность работы даже простых графовых алгоритмов. Однако даже самые крупные общедоступные сети из этого диапазона размеров будут вмещаться в основную память больших систем с общей памятью с объемом оперативной памяти около 1 ТБ. Это была мотивация проекта Ligra. Кроме того, расчеты эффективного диаметра в сетях Facebook с числом ребер 70B были выполнены на одной машине с общей памятью.

Гигантские графы (свыше 10 миллиардов вершин). Графы, имеющие более 10 миллиардов вершин, не поддаются обработке на системах с общей памятью. Конкретное число, определяющее этот порог, несомненно, в какой-то момент изменится, но уже есть и всегда будут существовать достаточно большие структуры, обработка которых будет невозможна на машинах с общей памятью и будет требовать специальных распределенных методов. Это касается, например, всего веб-графа. Нужно иметь ввиду, что в то время как для задач глобальной обработки таких графов может потребоваться компьютер с распределенной памятью, часто можно из них извлечь гораздо меньшие части, которые являются лишь громадными и могут быть легко обработаны на компьютерах с общей памятью. А задачи, которые возможно решать на сверх гигантских графах, - это только весьма простые задачи, такие, как, например, треугольники, компоненты связности, PageRank (ранг страницы) и label propagation (распространение меток).

Литература

• Buhlmann P., Drineas P., Kane M., van der Laan M. (eds.) Handbook of Big Data. — CRC Press, 2016.