Как найти кластеры с сетью на основе плотности и веса ребер в python - networkx package

Question

Я построил сеть, использующую пакет python - networkx, каждый край имеет вес, который указывает, насколько близки два узла, с точки зрения корреляция.

Было бы идеально, если бы был встроенный алгоритм, который бы возвращал кластерный граф, назначая каждому узлу его идентификатор кластера (от 1 до k).

Было бы еще лучше, если бы он мог кластер на основе веса ребер, но не критично ...

Любая идея, как это можно сделать?

Answer 1

Возможно, вы захотите изучить пакет python-louvain. С его помощью вы можете обнаружить сообщества на графике, используя функцию best_partition. Из описания функции:

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.

В моем примере я вычисляю сообщество для karate_club_graph. (Обратите внимание, что я использую best_partition с weight ключевым словом, хотя мой график не взвешенные дуг - я просто показываю, как бы вы использовали функцию в вашем случае.)

import networkx as nx 
import community 

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

Выход:

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

Выход - это словарь (ключ = узел, значение = раздел). Перегородки идут от 0 до k-1. Если вам нужно, чтобы они переместились от 1 до k, вы можете просто увеличить значения словаря до +1.

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