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)

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}