内置算法

graphscope.nx.builtin.hits(G, max_iter=100, tol=1e-08, nstart=None, normalized=True)

返回节点的HITS枢纽值和权威值。

HITS算法为节点计算两个数值。 权威值(Authorities)基于入链评估节点价值。 枢纽值(Hubs)基于出链评估节点价值。

Parameters:

• G (图) – 一个NetworkX图

• max_iter (整数, 可选) – 幂方法中的最大迭代次数。

• tol (float, optional) – 用于检查幂法迭代收敛性的误差容忍度。

• nstart (dictionary, optional) – 用于幂方法迭代的每个节点的初始值。

• normalized (bool (默认=True)) – 将所有值的总和归一化处理结果。

Returns:

(hubs,authorities) – 两个以节点为键的字典，分别包含hub和authority的值。

Return type:

字典的双元组

Raises:

PowerIterationFailedConvergence - 如果算法未能在幂迭代方法指定的迭代次数内收敛到指定的容差。

示例

>>> G = nx.path_graph(4)
>>> h, a = nx.hits(G)

备注

特征向量计算采用幂迭代法完成，无法保证收敛性。迭代将在达到max_iter次迭代或误差容限number_of_nodes(G)*tol时停止。

HITS算法专为有向图设计，但该算法不会检查输入图是否为有向图，也将在无向图上执行。

参考文献

[1]

A. Langville and C. Meyer, “A survey of eigenvector methods of web information retrieval.” http://citeseer.ist.psu.edu/713792.html

[2]

乔恩·克莱因伯格， 超链接环境中的权威来源 《ACM期刊》第46卷(5期):604-32页，1999年。 doi:10.1145/324133.324140。 http://www.cs.cornell.edu/home/kleinber/auth.pdf。

graphscope.nx.builtin.degree_centrality(G)

计算节点的度中心性。

节点v的度中心性是指与其相连的节点所占的比例。

Parameters:

G (图) – 一个networkx图

Returns:

nodes – 以度中心性为值的节点字典。

Return type:

字典

另请参阅

betweenness_centrality, load_centrality, eigenvector_centrality

备注

度中心性值通过除以简单图中的最大可能度数n-1进行归一化，其中n是图G中的节点数量。

对于多重图或带自环的图，最大度数可能超过n-1，此时度中心性值大于1的情况是可能出现的。

graphscope.nx.builtin.in_degree_centrality(G)

计算节点的入度中心性。

节点v的入度中心性是指其入边所连接的节点所占的比例。

Parameters:

G (图) – 一个NetworkX图

Returns:

nodes – 以入度中心性为值的节点字典。

Return type:

字典

Raises:

NetworkXNotImplemented – 如果图G是无向的。

另请参阅

degree_centrality, out_degree_centrality

备注

度中心性值通过除以简单图中的最大可能度数n-1进行归一化，其中n是图G中的节点数量。

对于多重图或带自环的图，最大度数可能超过n-1，此时度中心性值大于1的情况是可能出现的。

graphscope.nx.builtin.out_degree_centrality(G)

计算节点的出度中心性。

节点v的出度中心性是其出边所连接的节点所占的比例。

Parameters:

G (图) – 一个NetworkX图

Returns:

nodes – 以出度中心性为值的节点字典。

Return type:

字典

Raises:

NetworkXNotImplemented – 如果图G是无向的。

另请参阅

degree_centrality, in_degree_centrality

备注

度中心性值通过除以简单图中的最大可能度数n-1进行归一化，其中n是图G中的节点数量。

对于多重图或带自环的图，最大度数可能超过n-1，此时度中心性值大于1的情况是可能出现的。

graphscope.nx.builtin.eigenvector_centrality(G, max_iter=100, tol=1e-06, nstart=None, weight=None)

计算图G的特征向量中心性。

特征向量中心性基于节点的邻居中心性来计算该节点的中心性。节点$i$的特征向量中心性是向量$x$的第$i$个元素，该向量由以下方程定义

\[Ax = \lambda x\]

其中$A$是图G的邻接矩阵，其特征值为$lambda$。根据Perron-Frobenius定理，当$lambda$是邻接矩阵$A$的最大特征值时，存在唯一的解$x$，且其所有分量均为正数([2]_)。

Parameters:

• G (图) – 一个networkx图

• max_iter (integer, optional (default=100)) – 幂方法中的最大迭代次数。

• tol (float, optional (default=1.0e-6)) – 幂迭代法中用于检查收敛性的误差容限。

• nstart (dictionary, optional (default=None)) – 每个节点特征向量迭代的初始值。

• weight (None or string, optional (default=None)) – 如果为None，则所有边的权重被视为相等。 否则指定用作权重的边属性名称。 在此度量中，权重被解释为连接强度。

Returns:

nodes – 以特征向量中心性为值的节点字典。

Return type:

字典

示例

>>> G = nx.path_graph(4)
>>> centrality = nx.eigenvector_centrality(G)
>>> sorted((v, f"{c:0.2f}") for v, c in centrality.items())
[(0, '0.37'), (1, '0.60'), (2, '0.60'), (3, '0.37')]

Raises:

• NetworkXPointlessConcept – 如果图 G 是空图。

• NetworkXError – 如果nstart中的每个值都为零。

• PowerIterationFailedConvergence - 如果算法在幂迭代方法的指定迭代次数内未能收敛到指定的容差。

另请参阅

eigenvector_centrality_numpy, pagerank, hits

备注

该测量方法由[1]_提出，并在[2]_中进行了讨论。

幂迭代方法用于计算特征向量，但不保证收敛。我们的方法在达到max_iter次迭代后停止，或者当两次迭代间计算向量的变化小于误差容限G.number_of_nodes() * tol时停止。此实现使用($A + I$)而非邻接矩阵$A$，因为它通过平移谱来确保即使在具有多个主导特征值的网络中也能识别出正确的特征向量。

对于有向图，这是“左”特征向量中心性，对应于图中的入边。要计算出边的特征向量中心性，首先需要使用G.reverse()反转图。

参考文献

[1]

菲利普·博纳西奇。 "权力与中心性：一系列衡量指标。" 美国社会学杂志 92(5):1170–1182, 1986 <http://www.leonidzhukov.net/hse/2014/socialnetworks/papers/Bonacich-Centrality.pdf>

[2]

马克·E·J·纽曼。 网络：导论。 美国牛津大学出版社，2010年，第169页。

graphscope.nx.builtin.katz_centrality(G, alpha=0.1, beta=1.0, max_iter=100, tol=1e-06, nstart=None, normalized=True, weight=None)

计算图G中节点的Katz中心性。

Katz中心性通过邻居节点的中心性来计算一个节点的中心性。它是特征向量中心性的一种推广。节点$i$的Katz中心性计算公式为

\[x_i = \alpha \sum_{j} A_{ij} x_j + \beta,\]

其中$A$是图G的邻接矩阵，其特征值为$lambda$。

参数$beta$控制初始中心度

\[\alpha < \frac{1}{\lambda_{\max}}.\]

Katz中心性通过测量直接邻居(第一度节点)的数量以及网络中通过这些直接邻居连接到所考虑节点的所有其他节点，来计算节点在网络中的相对影响力。

可以通过参数$beta$为直接邻居提供额外的权重。然而，与远距离邻居建立的连接会受到衰减因子$alpha$的惩罚，该因子必须严格小于邻接矩阵最大特征值的倒数，才能正确计算Katz中心性。更多信息请参阅[1]_。

Parameters:

• G (图) – 一个NetworkX图。

• alpha (float) – 衰减因子

• beta (标量 或 字典, 可选 (默认=1.0)) - 赋予直接邻域的权重。如果不是标量，则该字典必须为每个节点都包含一个值。

• max_iter (integer, optional (default=1000)) – 幂方法中的最大迭代次数。

• tol (float, optional (default=1.0e-6)) – 幂迭代法中用于检查收敛性的误差容限。

• nstart (dictionary, optional) – 每个节点的Katz迭代初始值。

• normalized (bool, optional (default=True)) – 如果为True，则对结果值进行归一化处理。

• weight (None or string, optional (default=None)) - 如果为None，则所有边的权重被视为相等。 否则指定用作权重的边属性名称。 在此度量中，权重被解释为连接强度。

Returns:

nodes – 以Katz中心性为值的节点字典。

Return type:

字典

Raises:

• NetworkXError - 如果参数beta不是标量且至少有一个节点缺少值

• PowerIterationFailedConvergence - 如果算法在幂迭代方法的指定迭代次数内未能收敛到指定的容差。

示例

>>> import math
>>> G = nx.path_graph(4)
>>> phi = (1 + math.sqrt(5)) / 2.0  # largest eigenvalue of adj matrix
>>> centrality = nx.katz_centrality(G, 1 / phi - 0.01)
>>> for n, c in sorted(centrality.items()):
...     print(f"{n} {c:.2f}")
0 0.37
1 0.60
2 0.60
3 0.37

另请参阅

katz_centrality_numpy, eigenvector_centrality, eigenvector_centrality_numpy, pagerank, hits

备注

Katz中心性由[2]_提出。

该算法利用幂法寻找图G邻接矩阵最大特征值对应的特征向量。 参数alpha必须严格小于邻接矩阵最大特征值的倒数，算法才能收敛。 您可以使用max(nx.adjacency_spectrum(G))获取邻接矩阵的最大特征值$lambda_{max}$。 迭代将在达到max_iter次迭代或number_of_nodes(G) * tol的误差容限时停止。

当 $alpha = 1/lambda_{max}$ 且 $beta=0$ 时，Katz中心性与特征向量中心性相同。

对于有向图，此方法找到对应于图中入边的"左"特征向量。对于出边的Katz中心性，首先需要使用G.reverse()反转图。

参考文献

[1]

马克·E·J·纽曼： 《网络：导论》。 牛津大学出版社，美国，2010年，第720页。

[2]

Leo Katz: 一种源自社会测量指数的新状态指标。 Psychometrika 18(1):39–43, 1953 https://link.springer.com/content/pdf/10.1007/BF02289026.pdf

graphscope.nx.builtin.has_path(G, source, target)

如果G中存在从source到target的路径，则返回True。

Parameters:

• G (NetworkX图) –

• source (node) – 路径的起始节点

• target (node) – 路径的终点节点

graphscope.nx.builtin.average_shortest_path_length(G, weight=None, method=None)

返回平均最短路径长度。

平均最短路径长度为

\[a =\sum_{s,t \in V} \frac{d(s, t)}{n(n-1)}\]

其中V是G中的节点集合， d(s, t)是从s到t的最短路径， n是G中的节点数量。

Parameters:

• G (NetworkX 图) –

• weight (None, string or function, optional (default = None)) – 如果为None，则每条边的权重/距离/成本均为1。 如果是字符串，则使用该边属性作为边的权重。 任何不存在的边属性默认为1。 如果这是一个函数，则边的权重是该函数返回的值。 该函数必须恰好接受三个位置参数：边的两个端点和该边的属性字典。 该函数必须返回一个数字。

• method (string, optional (default = 'unweighted' or 'djikstra')) – 用于计算路径长度的算法。 支持的选项有 'unweighted'、'dijkstra'、'bellman-ford'、 'floyd-warshall' 和 'floyd-warshall-numpy'。 其他方法值将引发 ValueError 异常。 如果 weight 为 None，则默认方法是 'unweighted'， 否则默认方法是 'dijkstra'。

Raises:

• NetworkXPointlessConcept – 如果 G 是空图（即零节点的图）。

• NetworkXError – 如果G不是连通图（对于有向图的情况，如果不是弱连通图）。

• ValueError – 如果method不在支持的选项范围内。

示例

>>> G = nx.path_graph(5)
>>> nx.average_shortest_path_length(G)
2.0

对于不连通的图，您可以计算每个连通分量的平均最短路径长度

>>> G = nx.Graph([(1, 2), (3, 4)])
>>> for C in (G.subgraph(c).copy() for c in nx.connected_components(G)):
...     print(nx.average_shortest_path_length(C))
1.0
1.0

graphscope.nx.builtin.bfs_edges(G, source, depth_limit=None)

从源点开始的广度优先搜索中的边。

Parameters:

• G (networkx图) –

• source (node) - 指定广度优先搜索的起始节点；该函数仅遍历从该节点可达的组件中的边。

• depth_limit (int, optional(default=len(G))) - 指定最大搜索深度

Returns:

edges – 广度优先搜索中的边列表。

Return type:

列表

示例

以广度优先搜索获取边：

>>> G = nx.path_graph(3)
>>> list(nx.bfs_edges(G, 0))
[(0, 1), (1, 2)]
>>> list(nx.bfs_edges(G, source=0, depth_limit=1))
[(0, 1)]

graphscope.nx.builtin.k_core(G, k=None, core_number=None)

返回图G的k核。

k-core（k核）是指一个最大子图，其中包含度数为k或更高的节点。

Parameters:

• G (networkx 图) – 一个图或有向图

• k (int, optional) – 核心的阶数。如果未指定，则返回主核心。

Returns:

• :class:`VertexDataContext` (一个为每个顶点分配布尔值的上下文：)

• 如果顶点满足k-core条件则为1，否则为0。

参考文献

[1]

一种用于网络核心分解的O(m)算法 Vladimir Batagelj 和 Matjaz Zaversnik，2003年。 https://arxiv.org/abs/cs.DS/0310049

graphscope.nx.builtin.clustering(G, nodes=None, weight=None)

计算节点的聚类系数。

对于无权图，节点\(u\)的聚类系数表示通过该节点实际存在的三角形数量与可能存在的三角形总数之比。

\[c_u = \frac{2 T(u)}{deg(u)(deg(u)-1)},\]

其中\(T(u)\)表示通过节点\(u\)的三角形数量， \(deg(u)\)表示节点\(u\)的度数。

对于加权图，有几种定义聚类系数的方法[1]_。 这里采用的定义方式是子图边权重的几何平均值[2]_，

\[c_u = \frac{1}{deg(u)(deg(u)-1))} \sum_{vw} (\hat{w}_{uv} \hat{w}_{uw} \hat{w}_{vw})^{1/3}.\]

边权重 \(\hat{w}_{uv}\) 通过网络中的最大权重进行归一化处理 \(\hat{w}_{uv} = w_{uv}/\max(w)\)。

如果\(deg(u) < 2\)，则\(c_u\)的值被赋为0。

此外，这个加权定义已被推广以支持负边权重[3]。

对于有向图，聚类的定义类似，分别针对无权有向图和加权有向图，计算所有可能的有向三角形占比或子图边权重的几何平均值[4]。

\[c_u = \frac{2}{deg^{tot}(u)(deg^{tot}(u)-1) - 2deg^{\leftrightarrow}(u)} T(u),\]

其中\(T(u)\)表示通过节点\(u\)的有向三角形数量，\(deg^{tot}(u)\)是节点\(u\)的入度和出度之和，而\(deg^{\leftrightarrow}(u)\)表示节点\(u\)的互惠度。

Parameters:

• G (图) –

• nodes (container of nodes, optional (default=all nodes in G)) – 计算该容器中节点的聚类。

• weight (string or None, optional (default=None)) – 表示权重的边属性名称，该数值将作为权重值使用。如果为None，则每条边的权重默认为1。

Returns:

out – 指定节点处的聚类系数

Return type:

浮点数或字典

示例

>>> G = nx.complete_graph(5)
>>> print(nx.clustering(G, 0))
1.0
>>> print(nx.clustering(G))
{0: 1.0, 1: 1.0, 2: 1.0, 3: 1.0, 4: 1.0}

备注

自循环将被忽略。

参考文献

[1]

J. Saramäki、M. Kivelä、J.-P. Onnela、K. Kaski和J. Kertész在《Physical Review E》75卷027105期(2007年)发表的加权复杂网络聚类系数泛化研究。 http://jponnela.com/web_documents/a9.pdf

[2]

加权复杂网络中模体的强度和相干性，作者：J. P. Onnela, J. Saramäki, J. Kertész 和 K. Kaski，发表于《物理评论E》，71(6)，065103 (2005)。

[3]

符号相关网络中聚类系数的泛化 作者：G. Costantini 和 M. Perugini，发表于《公共科学图书馆·综合》期刊，9(2)，e88669 (2014)。

[4]

G. Fagiolo在复杂有向网络中的聚类研究， 《物理评论E》，76(2)，026107（2007年）。

graphscope.nx.builtin.triangles(G, nodes=None)

计算三角形的数量。

计算包含某个节点作为一个顶点的三角形数量。

Parameters:

• G (图) – 一个networkx图

• nodes (节点容器，可选（默认=G中的所有节点）) – 计算该容器中节点的三角形。

Returns:

out – 按节点标签统计的三角形数量。

Return type:

字典

示例

>>> G = nx.complete_graph(5)
>>> print(nx.triangles(G, 0))
6
>>> print(nx.triangles(G))
{0: 6, 1: 6, 2: 6, 3: 6, 4: 6}
>>> print(list(nx.triangles(G, (0, 1)).values()))
[6, 6]

备注

当计算整个图的三角形时，每个三角形会被计数三次，每个节点一次。自循环将被忽略。

graphscope.nx.builtin.average_clustering(G, nodes=None, weight=None, count_zeros=True)

计算图G的平均聚类系数。

该图的聚类系数是平均值，

\[C = \frac{1}{n}\sum_{v \in G} c_v,\]

其中 \(n\) 表示 G 中的节点数量。

Parameters:

• G (图) –

• nodes (节点容器，可选（默认=G中的所有节点）) – 计算此容器中节点的平均聚类系数。

• weight (string or None, optional (default=None)) – 表示权重的边属性名称，该数值将作为权重值使用。如果为None，则每条边的权重默认为1。

• count_zeros (bool) – 如果为False，则平均值中仅包含聚类系数非零的节点。

Returns:

avg – 平均聚类系数

Return type:

浮点数

示例

>>> G = nx.complete_graph(5)
>>> print(nx.average_clustering(G))
1.0

备注

这是一个节省空间的例程；使用聚类函数获取列表再取平均值可能会更快。

自循环将被忽略。

参考文献

[1]

J. Saramäki、M. Kivelä、J.-P. Onnela、K. Kaski和J. Kertész在《Physical Review E》75卷027105期(2007年)发表的加权复杂网络聚类系数泛化研究。 http://jponnela.com/web_documents/a9.pdf

[2]

Marcus Kaiser, 平均聚类系数：孤立节点和叶子节点对小世界网络聚类测度的影响。 https://arxiv.org/abs/0802.2512