python - 文本等级 : complementing pagerank for sentence extraction using networkx

Question

我正在尝试按照描述的方式实现用于句子提取的 textrank 算法 here .对于那些需要用加权边补充 pagerank 算法并让它在无向图上运行的人。Networkx pagerank 算法实现允许我轻松地集成加权边，据说可以将有向图转换为无向图:参见 here .但是，当我测试时它似乎仍然使用有向图。我在这里错过了什么？非常感谢帮助。

示例:

import networkx as nx
D=nx.DiGraph()
D.add_weighted_edges_from([('A','B',0.5),('A','C',1)])
print nx.pagerank(D)

---

输出:{'A': 0.25974025929223499, 'C': 0.40692640737443164, 'B': 0.33333333333333331}

Answer 1

我认为您误解了 networkx 文档中的注释。不过，我必须承认它的措辞可能更好。

The PageRank algorithm was designed for directed graphs but this algorithm does not check if the input graph is directed and will execute on undirected graphs by converting each oriented edge in the directed graph to two edges.

这表明，PageRank 算法是为有向图设计的，但它可以用于无向图。为此，它将无向网络转换为有向网络，方法是用两条有向边(进出边)替换每条边。

因此，如果你给它一个有向网络，它会根据有向结构计算PageRank。所以要么从无向网络开始:

import networkx as nx

# Undirected Network
D = nx.Graph()
D.add_weighted_edges_from([('A', 'B', 0.5),('A', 'C', 1)])

# Default max number of iterations failed to converge for me
print nx.pagerank(D, max_iter=200)

# Outputs:
{'A': 0.48648648872844047, 'C': 0.32567567418103965, 'B': 0.18783783709051982}

或者如果您已经有一个有向网络，请将其转换为无向网络:

import networkx as nx

# Directed Network
D = nx.DiGraph()
D.add_weighted_edges_from([('A', 'B', 0.5), ('A', 'C', 1)])

# Convert to undirected
G = D.to_undirected()

# Default max number of iterations failed to converge for me
print nx.pagerank(G, max_iter=200)

# Outputs:
{'A': 0.48648648872844047, 'C': 0.32567567418103965, 'B': 0.18783783709051982}