Wie man Cluster mit einem Netzwerk basierend auf Dichte und Gewicht der Kanten in Python findet - networkx package

Question

Ich baute ein Netzwerk mit dem Python - Paket - networkx, jede Kante hat eine Gewichtung, die angibt, wie nahe die beiden Knoten sind Korrelation.

Es wäre ideal, wenn es einen eingebauten Algorithmus gäbe, der ein gruppiertes Diagramm zurückgibt und jedem Knoten seine Cluster-ID (1 bis k) zuweist.

Es wäre noch besser, wenn es bezogen auf das Gewicht der Kanten Cluster könnte, aber nicht kritisch ...

Jede Idee, wie dies geschehen könnte?

Answer 1

Vielleicht möchten Sie in das Paket python-louvain suchen. Damit können Sie Gemeinschaften in einem Graphen mit der Funktion best_partition erkennen. Aus der Funktionsbeschreibung:

Compute the partition of the graph nodes which maximises the modularity (or try..) using the Louvain heuristices

This is the partition of highest modularity, i.e. the highest partition of the dendrogram generated by the Louvain algorithm.

In meinem Beispiel berechnen ich die Gemeinden für die karate_club_graph. (Beachten Sie, dass ich best_partition mit dem weight Schlüsselwort verwenden, obwohl meine Graph nicht gewichtete Kanten hat - Ich zeige, wie würden Sie die Funktion in Ihrem Fall verwenden.)

import networkx as nx 
import community 

G = nx.karate_club_graph() 
p = community.best_partition(G, weight='weight') 
print(p) 

Ausgang:

{0: 0, 1: 0, 2: 0, 3: 0, 4: 1, 5: 1, 6: 1, 7: 0, 8: 2, 9: 0, 10: 1, 11: 0, 12: 0, 13: 0, 14: 2, 15: 2, 16: 1, 17: 0, 18: 2, 19: 0, 20: 2, 21: 0, 22: 2, 23: 3, 24: 3, 25: 3, 26: 2, 27: 3, 28: 3, 29: 2, 30: 2, 31: 3, 32: 2, 33: 2} 

Die Ausgabe ist ein Wörterbuch (Schlüssel = Knoten, Wert = Partition). Die Partitionen gehen von 0 bis k-1. Wenn Sie sie von 1 bis k benötigen, können Sie die Wörterbuchwerte einfach auf +1 setzen.

for k, v in p.items(): 
    p[k] = v + 1