Аноним

Классификация больших графов: различия между версиями

Материал из WEGA
нет описания правки
Нет описания правки
Нет описания правки
 
Строка 5: Строка 5:
''Большие маленькие графы'' (от 10 тыс. до 1 миллиона вершин). Это графы, для которых алгоритмы с временной сложностью <math> O(n^2)</math> возможны, но алгоритмы с емкостной сложностью <math> O(n^2)</math> становятся недопустимыми или невозможными. Эти графы весьма близки к небольшим графам, потому что есть много задач, таких как вычисление диаметра, которые могут быть решены для этих графах за небольшое дополнительное время. Однако есть два различия: (1) наиболее важные свойства графов этого (и большего) размера сильно отличаются от свойств малых графов, и (2) даже если квадратичные по времени вычисления возможны, они могут усложняться и даже стать недопустимым, если будут использоваться в режиме анализа исследовательских данных или как часть большого взаимно проверяемого вычисления.
''Большие маленькие графы'' (от 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 вершинами занимает несколько минут на современном ноутбуке.
''Маленькие большие графы'' (от 1 миллиона до 100 миллионов вершин). Во многих отношениях переход между небольшими и большими графами происходит на графах, содержащих около миллиона вершин. Например, для графов с пятью миллионами вершин применение алгоритмов, которые требуют <math> O(n^2)</math> времени, обычно невозможно без специализированных вычислительных ресурсов. Тем не менее, с учетом соответствующих соображений, касающихся вычислительных проблем, графы с вершинами от 1 до 100 миллионов достаточно легко обрабатывать с помощью довольно сложных методов, учитывающих современные вычислительные ресурсы. Основной причиной этого является крайняя разреженность реальных сетей. Графы реального мира этого диапазона размеров обычно имеют среднюю степень вершин от 5 до 100. Таким образом, даже большой такой реальный граф будет иметь не более нескольких миллиардов ребер. Он потребует нескольких гигабайт памяти и может быть легко обработан на современном ноутбуке или настольном компьютере с 32 ГБ памяти. Например, вычисление вектора PageRank (ранг страницы) на графе с 60M вершинами занимает несколько минут на современном ноутбуке.


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


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


==Литература==
==Литература==