1294
правки
Классификация больших графов: различия между версиями
Материал из WEGA
Классификация больших графов (посмотреть исходный код)
Версия от 16:49, 23 октября 2019
, 23 октября 2019нет описания правки
KVN (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 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 миллиардов вершин, не поддаются обработке на системах с общей памятью. Конкретное число, определяющее этот порог, несомненно, в какой-то момент изменится, но уже есть и всегда будут существовать достаточно большие структуры, обработка которых будет невозможна на машинах с общей памятью и будет требовать специальных распределенных методов. Это касается, например, всего веб-графа. Нужно иметь ввиду, что в то время как для задач глобальной обработки таких графов может потребоваться компьютер с распределенной памятью, часто можно из них извлечь гораздо меньшие части, которые являются лишь громадными и могут быть легко обработаны на компьютерах с общей памятью. А задачи, которые возможно решать на сверх гигантских графах, - это только весьма простые задачи, такие, как, например, треугольники, | ''Гигантские графы'' (свыше 10 миллиардов вершин). Графы, имеющие более 10 миллиардов вершин, не поддаются обработке на системах с общей памятью. Конкретное число, определяющее этот порог, несомненно, в какой-то момент изменится, но уже есть и всегда будут существовать достаточно большие структуры, обработка которых будет невозможна на машинах с общей памятью и будет требовать специальных распределенных методов. Это касается, например, всего веб-графа. Нужно иметь ввиду, что в то время как для задач глобальной обработки таких графов может потребоваться компьютер с распределенной памятью, часто можно из них извлечь гораздо меньшие части, которые являются лишь громадными и могут быть легко обработаны на компьютерах с общей памятью. А задачи, которые возможно решать на сверх гигантских графах, - это только весьма простые задачи, такие, как, например, [[треугольник|треугольники]], [[компонента связности|компоненты связности]], PageRank (ранг страницы) и label propagation (распространение меток). | ||
==Литература== | ==Литература== | ||
