Eindeutige ID für Netzwerkcluster

Question

Ich habe ein Netzwerk von Knoten (parends/childs, jede mit einer ID) und möchte eine eindeutige ID für jeden Cluster von verbundenen Knoten generieren. Ich benutze Python, Pandas und networkx.

Zum Beispiel habe ich

id a b c 
1 101 201 301 
2 101 202 302 
3 102 202 302 
4 103 203 303 
5 103 204 304 

wo zum Beispiel in Spalte a, Zeilen 1 und 2 verbunden sind.

würde Ich mag

id a b c id_cluster 
1 101 201 301  1 
2 101 202 302  1 
3 102 202 302  1 
4 103 203 303  2 
5 103 204 304  2 

Answer 1

So erhalten, wenn ich die Dinge richtig zu verstehen bin, dies zu zwei Typen von Knoten entspricht:

1. Knoten in Ihrem Datenrahmen, die haben und id
2. Kombination von Säule und Wert in dem Datenrahmen

und dieser DataFrame sind die Kanten des Graphen.

So (a, 101) Verbindung zu 1 & 2

und (b, 202) Verbindung zu 2 & 3

Also, alle 1, 2, 3, (a, 101), (a, 102), (b, 201), (b, 202), (c, 301) und (c, 302) sind in Verbindung gebracht.

Ich bin nicht vertraut mit networkx, aber es scheint, als gäbe es eine Funktion namens connected_components, die Sie verbundenen Teilgraphen gibt. So

import pandas as pd 
import networkx as nx 
from StringIO import StringIO 


df = pd.read_table(StringIO(""" 
id a b c 
1 101 201 301 
2 101 202 302 
3 102 202 302 
4 103 203 303 
5 103 204 304"""), delim_whitespace=True) 

df = df.set_index('id') 

G = nx.Graph() 
for (id_, column), other_node in df.stack().iteritems(): 
    G.add_edge(id_, (column, other_node)) 

cluster_map = pd.Series(
    {id_: id_cluster + 1 
    for id_cluster, ids in enumerate(nx.connected_components(G)) 
    for id_ in ids 
    if not isinstance(id_, tuple)}, 
    name='id_cluster') 

df = df.join(cluster_map) 
print(df) 

ergibt

 a b c id_cluster 
id       
1 101 201 301   1 
2 101 202 302   1 
3 102 202 302   1 
4 103 203 303   2 
5 103 204 304   2