Сборники трудов ИСП РАН


Параллельное вычисление модулярности для направленных взвешенных графов с пересекающимися сообществами

М. Дробышевский (ИСП РАН, Москва, Россия)
А. Коршунов (ИСП РАН, Москва, Россия)
Д. Турдаков (ИСП РАН, Москва, Россия, МГУ, Москва, Россия, ВШЭ, Москва, Россия)

Аннотация

В статье представлены новые алгоритмы расчета модулярности для направленных взвешенных графов с пересекающимися сообществами. Рассматриваются несколько подходов для вычисления модулярности и их расширения. Учитывая вычислительную сложность известных подходов, предлагаются два параллельных расширения, масштабируемых на графы с более 104 вершин.

Ключевые слова

модулярность, поиск сообществ, пэйдж-ранк, линк-ранк, функция принадлежности, коэффициент принадлежности

Издание

Труды Института системного программирования РАН, том 28, вып. 6, 2016, стр. 153-170.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2016-28(6)-11

Полный текст статьи в формате pdf (на английском) Вернуться к содержанию тома