1023
правки
Классификация больших графов: различия между версиями
Материал из WEGA
Классификация больших графов (посмотреть исходный код)
Версия от 15:37, 23 октября 2019
, 23 октября 2019нет описания правки
KVN (обсуждение | вклад) (Новая страница: «'''Классификация больших графов''' (''Classification of large graphs'') основана на их размере <math> n</math>,…») |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 3: | Строка 3: | ||
''Небольшие графы'' (до 10 тыс. вершин). При таком размере графа стандартные алгоритмы хорошо работают. Например, для вычисления всех пар кратчайших путей требуется <math> O(n^3)</math> времени и <math> O(n^2)</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) наиболее важные свойства графов этого (и большего) размера сильно отличаются от свойств малых графов | ''Большие маленькие графы'' (от 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 вершинами занимает несколько минут на современном ноутбуке. | ||
