comment trouver des clusters avec un réseau basé sur la densité et le poids des bords dans python - paquet networkx

Question

J'ai construit un réseau en utilisant le paquet python - networkx, chaque arête a un poids qui indique à quel point les deux nœuds sont proches, en termes de corrélation.

Il serait idéal s'il y a un algorithme intégré qui retournerait un graphe groupé, assignant chaque nœud à son ID de grappe (1 à k).

Il serait encore mieux si elle pouvait se regrouper en fonction du poids des bords, mais pas critique ...

Toute idée de comment cela pourrait se faire?

Answer 1

Vous voudrez peut-être regarder dans le paquet python-louvain. Avec lui, vous pouvez détecter les communautés dans un graphique en utilisant la fonction best_partition. De la description de la fonction:

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.

Dans mon exemple, je calcule les communautés pour la karate_club_graph. (Notez que j'utiliser best_partition avec le mot-clé weight même si mon graphique ne pas les bords pondérés - Je suis juste montrer comment vous utilisez la fonction dans votre cas.)

import networkx as nx 
import community 

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

Sortie:

{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} 

La sortie est un dictionnaire (clé = noeud, valeur = partition). Les partitions vont de 0 à k-1. Si vous avez besoin d'aller de 1 à k, vous pouvez simplement augmenter les valeurs du dictionnaire à +1.

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