Обнаружение сообщества в Networkx

Я изучаю сообщества обнаружения в сетях.

Я использую igraph и Python

Для оптимального числа сообществ в терминах меры модульности:

from igraph import *
karate = Nexus.get("karate")
cl = karate.community_fastgreedy()
cl.as_clustering().membership

Для обеспечения желаемого количества сообществ:

from igraph import *
karate = Nexus.get("karate")
cl = karate.community_fastgreedy()
k=2
cl.as_clustering(k).membership

Однако мне нравится делать это с помощью networkx. Я знаю, что оптимальное количество сообществ с точки зрения модульности:

import community # --> http://perso.crans.org/aynaud/communities/
import fastcommunity as fg # --> https://networkx.lanl.gov/trac/ticket/245
import networkx as nx

g = nx.karate_club_graph()
partition = community.best_partition(g)
print "Louvain Modularity: ", community.modularity(partition, g)
print "Louvain Partition: ", partition

cl = fg.communityStructureNewman(g)
print "Fastgreed Modularity: ", cl[0]
print "Fastgreed Partition: ", cl[1]

Но я не могу получить нужное количество сообществ. Есть ли какой-нибудь алгоритм для этого, используя Networkx?

Ответы

Ответ 1

Я также новичок в networkx и igraph, я использовал Gephi, инструмент/программное обеспечение для визуализации данных. И он имеет тот же алгоритм обнаружения сообщества, что и тот, который используется в networkx, который вы сейчас используете. В частности, в http://perso.crans.org/aynaud/communities/

Он использует метод louvain, описанный в разделе Быстрое развертывание сообществ в крупных сетях, Винсент Д. Блондель, Жан-Луп Гийом, Рено Ламбиотт, Рено Лефевр, Журнал статистической механики: теория и эксперимент 2008 (10), P10008 (12pp)

Вы не можете получить желаемое количество сообществ, как я знаю, есть два пути, которые стоит попробовать:

  • Используйте Gephi. Вы можете использовать gephi и там параметр resolution, который изменит размер сообщества, которое вы получите.
  • Использовать NetworkX. На этот раз мы больше не можем использовать best_partition(G). Но используйте partition_at_level(dendrogram, level), я думаю, это могло бы помочь.

Подробнее читайте исходный код здесь.

Ответ 2

Возможно, я вас не понимаю, но если вы хотите, чтобы количество сообществ было реализовано с помощью реализации алгоритма best_partition NetworkX, просто обратите внимание, что best_partition (G) предоставляет словарь с узлами в качестве ключей и их номер раздела как значение.

Вы можете подсчитать количество уникальных значений в словаре, как это (вероятно, не оптимально):

dict = {'a':1,'b':1,'c':2,'d':1,'e':3,'f':4,'g':5}
count=list(set([i for i in dict.values()]))
print count
print len(count)

В результате

[1, 2, 3, 4, 5]
5