1178
правок
Методы обработки больших графов: различия между версиями
Материал из WikiGrapp
Методы обработки больших графов (посмотреть исходный код)
Версия от 11:03, 29 сентября 2019
, 29 сентября 2019нет описания правки
KVN (обсуждение | вклад) (Новая страница: «Существует три канонических типа методов обработки больших графов (''Large graph mining methods''),…») |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 6: | Строка 6: | ||
Использование графовых диффузий при обработке графов обычно является формализацией следующей идеи: значение течет от исходной вершины по дугам графа к смежным ей вершинам. Механизм поведения диффузии на дуге графа определяет конкретный тип диффузии. Хорошо известными примерами являются: диффузия PageRank, диффузия Каца, диффузия теплового ядра, диффузия усеченных случайных блужданий. Эти методы можно использовать для ответов на такие вопросы, как «Как выглядит область данного графа вокруг данного конкретного объекта?». Их легко также масштабировать на большие графы, потому что здесь не нужно исследовать весь граф. Например, случайные блуждания с перезапуском являются примером этой идеи. Следует подумать о том, чтобы запускать эти диффузии в окрестностях не у всех, а только у <math> O(\log n)</math> или <math> O(\sqrt n)</math> вершин. | Использование графовых диффузий при обработке графов обычно является формализацией следующей идеи: значение течет от исходной вершины по дугам графа к смежным ей вершинам. Механизм поведения диффузии на дуге графа определяет конкретный тип диффузии. Хорошо известными примерами являются: диффузия PageRank, диффузия Каца, диффузия теплового ядра, диффузия усеченных случайных блужданий. Эти методы можно использовать для ответов на такие вопросы, как «Как выглядит область данного графа вокруг данного конкретного объекта?». Их легко также масштабировать на большие графы, потому что здесь не нужно исследовать весь граф. Например, случайные блуждания с перезапуском являются примером этой идеи. Следует подумать о том, чтобы запускать эти диффузии в окрестностях не у всех, а только у <math> O(\log n)</math> или <math> O(\sqrt n)</math> вершин. | ||
'''Обработка на основе обобщенных произведений матрица-вектор''' является одним из самых гибких и масштабируемых способов обработки больших графов. Как следует из названия, эти методы возникают из обобщенного понятия матрично-векторного произведения на обобщениях матрицы смежности графа. В более общем смысле матрично-векторный произведение можно рассматривать как частный случай следующего вычислительного примитива: обновлять данные вершины на основе некоторой заданной функции от данных смежных ей вершин. Стандартное матрично-векторное произведение использует суммирование в качестве данной функции. Итерационные последовательности этих операций, с различными функциями, вычисляют связанные компоненты, кратчайшие пути из одного источника, распространение меток, эффективные диаметры и гистограммы расстояний. Такие операции, как минимальные остовные деревья, паросочетания максимального веса и методы передачи сообщений, также вписываются в эту же схему. Все эти методы и алгоритмы | '''Обработка на основе обобщенных произведений матрица-вектор''' является одним из самых гибких и масштабируемых способов обработки больших графов. Как следует из названия, эти методы возникают из обобщенного понятия матрично-векторного произведения на обобщениях матрицы смежности графа. В более общем смысле матрично-векторный произведение можно рассматривать как частный случай следующего вычислительного примитива: обновлять данные вершины на основе некоторой заданной функции от данных смежных ей вершин. Стандартное матрично-векторное произведение использует суммирование в качестве данной функции. Итерационные последовательности этих операций, с различными функциями, вычисляют связанные компоненты, кратчайшие пути из одного источника, распространение меток, эффективные диаметры и гистограммы расстояний. Такие операции, как минимальные остовные деревья, паросочетания максимального веса и методы передачи сообщений, также вписываются в эту же схему. Все эти методы и алгоритмы применяются в пакетных системах, а не в онлайн-системах. | ||
=Литература== | =Литература== | ||
