Блог

Предположим, я создаю следующий ориентированный граф с использованием 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},
  ...
]
  

Я внес прямую модификацию 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)
  

Затем используйте функцию verbose_pagerank так же, как вы делали с 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)
  

Вывод:

 {'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}