[PYTHON] Netzwerkanalyse mit NetworkX --- Community-Erkennungsvolumen

Ich wollte so etwas wie eine "kleine Gruppe, in der alles verbunden und verbunden ist" aus dem gesamten Netzwerk extrahieren, also habe ich es mit der Python-Bibliothek "Network X" gemacht.

https://networkx.github.io/

Was ist die Community hier?

In menschlicher Hinsicht handelt es sich um eine "Gruppe von Menschen, die miteinander befreundet sind", und es handelt sich um eine Menge, die eine vollständige Grafik (alle miteinander verbunden) als komplementäre Menge des gesamten Netzwerks darstellt. Es scheint in der Graphentheorie "Clique" genannt zu werden.

Erstellen Sie eine Diagrammstruktur

Experimentieren Sie mit einem kleinen Satz von 6 Knoten.

from networkx import *
import matplotlib.pyplot as plt

#Originale Daten
data = [["A","B"],["A","C"],["C","B"],["D","C"],["D","E"],["C","E"],["E","F"]]

#Erstellen eines Knotens
G = nx.Graph()
for p in list(set([r[0] for r in data] + [r[1] for r in data])):
    G.add_node(p)

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

#Zeichnung
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()

Visualisierte Diagrammstruktur

Extrahieren Sie die Clique aus der vorgefertigten Diagrammstruktur

Nachdem wir nun eine Diagrammstruktur haben, erkennen wir die Community.

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

Standardausgabe

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

kam heraus! Sie können die Community richtig extrahieren!

Wenn es sich um kleine Daten handelt, fühlt es sich wie Hoon an, aber wenn Sie es mit großen Datenmengen tun, gibt es verschiedene Entdeckungen.

Performance

Es ist sehr schnell, da es in wenigen Sekunden etwa 100.000 Daten verarbeiten kann. Die Cliquenerkennung scheint jedoch ein Prozess zu sein (wahrscheinlich ein Problem mit NP), dessen Verarbeitungszeit mit zunehmender Anzahl von Knoten explodiert. Wenn es sich also um größere Daten handelt, erreicht NetWork X möglicherweise ein Plateau, ist aber immer noch ein Rätsel.

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

Vielleicht benutzen ernsthafte Leute Spark oder so.