# See https://github.com/networkx/networkx/pull/1474
# Copyright 2011 Reya Group <http://www.reyagroup.com>
# Copyright 2011 Alex Levenson <alex@isnotinvain.com>
# Copyright 2011 Diederik van Liere <diederik.vanliere@rotman.utoronto.ca>
"""用于分析图的三元组的函数。"""
from collections import defaultdict
from itertools import combinations, permutations
import networkx as nx
from networkx.utils import not_implemented_for, py_random_state
__all__ = [
"triadic_census",
"is_triad",
"all_triplets",
"all_triads",
"triads_by_type",
"triad_type",
"random_triad",
]
#: The integer codes representing each type of triad.
#:
#: Triads that are the same up to symmetry have the same code.
TRICODES = (
1,
2,
2,
3,
2,
4,
6,
8,
2,
6,
5,
7,
3,
8,
7,
11,
2,
6,
4,
8,
5,
9,
9,
13,
6,
10,
9,
14,
7,
14,
12,
15,
2,
5,
6,
7,
6,
9,
10,
14,
4,
9,
9,
12,
8,
13,
14,
15,
3,
7,
8,
11,
7,
12,
14,
15,
8,
14,
13,
15,
11,
15,
15,
16,
)
#: The names of each type of triad. The order of the elements is
#: important: it corresponds to the tricodes given in :data:`TRICODES`.
TRIAD_NAMES = (
"003",
"012",
"102",
"021D",
"021U",
"021C",
"111D",
"111U",
"030T",
"030C",
"201",
"120D",
"120U",
"120C",
"210",
"300",
)
#: A dictionary mapping triad code to triad name.
TRICODE_TO_NAME = {i: TRIAD_NAMES[code - 1] for i, code in enumerate(TRICODES)}
def _tricode(G, v, u, w):
"""返回给定三元组的整数码。
这是来自Batagelj和Mrvar论文中的一些巧妙魔法。它将连接 `v` 、 `u` 和 `w` 每对顶点的边视为一个整数的二进制表示中的一个位。
"""
combos = ((v, u, 1), (u, v, 2), (v, w, 4), (w, v, 8), (u, w, 16), (w, u, 32))
return sum(x for u, v, x in combos if v in G[u])
[docs]
@not_implemented_for("undirected")
@nx._dispatchable
def triadic_census(G, nodelist=None):
"""确定有向图的三元组普查。
三元组普查是计算有向图中存在的16种可能的三元组类型的数量。如果传递了一个节点列表，则只考虑包含节点列表元素的三元组。
Parameters
----------
G : 有向图
一个NetworkX有向图
nodelist : 列表
要计算三元组普查的节点列表
Returns
-------
census : 字典
以三元组类型为键，出现次数为值的字典。
Examples
--------
>>> G = nx.DiGraph([(1, 2), (2, 3), (3, 1), (3, 4), (4, 1), (4, 2)])
>>> triadic_census = nx.triadic_census(G)
>>> for key, value in triadic_census.items():
... print(f"{key}: {value}")
003: 0
012: 0
102: 0
021D: 0
021U: 0
021C: 0
111D: 0
111U: 0
030T: 2
030C: 2
201: 0
120D: 0
120U: 0
120C: 0
210: 0
300: 0
Notes
-----
该算法的时间复杂度为$O(m)$，其中$m$是图中的边数。
对于无向图，可以通过首先使用 ``G.to_directed()`` 方法将有向图转换为无向图来计算三元组普查。转换后，只有三元组类型003、102、201和300会出现在无向图中。
Raises
------
ValueError
如果 `nodelist` 包含重复节点或不在 `G` 中的节点。
如果想要忽略这一点，可以预处理为 `set(nodelist) & G.nodes`
See Also
--------
triad_graph
References
----------
.. [1] Vladimir Batagelj和Andrej Mrvar，一种适用于具有小最大度的大稀疏网络的次二次三元组普查算法，
卢布尔雅那大学，
http://vlado.fmf.uni-lj.si/pub/networks/doc/triads/triads.pdf
"""
nodeset = set(G.nbunch_iter(nodelist))
if nodelist is not None and len(nodelist) != len(nodeset):
raise ValueError("nodelist includes duplicate nodes or nodes not in G")
N = len(G)
Nnot = N - len(nodeset) # can signal special counting for subset of nodes
# create an ordering of nodes with nodeset nodes first
m = {n: i for i, n in enumerate(nodeset)}
if Nnot:
# add non-nodeset nodes later in the ordering
not_nodeset = G.nodes - nodeset
m.update((n, i + N) for i, n in enumerate(not_nodeset))
# build all_neighbor dicts for easy counting
# After Python 3.8 can leave off these keys(). Speedup also using G._pred
# nbrs = {n: G._pred[n].keys() | G._succ[n].keys() for n in G}
nbrs = {n: G.pred[n].keys() | G.succ[n].keys() for n in G}
dbl_nbrs = {n: G.pred[n].keys() & G.succ[n].keys() for n in G}
if Nnot:
sgl_nbrs = {n: G.pred[n].keys() ^ G.succ[n].keys() for n in not_nodeset}
# find number of edges not incident to nodes in nodeset
sgl = sum(1 for n in not_nodeset for nbr in sgl_nbrs[n] if nbr not in nodeset)
sgl_edges_outside = sgl // 2
dbl = sum(1 for n in not_nodeset for nbr in dbl_nbrs[n] if nbr not in nodeset)
dbl_edges_outside = dbl // 2
# Initialize the count for each triad to be zero.
census = {name: 0 for name in TRIAD_NAMES}
# Main loop over nodes
for v in nodeset:
vnbrs = nbrs[v]
dbl_vnbrs = dbl_nbrs[v]
if Nnot:
# set up counts of edges attached to v.
sgl_unbrs_bdy = sgl_unbrs_out = dbl_unbrs_bdy = dbl_unbrs_out = 0
for u in vnbrs:
if m[u] <= m[v]:
continue
unbrs = nbrs[u]
neighbors = (vnbrs | unbrs) - {u, v}
# Count connected triads.
for w in neighbors:
if m[u] < m[w] or (m[v] < m[w] < m[u] and v not in nbrs[w]):
code = _tricode(G, v, u, w)
census[TRICODE_TO_NAME[code]] += 1
# Use a formula for dyadic triads with edge incident to v
if u in dbl_vnbrs:
census["102"] += N - len(neighbors) - 2
else:
census["012"] += N - len(neighbors) - 2
# Count edges attached to v. Subtract later to get triads with v isolated
# _out are (u,unbr) for unbrs outside boundary of nodeset
# _bdy are (u,unbr) for unbrs on boundary of nodeset (get double counted)
if Nnot and u not in nodeset:
sgl_unbrs = sgl_nbrs[u]
sgl_unbrs_bdy += len(sgl_unbrs & vnbrs - nodeset)
sgl_unbrs_out += len(sgl_unbrs - vnbrs - nodeset)
dbl_unbrs = dbl_nbrs[u]
dbl_unbrs_bdy += len(dbl_unbrs & vnbrs - nodeset)
dbl_unbrs_out += len(dbl_unbrs - vnbrs - nodeset)
# if nodeset == G.nodes, skip this b/c we will find the edge later.
if Nnot:
# Count edges outside nodeset not connected with v (v isolated triads)
census["012"] += sgl_edges_outside - (sgl_unbrs_out + sgl_unbrs_bdy // 2)
census["102"] += dbl_edges_outside - (dbl_unbrs_out + dbl_unbrs_bdy // 2)
# calculate null triads: "003"
# null triads = total number of possible triads - all found triads
total_triangles = (N * (N - 1) * (N - 2)) // 6
triangles_without_nodeset = (Nnot * (Nnot - 1) * (Nnot - 2)) // 6
total_census = total_triangles - triangles_without_nodeset
census["003"] = total_census - sum(census.values())
return census
[docs]
@nx._dispatchable
def is_triad(G):
"""返回 True 如果图 G 是一个三元组，否则返回 False。
Parameters
----------
G : 图
一个 NetworkX 图
Returns
-------
istriad : 布尔值
G 是否是一个有效的三元组
Examples
--------
>>> G = nx.DiGraph([(1, 2), (2, 3), (3, 1)])
>>> nx.is_triad(G)
True
>>> G.add_edge(0, 1)
>>> nx.is_triad(G)
False
"""
if isinstance(G, nx.Graph):
if G.order() == 3 and nx.is_directed(G):
if not any((n, n) in G.edges() for n in G.nodes()):
return True
return False
[docs]
@not_implemented_for("undirected")
@nx._dispatchable
def all_triplets(G):
"""返回一个生成器，包含DiGraph中所有可能的三节点组合。
.. deprecated:: 3.3
all_triplets已弃用，将在NetworkX版本3.5中移除。请改用 `itertools.combinations` ::
all_triplets = itertools.combinations(G, 3)
Parameters
----------
G : 有向图
NetworkX有向图
Returns
-------
triplets : 3元组的生成器
包含3个节点的元组的生成器
Examples
--------
>>> G = nx.DiGraph([(1, 2), (2, 3), (3, 4)])
>>> list(nx.all_triplets(G))
[(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]
"""
import warnings
warnings.warn(
(
"\n\nall_triplets is deprecated and will be removed in v3.5.\n"
"Use `itertools.combinations(G, 3)` instead."
),
category=DeprecationWarning,
stacklevel=4,
)
triplets = combinations(G.nodes(), 3)
return triplets
[docs]
@not_implemented_for("undirected")
@nx._dispatchable(returns_graph=True)
def all_triads(G):
"""G中所有可能的三元组的生成器。
Parameters
----------
G : 有向图
一个NetworkX有向图
Returns
-------
all_triads : 有向图生成器
三元组（三阶有向图）的生成器
Examples
--------
>>> G = nx.DiGraph([(1, 2), (2, 3), (3, 1), (3, 4), (4, 1), (4, 2)])
>>> for triad in nx.all_triads(G):
... print(triad.edges)
[(1, 2), (2, 3), (3, 1)]
[(1, 2), (4, 1), (4, 2)]
[(3, 1), (3, 4), (4, 1)]
[(2, 3), (3, 4), (4, 2)]
"""
triplets = combinations(G.nodes(), 3)
for triplet in triplets:
yield G.subgraph(triplet).copy()
[docs]
@not_implemented_for("undirected")
@nx._dispatchable
def triads_by_type(G):
"""返回有向图中每种三元组类型的所有三元组列表。
共有16种不同的三元组类型。假设1、2、3是三个节点，如果它们的连接方式如下，则它们将被归类为特定的三元组类型：
- 003: 1, 2, 3
- 012: 1 -> 2, 3
- 102: 1 <-> 2, 3
- 021D: 1 <- 2 -> 3
- 021U: 1 -> 2 <- 3
- 021C: 1 -> 2 -> 3
- 111D: 1 <-> 2 <- 3
- 111U: 1 <-> 2 -> 3
- 030T: 1 -> 2 -> 3, 1 -> 3
- 030C: 1 <- 2 <- 3, 1 -> 3
- 201: 1 <-> 2 <-> 3
- 120D: 1 <- 2 -> 3, 1 <-> 3
- 120U: 1 -> 2 <- 3, 1 <-> 3
- 120C: 1 -> 2 -> 3, 1 <-> 3
- 210: 1 -> 2 <-> 3, 1 <-> 3
- 300: 1 <-> 2 <-> 3, 1 <-> 3
有关三元组类型的可视化示例，请参阅 :doc:`示例图库 </auto_examples/graph/plot_triad_types>` 。
Parameters
----------
G : 有向图
一个NetworkX有向图
Returns
-------
tri_by_type : 字典
以三元组类型为键，以三元组列表为值的字典。
Examples
--------
>>> G = nx.DiGraph([(1, 2), (1, 3), (2, 3), (3, 1), (5, 6), (5, 4), (6, 7)])
>>> dict = nx.triads_by_type(G)
>>> dict["120C"][0].edges()
OutEdgeView([(1, 2), (1, 3), (2, 3), (3, 1)])
>>> dict["012"][0].edges()
OutEdgeView([(1, 2)])
References
----------
.. [1] Snijders, T. (2012). "Transitivity and triads." University of
Oxford.
https://web.archive.org/web/20170830032057/http://www.stats.ox.ac.uk/~snijders/Trans_Triads_ha.pdf
"""
# num_triads = o * (o - 1) * (o - 2) // 6
# if num_triads > TRIAD_LIMIT: print(WARNING)
all_tri = all_triads(G)
tri_by_type = defaultdict(list)
for triad in all_tri:
name = triad_type(triad)
tri_by_type[name].append(triad)
return tri_by_type
[docs]
@not_implemented_for("undirected")
@nx._dispatchable
def triad_type(G):
"""返回一个三元组的社会学三元类型。
Parameters
----------
G : 有向图
一个包含3个节点的NetworkX有向图
Returns
-------
triad_type : str
一个字符串，标识三元类型
Examples
--------
>>> G = nx.DiGraph([(1, 2), (2, 3), (3, 1)])
>>> nx.triad_type(G)
'030C'
>>> G.add_edge(1, 3)
>>> nx.triad_type(G)
'120C'
Notes
-----
一个三元组（3个节点的有向图）中可以有6条独特的边（因此给定3个节点，有2^6=64种独特的三元组）。这64种三元组各自恰好展示16种三元组拓扑结构中的一种（拓扑结构可以排列）。这些拓扑结构用以下符号标识：
{m}{a}{n}{type}（例如：111D, 210, 102）
其中：
{m} = 互惠边的数量（取值0, 1, 2, 3）；互惠边是(0,1)和(1,0)
{a} = 非对称边的数量（取值0, 1, 2, 3）；非对称边是(0,1)但不是(1,0)或反之
{n} = 空边的数量（取值0, 1, 2, 3）；空边既不是(0,1)也不是(1,0)
{type} = 一个字母（取值U, D, C, T），对应向上、向下、循环和传递。这仅用于可以有多种形式（例如：021D和021U）的拓扑结构。
References
----------
.. [1] Snijders, T. (2012). "Transitivity and triads." University of
Oxford.
https://web.archive.org/web/20170830032057/http://www.stats.ox.ac.uk/~snijders/Trans_Triads_ha.pdf
"""
if not is_triad(G):
raise nx.NetworkXAlgorithmError("G is not a triad (order-3 DiGraph)")
num_edges = len(G.edges())
if num_edges == 0:
return "003"
elif num_edges == 1:
return "012"
elif num_edges == 2:
e1, e2 = G.edges()
if set(e1) == set(e2):
return "102"
elif e1[0] == e2[0]:
return "021D"
elif e1[1] == e2[1]:
return "021U"
elif e1[1] == e2[0] or e2[1] == e1[0]:
return "021C"
elif num_edges == 3:
for e1, e2, e3 in permutations(G.edges(), 3):
if set(e1) == set(e2):
if e3[0] in e1:
return "111U"
# e3[1] in e1:
return "111D"
elif set(e1).symmetric_difference(set(e2)) == set(e3):
if {e1[0], e2[0], e3[0]} == {e1[0], e2[0], e3[0]} == set(G.nodes()):
return "030C"
# e3 == (e1[0], e2[1]) and e2 == (e1[1], e3[1]):
return "030T"
elif num_edges == 4:
for e1, e2, e3, e4 in permutations(G.edges(), 4):
if set(e1) == set(e2):
# identify pair of symmetric edges (which necessarily exists)
if set(e3) == set(e4):
return "201"
if {e3[0]} == {e4[0]} == set(e3).intersection(set(e4)):
return "120D"
if {e3[1]} == {e4[1]} == set(e3).intersection(set(e4)):
return "120U"
if e3[1] == e4[0]:
return "120C"
elif num_edges == 5:
return "210"
elif num_edges == 6:
return "300"
[docs]
@not_implemented_for("undirected")
@py_random_state(1)
@nx._dispatchable(preserve_all_attrs=True, returns_graph=True)
def random_triad(G, seed=None):
"""从有向图中返回一个随机的三元组。
.. deprecated:: 3.3
random_triad 已弃用，并将在版本 3.5 中移除。
请直接使用随机采样代替::
G.subgraph(random.sample(list(G), 3))
Parameters
----------
G : 有向图
NetworkX 有向图
seed : 整数, random_state, 或 None (默认)
随机数生成状态的指示器。
参见 :ref:`随机性<randomness>` 。
Returns
-------
G2 : 子图
一个随机选择的三元组（3 阶 NetworkX 有向图）
Raises
------
NetworkXError
如果输入图的节点数少于 3 个。
Examples
--------
>>> G = nx.DiGraph([(1, 2), (1, 3), (2, 3), (3, 1), (5, 6), (5, 4), (6, 7)])
>>> triad = nx.random_triad(G, seed=1)
>>> triad.edges
OutEdgeView([(1, 2)])
"""
import warnings
warnings.warn(
(
"\n\nrandom_triad is deprecated and will be removed in NetworkX v3.5.\n"
"Use random.sample instead, e.g.::\n\n"
"\tG.subgraph(random.sample(list(G), 3))\n"
),
category=DeprecationWarning,
stacklevel=5,
)
if len(G) < 3:
raise nx.NetworkXError(
f"G needs at least 3 nodes to form a triad; (it has {len(G)} nodes)"
)
nodes = seed.sample(list(G.nodes()), 3)
G2 = G.subgraph(nodes)
return G2
