5

我正在尝试实现用于句子提取的 textrank 算法，如此处所述。为此，需要用加权边来补充 pagerank 算法并让它在无向图上运行。Networkx pagerank 算法实现允许我轻松集成加权边，据说可以将有向图转换为无向图：请参见此处。但是，当我测试时，它似乎仍然使用有向图。我在这里想念什么？帮助很大。

例子：

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}

4

2 回答 2

9

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

PageRank 算法是为有向图设计的，但该算法不检查输入图是否有向，而是通过将有向图中的每个有向边转换为两条边来在无向图上执行。

这说明，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}
于 2012-02-12T09:35:13.487 回答
0

可以在这里找到 Python 中 TextRank 算法的一个很好的实现。如果你想使用这个脚本，你必须事先运行 nltk.download() 来安装必要的数据文件，如此处所述。

于 2012-10-02T10:18:58.170 回答