使用NetworkX计算社区模块度时访问图权重遇KeyError求助

问题背景 #

我正在用NetworkX编写算法计算社区模块度，执行G[complst[i]][complst[j]]['weight']时总是抛出KeyError，但已经确认complst[i]和complst[j]的节点值是正确的，试了单独存储变量等调试方法都没用，代码如下：

import networkx as nx
import copy
#load the graph made in previous task
G = nx.read_gexf("graph.gexf")
#set a global max modualrity value
maxmod = 0
#deep copy of the original graph, since when removing edges, the graph will change
ori = copy.deepcopy(G)
#create an array for saving the edges to remove
arr = []
#see if all edges are broken, if not, keep looping, otherwise stop
while(G.number_of_edges()!=0):
    #find the edge_betweeness for each edge
    betweeness = nx.edge_betweenness_centrality(G,weight='weight',normalized=False)
    print('------------------******************--------------------')
    #sort the result in descending order and save all edges with the maximum betweenness to 'arr'
    sortbet = {k: v for k, v in sorted(betweeness.items(), key=lambda item: item[1],reverse=True)}
    #convert the dict to list for processing
    betlst = list(sortbet)
    for i in range(len(betlst)):
        if betlst[i] == betlst[0]:
            arr.append(betlst[i])
    #remove all edges with maximum betweeness from the graph
    G.remove_edges_from(arr)
    #find the leftover component, and convert the result to list for further modualrity processing
    lst = list(nx.connected_components(G))
    #!!!!!!!!testing and debugging the value, now the value is printed correctly
    print(G['pk_sullivan']['ChrisWarcraft']['weight'])
    #create a variable cnt to represent modularity in this graph
    cnt = 0
    #iterate the lst, which is each component(each component is saved as python set)
    for n in range(len(lst)):
        #convert each component from set to list for processing
        complst = list(lst[n])
        #if this component is a singleton, the modualrity for this component 0, so add 0 the current cnt
        if len(complst)==1:
            cnt += 0
        else:
            # calulate the modularity for this component by using combinations of edges
            for i in range(0,len(complst)):
                if i+1 <=len(complst)-1:
                    for j in range(i+1,len(complst)):
                        #!!!!!!!!! there is a bunch of my testing and find the value are printed all fine until "print(G[a][b]['weight'])"
                        print(i)
                        print(j)
                        print(complst)
                        a = complst[i]
                        print(type(a))
                        b = complst[j]
                        print(type(b))
                        print(G[a][b]['weight'])
                        #calculate the modualrity by using equation M = 1/2m*(weight(a,b)-degree(a)*degree(b)/2m)
                        cnt += 1/(2*ori.number_of_edges())*(G[a][b]['weight']-ori.degree(a)*ori.degree(b)/(2*ori.number_of_edges()))
    #find the maximum modualrity and save this split of graph, end!
    if cnt>=maxmod:
        maxmod = cnt
        newgraph = copy.deepcopy(G)
    print('maxmod is',maxmod)

问题原因 #

这个KeyError的核心逻辑很清晰：
你在循环中不断用G.remove_edges_from(arr)删除图G的边，但计算模块度时，遍历的是当前G的连通分量里的节点对——这些节点对在原始图ori中可能存在边，但在当前的G中已经被你之前的删除操作移除了，所以访问G[a][b]['weight']时，这条边已经不存在，自然抛出KeyError。

你测试的print(G['pk_sullivan']['ChrisWarcraft']['weight'])能正常打印，只是刚好这条边还没被移除而已，其他节点对的边可能已经被删掉了。

解决方案 #

模块度的计算逻辑是基于原始图的边权重（衡量社区内部实际边与随机期望边的差异），所以应该用原始图ori的数据，而不是被修改后的G。同时要先判断原始图里是否存在这条边，避免原始图里就没有边的情况。

修改后的核心代码片段：

else:
    # 改用原始图ori计算模块度
    for i in range(0, len(complst)):
        for j in range(i+1, len(complst)):
            a = complst[i]
            b = complst[j]
            # 先检查原始图中是否存在这条边
            if ori.has_edge(a, b):
                weight = ori[a][b]['weight']
                # 模块度计算公式
                cnt += 1/(2*ori.number_of_edges())*(weight - ori.degree(a)*ori.degree(b)/(2*ori.number_of_edges()))
            else:
                # 原始图中无此边，权重为0，贡献为0，直接跳过
                continue

额外优化建议 #

• 你的arr列表没有在每次循环后清空，会导致重复尝试删除已经删掉的边，建议在每次while循环开始时重置arr = []。
• 遍历节点对可以用itertools.combinations简化代码，更高效也更简洁：

import itertools

# 替换原来的双层for循环
for a, b in itertools.combinations(complst, 2):
    if ori.has_edge(a, b):
        weight = ori[a][b]['weight']
        cnt += 1/(2*ori.number_of_edges())*(weight - ori.degree(a)*ori.degree(b)/(2*ori.number_of_edges()))

内容的提问来源于stack exchange，提问作者bot99zjc