[PYTHON] Analyse de réseau avec NetworkX --- Volume de détection de la communauté

Je voulais extraire quelque chose comme un "petit groupe où tout est connecté et connecté" de tout le réseau, alors je l'ai fait avec la bibliothèque python "Network X".

https://networkx.github.io/

Quelle est la communauté ici?

En termes humains, c'est un «groupe de personnes qui sont amis les uns avec les autres», et c'est un ensemble qui est un graphe complet (tous connectés) comme un ensemble complémentaire de l'ensemble du réseau. Il semble s'appeler "Clique" en théorie des graphes.

Créer une structure graphique

Expérimentez avec un petit ensemble de 6 nœuds.

from networkx import *
import matplotlib.pyplot as plt

#données brutes
data = [["A","B"],["A","C"],["C","B"],["D","C"],["D","E"],["C","E"],["E","F"]]

#Construire un nœud
G = nx.Graph()
for p in list(set([r[0] for r in data] + [r[1] for r in data])):
    G.add_node(p)

#Construction de bord
for d in data:
    G.add_edge(d[0],d[1])

#dessin
pos = nx.spring_layout(G)
nx.draw_networkx_nodes(G, pos, node_size=1200,node_color="white")
nx.draw_networkx_edges(G, pos)
nx.draw_networkx_labels(G, pos)
plt.show()

Structure graphique visualisée

Extraire la clique de la structure graphique prédéfinie

Maintenant que nous avons une structure graphique, détectons la communauté.

cliques = nx.find_cliques(G)
#Sortie standard
print  [ c for c in cliques]

Sortie standard

[['C', 'A', 'B'], ['C', 'E', 'D'], ['F', 'E']]

sortit de! Vous pouvez extraire la communauté correctement!

S'il s'agit de petites données, cela ressemble à Hoon, mais si vous le faites avec de grandes données, il y a diverses découvertes.

performance

Il est très rapide car il peut traiter environ 100 000 données en quelques secondes. Cependant, la détection de clique semble être un processus (probablement un problème avec NP) dont le temps de traitement explose à mesure que le nombre de nœuds augmente, donc s'il s'agit de données plus volumineuses, NetWork X peut atteindre un plateau, mais cela reste un mystère.

https://en.wikipedia.org/wiki/Clique_problem

Peut-être que des personnes sérieuses utilisent Spark ou quelque chose comme ça.