networkx pagerank的详细输出

Question

假设我使用networkx创建以下有向图，并在其上执行pagerank算法

adj_lists={
'A': 'B C'.split(' '),
'B': 'C',
'C': 'A',
'D': 'C'
}
G=nx.DiGraph()
for k in adj_lists.keys():
G.add_node(k)
for k in adj_lists.keys():
G.add_edges_from([(k, t) for t in adj_lists[k]])
nx.pagerank(G, alpha=1)

是否可以得到一个详细的输出，告诉我每个节点的值的发展，甚至生成一个显示其进展的列表？我在想这样的事情：

[
{'A:0.25, 'B':0.25, 'C':0.25, 'D':0.25},
{'A:0.25, 'B':0.125, 'C':0.625, 'D':0},
{'A:0.625, 'B':0.3125, 'C':0.4375, 'D':0},
...
]

Answer 1

我直接修改了networkx.pagerank算法，将每次迭代的值存储在列表中。

import networkx as nx
from networkx.utils import not_implemented_for
def verbose_pagerank(
G,
alpha=0.85,
personalization=None,
max_iter=100,
tol=1.0e-6,
nstart=None,
weight="weight",
dangling=None,
):
if len(G) == 0:
return {}
if not G.is_directed():
D = G.to_directed()
else:
D = G
# Create a copy in (right) stochastic form
W = nx.stochastic_graph(D, weight=weight)
N = W.number_of_nodes()
# Choose fixed starting vector if not given
if nstart is None:
x = dict.fromkeys(W, 1.0 / N)
else:
# Normalized nstart vector
s = float(sum(nstart.values()))
x = {k: v / s for k, v in nstart.items()}
if personalization is None:
# Assign uniform personalization vector if not given
p = dict.fromkeys(W, 1.0 / N)
else:
s = float(sum(personalization.values()))
p = {k: v / s for k, v in personalization.items()}
if dangling is None:
# Use personalization vector if dangling vector not specified
dangling_weights = p
else:
s = float(sum(dangling.values()))
dangling_weights = {k: v / s for k, v in dangling.items()}
dangling_nodes = [n for n in W if W.out_degree(n, weight=weight) == 0.0]
# power iteration: make up to max_iter iterations
iterprogress = []
for i in range(max_iter):
xlast = x
iterprogress.append(x)
x = dict.fromkeys(xlast.keys(), 0)
danglesum = alpha * sum(xlast[n] for n in dangling_nodes)
for n in x:
# this matrix multiply looks odd because it is
# doing a left multiply x^T=xlast^T*W
for nbr in W[n]:
x[nbr] += alpha * xlast[n] * W[n][nbr][weight]
x[n] += danglesum * dangling_weights.get(n, 0) + (1.0 - alpha) * p.get(n, 0)
# check convergence, l1 norm
err = sum([abs(x[n] - xlast[n]) for n in x])
if err < N * tol:
iterprogress.append(x)
return iterprogress
raise nx.PowerIterationFailedConvergence(max_iter)

然后使用与nx.pagerank相同的函数verbose_pagerank

adj_lists={
'A': 'B C'.split(' '),
'B': 'C',
'C': 'A',
'D': 'C'
}
G=nx.DiGraph()
for k in adj_lists.keys():
G.add_node(k)
for k in adj_lists.keys():
G.add_edges_from([(k, t) for t in adj_lists[k]])
pr = verbose_pagerank(G, alpha=1)
for i in pr:
print(i)

输出：

{'A': 0.25, 'B': 0.25, 'C': 0.25, 'D': 0.25}
{'A': 0.25, 'B': 0.125, 'C': 0.625, 'D': 0.0}
{'A': 0.625, 'B': 0.125, 'C': 0.25, 'D': 0.0}
...
{'A': 0.40000057220458984, 'B': 0.20000028610229492, 'C': 0.39999914169311523, 'D': 0.0}