在networkx中收缩节点列表

Question

我有一个包含节点的字典：

supernodes = list(nx.connected_components(G1))

print(supernodes) 的结果是：

[{1, 2, 3, 5}, {8, 6}, {7, 9, 10, 12, 13}, {4}, {11}, {14}, {15}]

我该如何将每个列表合并到一个节点中？我找到了这个函数nx.contracted_nodes(G, (1, 3))，但是我应该如何将{1,2,3,5}、{8,6}等输入，并创建7个合并后的节点呢？

- Lee Yaan

---

你想让输出是什么？不清楚你想如何表示已缩减的节点。 - Imran

@Imran 我想要的输出是一个有7个节点的图。其中一个节点为{1, 2, 3, 5}，一个节点为{8, 6}，一个节点为{7, 9, 10, 12, 13}，一个节点为{4}等。 - Lee Yaan

Answer 1

你可以尝试这个：

import networkx as nx
# Preamble, define G1 

# contract nodes
for supernode in nx.connected_components(G1):
    nodes = sorted(list(supernode))
    for node in nodes[1:]:
        G1 = nx.contracted_nodes(G1, nodes[0], node)

G1中的每个节点x对应于以x为较小元素的超级节点。如果要删除自环，请改为写成nx.contracted_nodes(G1, nodes[0], node, self_loops=False)。

- rodgdor

---

代码将在没有 supernodes = list(nx.connected_components(G1)) 的情况下正常运行。只需使用 for supernode in nx.connected_components(G1): 即可。 - Joel

Answer 2

我尝试了 这个 答案，但是对于大图来说速度太慢了。我发现将 Networkx 图转换为 DataFrame，并在 DataFrame 上组合节点比现有的 Networkx 函数更快。

import time
import networkx as nx

#create node replacement dictionary
def createRepDict(G1):

    node2supernode={}
    for supernode in nx.connected_components(G1):
        nodes = sorted(list(supernode))
        for node in nodes:
             node2supernode[node]=nodes[0]
    
    #fill the missing nodes with itself (if you have different task)
    for node in G1.nodes:
        if node not in node2supernode:
             node2supernode[node]=node
    return node2supernode

start_time=time.time()
for _ in range(10):
    G1=G.copy()
    df=nx.to_pandas_edgelist(G1)

    #create node replacement dictionary
    node2supernode=createRepDict(G1)
    
    df['source']=df.apply(lambda row: node2supernode[row['source']],axis=1)
    df['target']=df.apply(lambda row: node2supernode[row['target']],axis=1)

    # you can drop the self loop created after combining the nodes
    self_loop=df[df['source']==df['target']].index
    df=df.drop(self_loop)

    # edge_attr field can change based on your edge datas
    G1=nx.from_pandas_edgelist(df,'source','target', 
edge_attr='edgeData',create_using=nx.MultiDiGraph())
print(time.time()-start_time)

这段代码在大约5千个节点和5千条边的图上进行10次随机运行只需要总共4秒，而使用现有方法进行10次随机运行则需要总共1455秒。

- Enes Altınışık