Suppose i create the following directed Graph using networkx and perform the pagerank algorithm on it
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)
Is ist possible to get a verbose output telling me the devolopment of each node's value or even to generate a list which shows their progress? I am thinking about something like this:
[
{'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},
...
]
I've made a direct modification of networkx.pagerank
algorithm to store the values of each iteration in a list.
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)
Then use the function verbose_pagerank
the same as you did with nx.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)
Output:
{'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}