"""图论中用于描述图中三角形数量的算法。"""
from collections import Counter
from itertools import chain, combinations
import networkx as nx
from networkx.utils import not_implemented_for
__all__ = [
"triangles",
"average_clustering",
"clustering",
"transitivity",
"square_clustering",
"generalized_degree",
]
[docs]
@not_implemented_for("directed")
@nx._dispatchable
def triangles(G, nodes=None):
"""计算三角形的数量。
查找包含某个节点作为其中一个顶点的三角形数量。
Parameters
----------
G : 图
一个 networkx 图
nodes : 节点, 可迭代节点, 或 None (默认=None)
如果是一个单独的节点，返回该节点的三角形数量。
如果是一个可迭代对象，计算其中每个节点的三角形数量。
如果为 `None` （默认值），计算 `G` 中所有节点的三角形数量。
Returns
-------
out : 字典或整数
如果 `nodes` 是一个节点容器，返回按节点键控的三角形数量（字典）。
如果 `nodes` 是一个特定节点，返回该节点的三角形数量（整数）。
Examples
--------
>>> 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]
Notes
-----
自环被忽略。
"""
if nodes is not None:
# If `nodes` represents a single node, return only its number of triangles
if nodes in G:
return next(_triangles_and_degree_iter(G, nodes))[2] // 2
# if `nodes` is a container of nodes, then return a
# dictionary mapping node to number of triangles.
return {v: t // 2 for v, d, t, _ in _triangles_and_degree_iter(G, nodes)}
# if nodes is None, then compute triangles for the complete graph
# dict used to avoid visiting the same nodes twice
# this allows calculating/counting each triangle only once
later_nbrs = {}
# iterate over the nodes in a graph
for node, neighbors in G.adjacency():
later_nbrs[node] = {n for n in neighbors if n not in later_nbrs and n != node}
# instantiate Counter for each node to include isolated nodes
# add 1 to the count if a nodes neighbor's neighbor is also a neighbor
triangle_counts = Counter(dict.fromkeys(G, 0))
for node1, neighbors in later_nbrs.items():
for node2 in neighbors:
third_nodes = neighbors & later_nbrs[node2]
m = len(third_nodes)
triangle_counts[node1] += m
triangle_counts[node2] += m
triangle_counts.update(third_nodes)
return dict(triangle_counts)
@not_implemented_for("multigraph")
def _triangles_and_degree_iter(G, nodes=None):
"""返回一个迭代器，包含节点、度数、三角形数和广义度数。
三角形数会重复计算，因此你可能需要将其除以2。
有关定义和详细信息，请参阅degree()、triangles()和generalized_degree()。
"""
if nodes is None:
nodes_nbrs = G.adj.items()
else:
nodes_nbrs = ((n, G[n]) for n in G.nbunch_iter(nodes))
for v, v_nbrs in nodes_nbrs:
vs = set(v_nbrs) - {v}
gen_degree = Counter(len(vs & (set(G[w]) - {w})) for w in vs)
ntriangles = sum(k * val for k, val in gen_degree.items())
yield (v, len(vs), ntriangles, gen_degree)
@not_implemented_for("multigraph")
def _weighted_triangles_and_degree_iter(G, nodes=None, weight="weight"):
"""返回一个迭代器，包含节点、度数和加权三角形。
用于加权聚类。
注意：这返回三角形中边的几何平均权重。
此外，每个三角形会被计算两次（每个方向）。
因此，您可能希望除以2。
"""
import numpy as np
if weight is None or G.number_of_edges() == 0:
max_weight = 1
else:
max_weight = max(d.get(weight, 1) for u, v, d in G.edges(data=True))
if nodes is None:
nodes_nbrs = G.adj.items()
else:
nodes_nbrs = ((n, G[n]) for n in G.nbunch_iter(nodes))
def wt(u, v):
return G[u][v].get(weight, 1) / max_weight
for i, nbrs in nodes_nbrs:
inbrs = set(nbrs) - {i}
weighted_triangles = 0
seen = set()
for j in inbrs:
seen.add(j)
# This avoids counting twice -- we double at the end.
jnbrs = set(G[j]) - seen
# Only compute the edge weight once, before the inner inner
# loop.
wij = wt(i, j)
weighted_triangles += np.cbrt(
[(wij * wt(j, k) * wt(k, i)) for k in inbrs & jnbrs]
).sum()
yield (i, len(inbrs), 2 * float(weighted_triangles))
@not_implemented_for("multigraph")
def _directed_triangles_and_degree_iter(G, nodes=None):
"""返回一个迭代器，包含
(节点, 总度数, 倒数度数, 有向三角形)。
用于有向聚类。
注意，与 `_triangles_and_degree_iter()` 不同，此函数计算
有向三角形，因此不会重复计算三角形。
"""
nodes_nbrs = ((n, G._pred[n], G._succ[n]) for n in G.nbunch_iter(nodes))
for i, preds, succs in nodes_nbrs:
ipreds = set(preds) - {i}
isuccs = set(succs) - {i}
directed_triangles = 0
for j in chain(ipreds, isuccs):
jpreds = set(G._pred[j]) - {j}
jsuccs = set(G._succ[j]) - {j}
directed_triangles += sum(
1
for k in chain(
(ipreds & jpreds),
(ipreds & jsuccs),
(isuccs & jpreds),
(isuccs & jsuccs),
)
)
dtotal = len(ipreds) + len(isuccs)
dbidirectional = len(ipreds & isuccs)
yield (i, dtotal, dbidirectional, directed_triangles)
@not_implemented_for("multigraph")
def _directed_weighted_triangles_and_degree_iter(G, nodes=None, weight="weight"):
"""返回一个迭代器，包含节点、总度数、倒数度数和有向加权三角形的数量。
用于有向加权聚类。请注意，与 `_weighted_triangles_and_degree_iter()` 不同，此函数计算有向三角形，因此不会重复计算三角形。
"""
import numpy as np
if weight is None or G.number_of_edges() == 0:
max_weight = 1
else:
max_weight = max(d.get(weight, 1) for u, v, d in G.edges(data=True))
nodes_nbrs = ((n, G._pred[n], G._succ[n]) for n in G.nbunch_iter(nodes))
def wt(u, v):
return G[u][v].get(weight, 1) / max_weight
for i, preds, succs in nodes_nbrs:
ipreds = set(preds) - {i}
isuccs = set(succs) - {i}
directed_triangles = 0
for j in ipreds:
jpreds = set(G._pred[j]) - {j}
jsuccs = set(G._succ[j]) - {j}
directed_triangles += np.cbrt(
[(wt(j, i) * wt(k, i) * wt(k, j)) for k in ipreds & jpreds]
).sum()
directed_triangles += np.cbrt(
[(wt(j, i) * wt(k, i) * wt(j, k)) for k in ipreds & jsuccs]
).sum()
directed_triangles += np.cbrt(
[(wt(j, i) * wt(i, k) * wt(k, j)) for k in isuccs & jpreds]
).sum()
directed_triangles += np.cbrt(
[(wt(j, i) * wt(i, k) * wt(j, k)) for k in isuccs & jsuccs]
).sum()
for j in isuccs:
jpreds = set(G._pred[j]) - {j}
jsuccs = set(G._succ[j]) - {j}
directed_triangles += np.cbrt(
[(wt(i, j) * wt(k, i) * wt(k, j)) for k in ipreds & jpreds]
).sum()
directed_triangles += np.cbrt(
[(wt(i, j) * wt(k, i) * wt(j, k)) for k in ipreds & jsuccs]
).sum()
directed_triangles += np.cbrt(
[(wt(i, j) * wt(i, k) * wt(k, j)) for k in isuccs & jpreds]
).sum()
directed_triangles += np.cbrt(
[(wt(i, j) * wt(i, k) * wt(j, k)) for k in isuccs & jsuccs]
).sum()
dtotal = len(ipreds) + len(isuccs)
dbidirectional = len(ipreds & isuccs)
yield (i, dtotal, dbidirectional, float(directed_triangles))
[docs]
@nx._dispatchable(edge_attrs="weight")
def average_clustering(G, nodes=None, weight=None, count_zeros=True):
r"""计算图 G 的平均聚类系数。
图的聚类系数是平均值，
.. math::
C = \frac{1}{n}\sum_{v \in G} c_v,
其中 :math:`n` 是图 `G` 中的节点数。
Parameters
----------
G : 图
nodes : 节点容器，可选（默认=G 中的所有节点）
计算该容器中节点的平均聚类系数。
weight : 字符串或 None，可选（默认=None）
作为权重使用的边属性。
如果为 None，则每条边的权重为 1。
count_zeros : 布尔值
如果为 False，则仅在平均值中包含具有非零聚类系数的节点。
Returns
-------
avg : 浮点数
平均聚类系数
Examples
--------
>>> G = nx.complete_graph(5)
>>> print(nx.average_clustering(G))
1.0
Notes
-----
这是一个节省空间的例程；使用聚类函数获取列表然后取平均值可能会更快。
自环被忽略。
References
----------
.. [1] J. Saramäki, M. Kivelä, J.-P. Onnela, K. Kaski 和 J. Kertész 对加权复杂网络的聚类系数进行了推广，物理评论 E, 75 027105 (2007)。
http://jponnela.com/web_documents/a9.pdf
.. [2] Marcus Kaiser, 平均聚类系数：小世界网络中孤立节点和叶节点对聚类测量的作用。
https://arxiv.org/abs/0802.2512
"""
c = clustering(G, nodes, weight=weight).values()
if not count_zeros:
c = [v for v in c if abs(v) > 0]
return sum(c) / len(c)
[docs]
@nx._dispatchable(edge_attrs="weight")
def clustering(G, nodes=None, weight=None):
r"""计算节点的聚类系数。
对于无权图，节点 :math:`u` 的聚类系数是经过该节点的可能三角形的存在的比例，
.. math::
c_u = \frac{2 T(u)}{deg(u)(deg(u)-1)},
其中 :math:`T(u)` 是经过节点 :math:`u` 的三角形数量，:math:`deg(u)` 是 :math:`u` 的度。
对于加权图，有几种定义聚类系数的方法 [1]_。这里使用的是子图边权重的几何平均值 [2]_，
.. math::
c_u = \frac{1}{deg(u)(deg(u)-1))}
\sum_{vw} (\hat{w}_{uv} \hat{w}_{uw} \hat{w}_{vw})^{1/3}.
边权重 :math:`\hat{w}_{uv}` 通过网络中的最大权重进行归一化 :math:`\hat{w}_{uv} = w_{uv}/\max(w)` 。
如果 :math:`deg(u) < 2` ，则 :math:`c_u` 的值被赋为 0。
此外，这种加权定义已被推广以支持负边权重 [3]_。
对于有向图，聚类系数同样定义为所有可能的有向三角形的比例或无权和加权有向图的子图边权重的几何平均值 [4]_。
.. math::
c_u = \frac{T(u)}{2(deg^{tot}(u)(deg^{tot}(u)-1) - 2deg^{\leftrightarrow}(u))},
其中 :math:`T(u)` 是经过节点 :math:`u` 的有向三角形数量，:math:`deg^{tot}(u)` 是 :math:`u` 的入度和出度之和，:math:`deg^{\leftrightarrow}(u)` 是 :math:`u` 的互反度。
Parameters
----------
G : 图
nodes : 节点, 节点集合, 或 None (默认=None)
如果是一个单独的节点，返回该节点的三角形数量。
如果是一个可迭代对象，计算这些节点的三角形数量。
如果为 `None` （默认），计算 `G` 中所有节点的三角形数量。
weight : 字符串或 None, 可选 (默认=None)
边属性，持有作为权重的数值。
如果为 None，则每条边的权重为 1。
Returns
-------
out : 浮点数, 或字典
指定节点的聚类系数
Examples
--------
>>> 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}
Notes
-----
自环被忽略。
References
----------
.. [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 对加权复杂网络中的模体强度和一致性进行了研究，Physical Review E, 71(6), 065103 (2005).
.. [3] G. Costantini 和 M. Perugini 对聚类系数进行了有符号相关网络的一般化，PloS one, 9(2), e88669 (2014).
.. [4] G. Fagiolo 对复杂有向网络中的聚类进行了研究，Physical Review E, 76(2), 026107 (2007).
"""
if G.is_directed():
if weight is not None:
td_iter = _directed_weighted_triangles_and_degree_iter(G, nodes, weight)
clusterc = {
v: 0 if t == 0 else t / ((dt * (dt - 1) - 2 * db) * 2)
for v, dt, db, t in td_iter
}
else:
td_iter = _directed_triangles_and_degree_iter(G, nodes)
clusterc = {
v: 0 if t == 0 else t / ((dt * (dt - 1) - 2 * db) * 2)
for v, dt, db, t in td_iter
}
else:
# The formula 2*T/(d*(d-1)) from docs is t/(d*(d-1)) here b/c t==2*T
if weight is not None:
td_iter = _weighted_triangles_and_degree_iter(G, nodes, weight)
clusterc = {v: 0 if t == 0 else t / (d * (d - 1)) for v, d, t in td_iter}
else:
td_iter = _triangles_and_degree_iter(G, nodes)
clusterc = {v: 0 if t == 0 else t / (d * (d - 1)) for v, d, t, _ in td_iter}
if nodes in G:
# Return the value of the sole entry in the dictionary.
return clusterc[nodes]
return clusterc
[docs]
@nx._dispatchable
def transitivity(G):
r"""计算图的传递性，即图中存在的所有可能三角形的比例。
可能的三角形通过“三元组”（两条共享一个顶点的边）的数量来识别。
传递性计算公式为：
.. math::
T = 3\frac{\#triangles}{\#triads}.
Parameters
----------
G : 图
Returns
-------
out : float
传递性
Notes
-----
忽略自环。
Examples
--------
>>> G = nx.complete_graph(5)
>>> print(nx.transitivity(G))
1.0
"""
triangles_contri = [
(t, d * (d - 1)) for v, d, t, _ in _triangles_and_degree_iter(G)
]
# If the graph is empty
if len(triangles_contri) == 0:
return 0
triangles, contri = map(sum, zip(*triangles_contri))
return 0 if triangles == 0 else triangles / contri
[docs]
@nx._dispatchable
def square_clustering(G, nodes=None):
r"""计算节点的平方聚类系数。
对于每个节点，返回存在的平方数与可能的平方数的比例 [1]_
.. math::
C_4(v) = \frac{ \sum_{u=1}^{k_v}
\sum_{w=u+1}^{k_v} q_v(u,w) }{ \sum_{u=1}^{k_v}
\sum_{w=u+1}^{k_v} [a_v(u,w) + q_v(u,w)]},
其中 :math:`q_v(u,w)` 是 :math:`u` 和 :math:`w` 除了 :math:`v` 之外的共同邻居数（即平方数），而 :math:`a_v(u,w) = (k_u -
(1+q_v(u,w)+\theta_{uv})) + (k_w - (1+q_v(u,w)+\theta_{uw}))` ，其中
:math:`\theta_{uw} = 1` 如果 :math:`u` 和 :math:`w` 相连，否则为 0。 [2]_
Parameters
----------
G : 图
nodes : 节点容器，可选（默认=G中的所有节点）
计算容器中节点的聚类系数。
Returns
-------
c4 : 字典
一个以节点为键，平方聚类系数值为值的字典。
Examples
--------
>>> G = nx.complete_graph(5)
>>> print(nx.square_clustering(G, 0))
1.0
>>> print(nx.square_clustering(G))
{0: 1.0, 1: 1.0, 2: 1.0, 3: 1.0, 4: 1.0}
Notes
-----
虽然 :math:`C_3(v)` （三角形聚类）给出了节点 v 的两个邻居相互连接的概率，但 :math:`C_4(v)` 是节点 v 的两个邻居共享一个不同于 v 的共同邻居的概率。此算法可应用于二分图和单分图网络。
References
----------
.. [1] Pedro G. Lind, Marta C. González, and Hans J. Herrmann. 2005
Cycles and clustering in bipartite networks.
Physical Review E (72) 056127.
.. [2] Zhang, Peng et al. Clustering Coefficient and Community Structure of
Bipartite Networks. Physica A: Statistical Mechanics and its Applications 387.27 (2008): 6869–6875.
https://arxiv.org/abs/0710.0117v1
"""
if nodes is None:
node_iter = G
else:
node_iter = G.nbunch_iter(nodes)
clustering = {}
for v in node_iter:
clustering[v] = 0
potential = 0
for u, w in combinations(G[v], 2):
squares = len((set(G[u]) & set(G[w])) - {v})
clustering[v] += squares
degm = squares + 1
if w in G[u]:
degm += 1
potential += (len(G[u]) - degm) + (len(G[w]) - degm) + squares
if potential > 0:
clustering[v] /= potential
if nodes in G:
# Return the value of the sole entry in the dictionary.
return clustering[nodes]
return clustering
[docs]
@not_implemented_for("directed")
@nx._dispatchable
def generalized_degree(G, nodes=None):
r"""计算节点的广义度。
对于每个节点，广义度显示该节点连接了多少条具有给定三角形重数的边。边的三角形重数是该边参与的三角形数量。节点 :math:`i` 的广义度可以写成向量 :math:`\mathbf{k}_i=(k_i^{(0)}, \dotsc, k_i^{(N-2)})` ，其中 :math:`k_i^{(j)}` 是连接到节点 :math:`i` 并参与 :math:`j` 个三角形的边的数量。
Parameters
----------
G : 图
nodes : 节点容器，可选（默认=G中的所有节点）
计算容器中节点的广义度。
Returns
-------
out : Counter，或 Counter 的字典
指定节点的广义度。Counter 按边的三角形重数键入。
Examples
--------
>>> G = nx.complete_graph(5)
>>> print(nx.generalized_degree(G, 0))
Counter({3: 4})
>>> print(nx.generalized_degree(G))
{0: Counter({3: 4}), 1: Counter({3: 4}), 2: Counter({3: 4}), 3: Counter({3: 4}), 4: Counter({3: 4})}
要恢复连接到节点的三角形数量：
>>> k1 = nx.generalized_degree(G, 0)
>>> sum([k * v for k, v in k1.items()]) / 2 == nx.triangles(G, 0)
True
Notes
-----
自环被忽略。
在一个 N 个节点的网络中，一条边可以具有的最高三角形重数是 N-2。
返回值不包括没有特定三角形重数的边的 `zero` 条目。
节点 :math:`i` 连接的三角形数量可以从广义度 :math:`\mathbf{k}_i=(k_i^{(0)}, \dotsc, k_i^{(N-2)})` 恢复为 :math:`(k_i^{(1)}+2k_i^{(2)}+\dotsc +(N-2)k_i^{(N-2)})/2` 。
References
----------
.. [1] V. Zlatić, D. Garlaschelli 和 G. Caldarelli 的“具有任意边重数的网络”，EPL（欧洲物理快报），
第 97 卷，第 2 期（2012 年）。
https://iopscience.iop.org/article/10.1209/0295-5075/97/28005
"""
if nodes in G:
return next(_triangles_and_degree_iter(G, nodes))[3]
return {v: gd for v, d, t, gd in _triangles_and_degree_iter(G, nodes)}
