Просмотр кода страницы Классификация больших графов

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

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

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

''Маленькие большие графы'' (от 1 миллиона до 100 миллионов вершин). Во многих отношениях переход между небольшими и большими графами происходит на графах, содержащих около миллиона вершин. Например, для графов с пятью миллионами вершин применение алгоритмов, которые требуют <math> 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. 


[[Категория: Большие графы]]