"""图结构的PageRank分析。"""
from warnings import warn
import networkx as nx
__all__ = ["pagerank", "google_matrix"]
def _pagerank_python(
G,
alpha=0.85,
personalization=None,
max_iter=100,
tol=1.0e-6,
nstart=None,
weight="weight",
dangling=None,
):
if len(G) == 0:
return {}
D = G.to_directed()
# 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 = 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 = 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 = 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
for _ in range(max_iter):
xlast = 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, wt in W.edges(n, data=weight):
x[nbr] += alpha * xlast[n] * wt
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:
return x
raise nx.PowerIterationFailedConvergence(max_iter)
[docs]
@nx._dispatchable(edge_attrs="weight")
def google_matrix(
G, alpha=0.85, personalization=None, nodelist=None, weight="weight", dangling=None
):
"""返回图的Google矩阵。
Parameters
----------
G : 图
一个NetworkX图。无向图将被转换为一个有向图，每条无向边对应两条有向边。
alpha : 浮点数
阻尼因子。
personalization: 字典, 可选
由包含图节点子集及其个性化值的字典组成的“个性化向量”。至少一个个性化值必须非零。如果未指定，节点的个性化值将为零。默认情况下，使用均匀分布。
nodelist : 列表, 可选
行和列根据nodelist中的节点排序。如果nodelist为None，则排序由G.nodes()生成。
weight : 键, 可选
用作权重的边数据键。如果为None，权重设置为1。
dangling: 字典, 可选
分配给任何“悬空”节点的出边，即没有出边的节点。字典键是出边指向的节点，字典值是该出边的权重。默认情况下，悬空节点根据个性化向量（如果未指定则为均匀分布）分配出边。这必须选择以产生不可约的转移矩阵（见下面的注释）。通常，悬空字典与个性化字典相同。
Returns
-------
A : 2D NumPy ndarray
图的Google矩阵
Notes
-----
返回的数组表示描述PageRank中使用的马尔可夫链的转移矩阵。为了使PageRank收敛到唯一解（即马尔可夫链中的唯一平稳分布），转移矩阵必须是不可约的。换句话说，图中每对节点之间必须存在路径，否则可能存在“排名下沉”。
此实现适用于多(有向)图。对于多图，两个节点之间的权重设置为这两个节点之间所有边权重的总和。
See Also
--------
pagerank
"""
import numpy as np
if nodelist is None:
nodelist = list(G)
A = nx.to_numpy_array(G, nodelist=nodelist, weight=weight)
N = len(G)
if N == 0:
return A
# Personalization vector
if personalization is None:
p = np.repeat(1.0 / N, N)
else:
p = np.array([personalization.get(n, 0) for n in nodelist], dtype=float)
if p.sum() == 0:
raise ZeroDivisionError
p /= p.sum()
# Dangling nodes
if dangling is None:
dangling_weights = p
else:
# Convert the dangling dictionary into an array in nodelist order
dangling_weights = np.array([dangling.get(n, 0) for n in nodelist], dtype=float)
dangling_weights /= dangling_weights.sum()
dangling_nodes = np.where(A.sum(axis=1) == 0)[0]
# Assign dangling_weights to any dangling nodes (nodes with no out links)
A[dangling_nodes] = dangling_weights
A /= A.sum(axis=1)[:, np.newaxis] # Normalize rows to sum to 1
return alpha * A + (1 - alpha) * p
def _pagerank_numpy(
G, alpha=0.85, personalization=None, weight="weight", dangling=None
):
"""返回图中节点的PageRank值。
PageRank根据图G中入链的结构计算节点排名。它最初被设计为一种网页排名算法。
Parameters
----------
G : 图
一个NetworkX图。无向图将被转换为一个有向图，每条无向边对应两条有向边。
alpha : 浮点数, 可选
PageRank的阻尼参数，默认为0.85。
personalization: 字典, 可选
由包含图节点子集及其个性化值的字典组成的“个性化向量”。至少一个个性化值必须非零。如果未指定，节点的个性化值将为零。默认使用均匀分布。
weight : 键, 可选
用作权重的边数据键。如果为None，权重设为1。
dangling: 字典, 可选
分配给任何“悬挂”节点的出边，即没有出边的节点。字典键是出边指向的节点，字典值是该出边的权重。默认情况下，悬挂节点根据个性化向量（如果未指定则为均匀分布）分配出边。这必须选择以产生不可约的转移矩阵（参见google_matrix下的注释）。通常，悬挂字典与个性化字典相同。
Returns
-------
pagerank : 字典
包含节点及其PageRank值的字典。
Examples
--------
>>> from networkx.algorithms.link_analysis.pagerank_alg import _pagerank_numpy
>>> G = nx.DiGraph(nx.path_graph(4))
>>> pr = _pagerank_numpy(G, alpha=0.9)
Notes
-----
特征向量计算使用NumPy与LAPACK特征值求解器的接口。这对于小图来说是最快且最准确的。
此实现适用于多(有向)图。对于多图，两个节点之间的权重设置为这两个节点之间所有边权重的总和。
See Also
--------
pagerank, google_matrix
References
----------
.. [1] A. Langville and C. Meyer,
"A survey of eigenvector methods of web information retrieval."
http://citeseer.ist.psu.edu/713792.html
.. [2] Page, Lawrence; Brin, Sergey; Motwani, Rajeev and Winograd, Terry,
The PageRank citation ranking: Bringing order to the Web. 1999
http://dbpubs.stanford.edu:8090/pub/showDoc.Fulltext?lang=en&doc=1999-66&format=pdf
"""
import numpy as np
if len(G) == 0:
return {}
M = google_matrix(
G, alpha, personalization=personalization, weight=weight, dangling=dangling
)
# use numpy LAPACK solver
eigenvalues, eigenvectors = np.linalg.eig(M.T)
ind = np.argmax(eigenvalues)
# eigenvector of largest eigenvalue is at ind, normalized
largest = np.array(eigenvectors[:, ind]).flatten().real
norm = largest.sum()
return dict(zip(G, map(float, largest / norm)))
def _pagerank_scipy(
G,
alpha=0.85,
personalization=None,
max_iter=100,
tol=1.0e-6,
nstart=None,
weight="weight",
dangling=None,
):
"""返回图中节点的PageRank值。
PageRank根据图G中入链的结构计算节点的排名。它最初被设计为一种对网页进行排名的算法。
Parameters
----------
G : 图
一个NetworkX图。无向图将被转换为一个有向图，每条无向边对应两条有向边。
alpha : 浮点数, 可选
PageRank的阻尼参数，默认为0.85。
personalization: 字典, 可选
由包含图节点子集及其个性化值的字典组成的“个性化向量”。至少一个个性化值必须非零。如果未指定，节点的个性化值将为零。默认使用均匀分布。
max_iter : 整数, 可选
幂方法特征值求解器中的最大迭代次数。
tol : 浮点数, 可选
用于检查幂方法求解器中收敛性的误差容限。迭代将在达到 ``len(G) * tol`` 的容限后停止。
nstart : 字典, 可选
每个节点的PageRank迭代初始值。
weight : 键, 可选
用作权重的边数据键。如果为None，权重设置为1。
dangling: 字典, 可选
分配给任何“悬挂”节点的出边，即没有出边的节点。字典键是出边指向的节点，字典值是该出边的权重。默认情况下，悬挂节点根据个性化向量（如果未指定则为均匀分布）分配出边。这必须选择以产生不可约的转移矩阵（参见google_matrix下的注释）。通常，悬挂字典与个性化字典相同。
Returns
-------
pagerank : 字典
包含节点及其PageRank值的字典
Examples
--------
>>> from networkx.algorithms.link_analysis.pagerank_alg import _pagerank_scipy
>>> G = nx.DiGraph(nx.path_graph(4))
>>> pr = _pagerank_scipy(G, alpha=0.9)
Notes
-----
特征向量计算使用带有SciPy稀疏矩阵表示的幂迭代。
此实现适用于多(有向)图。对于多图，两个节点之间的权重设置为这些节点之间所有边权重的总和。
See Also
--------
pagerank
Raises
------
PowerIterationFailedConvergence
如果算法在幂迭代方法的指定迭代次数内未收敛到指定容限。
References
----------
.. [1] A. Langville and C. Meyer,
"A survey of eigenvector methods of web information retrieval."
http://citeseer.ist.psu.edu/713792.html
.. [2] Page, Lawrence; Brin, Sergey; Motwani, Rajeev and Winograd, Terry,
The PageRank citation ranking: Bringing order to the Web. 1999
http://dbpubs.stanford.edu:8090/pub/showDoc.Fulltext?lang=en&doc=1999-66&format=pdf
"""
import numpy as np
import scipy as sp
N = len(G)
if N == 0:
return {}
nodelist = list(G)
A = nx.to_scipy_sparse_array(G, nodelist=nodelist, weight=weight, dtype=float)
S = A.sum(axis=1)
S[S != 0] = 1.0 / S[S != 0]
# TODO: csr_array
Q = sp.sparse.csr_array(sp.sparse.spdiags(S.T, 0, *A.shape))
A = Q @ A
# initial vector
if nstart is None:
x = np.repeat(1.0 / N, N)
else:
x = np.array([nstart.get(n, 0) for n in nodelist], dtype=float)
x /= x.sum()
# Personalization vector
if personalization is None:
p = np.repeat(1.0 / N, N)
else:
p = np.array([personalization.get(n, 0) for n in nodelist], dtype=float)
if p.sum() == 0:
raise ZeroDivisionError
p /= p.sum()
# Dangling nodes
if dangling is None:
dangling_weights = p
else:
# Convert the dangling dictionary into an array in nodelist order
dangling_weights = np.array([dangling.get(n, 0) for n in nodelist], dtype=float)
dangling_weights /= dangling_weights.sum()
is_dangling = np.where(S == 0)[0]
# power iteration: make up to max_iter iterations
for _ in range(max_iter):
xlast = x
x = alpha * (x @ A + sum(x[is_dangling]) * dangling_weights) + (1 - alpha) * p
# check convergence, l1 norm
err = np.absolute(x - xlast).sum()
if err < N * tol:
return dict(zip(nodelist, map(float, x)))
raise nx.PowerIterationFailedConvergence(max_iter)
