Модульная кластеризация Ньюмана для графов

Question

Мне интересно запустить алгоритм кластеризации Ньюмана modularity на большом графике.Если бы вы могли указать мне на библиотеку (или R-пакет и т. Д.), Которая ее реализует, я был бы очень признателен.

Answer 1

Используйте пакет igraph для R: http://igraph.sourceforge.net/doc/R/fastgreedy.community.html. В нем реализован быстрый алгоритм поиска сообщества с использованием метода максимизации модульности newman-girvan.

Ваш код будет выглядеть следующим образом:

library(igraph)
# read graph from csv file
G<-read.graph("edgelist.txt", format="ncol")
fgreedy<-fastgreedy.community(G,merges=TRUE, modularity=TRUE)
memberships <-community.to.membership(G, fgreedy$merges, steps=which.max(fgreedy$modularity)-1)
print(paste('Number of detected communities=',length(memberships$csize)))
# Community sizes:
print(memberships$csize)
# modularity:
max(fgreedy$modularity)

Answer 2

Я не совсем уверен, работает ли с этим алгоритмом инструмент визуализации данных с открытым исходным кодом, Gephi .Как я знаю, он работает с алгоритмом из бумаги: Быстрое развертывание сообществ в больших сетях

Это также методы на основе модульности.

Answer 3

В превосходном пакете networkx есть метод , который возвращает граф маленького мира Ньюмана-Ватта-Строгатца.