有没有办法在NetworkX的MultiGraph上运行pagerank算法？

Question

我正在处理一个在相同节点之间有多条边的图（边的值不同）。为了对这个图进行建模，我需要使用MultiGraph而不是普通graph。不幸的是，不可能在上面运行PageRank算法。

有什么解决办法吗？

NetworkXNotImplemented: not implemented for multigraph type

Answer 1

您可以创建一个没有平行边的图，然后运行pagerank。以下是一个将平行边的边权重相加以生成简单图的示例：

import networkx as nx
G = nx.MultiGraph()
G.add_edge(1,2,weight=7)
G.add_edge(1,2,weight=10)
G.add_edge(2,3,weight=9)
# make new graph with sum of weights on each edge
H = nx.Graph()
for u,v,d in G.edges(data=True):
    w = d['weight']
    if H.has_edge(u,v):
        H[u][v]['weight'] += w
    else:
        H.add_edge(u,v,weight=w)
print H.edges(data=True)
#[(1, 2, {'weight': 17}), (2, 3, {'weight': 9})]
print nx.pagerank(H)
#{1: 0.32037465332634, 2: 0.4864858243244209, 3: 0.1931395223492388}

Answer 2

您仍然可以通过组合边来组成有向图同时添加它们的权重。

# combining edges using defaultdict
# input-- combined list of all edges
# ouput-- list of edges with summed weights for duplicate edges
from collections import defaultdict  
def combine_edges(combined_edge_list):    
    ddict = defaultdict(list)
    for edge in combined_edge_list:
        n1,n2,w = edge
        ddict[(n1,n2)].append(w)
    
    for k in ddict.keys():
        ddict[k] = sum(ddict[k])
    
    edges = list(zip( ddict.keys(), ddict.values() ) )    
    return [(n1,n2,w) for (n1,n2),w in edges]