Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1# See https://github.com/networkx/networkx/pull/1474
2# Copyright 2011 Reya Group <http://www.reyagroup.com>
3# Copyright 2011 Alex Levenson <alex@isnotinvain.com>
4# Copyright 2011 Diederik van Liere <diederik.vanliere@rotman.utoronto.ca>
5"""Functions for analyzing triads of a graph."""
7from collections import defaultdict
8from itertools import combinations, permutations
10import networkx as nx
11from networkx.utils import not_implemented_for, py_random_state
13__all__ = [
14 "triadic_census",
15 "is_triad",
16 "all_triads",
17 "triads_by_type",
18 "triad_type",
19]
21#: The integer codes representing each type of triad.
22#:
23#: Triads that are the same up to symmetry have the same code.
24TRICODES = (
25 1,
26 2,
27 2,
28 3,
29 2,
30 4,
31 6,
32 8,
33 2,
34 6,
35 5,
36 7,
37 3,
38 8,
39 7,
40 11,
41 2,
42 6,
43 4,
44 8,
45 5,
46 9,
47 9,
48 13,
49 6,
50 10,
51 9,
52 14,
53 7,
54 14,
55 12,
56 15,
57 2,
58 5,
59 6,
60 7,
61 6,
62 9,
63 10,
64 14,
65 4,
66 9,
67 9,
68 12,
69 8,
70 13,
71 14,
72 15,
73 3,
74 7,
75 8,
76 11,
77 7,
78 12,
79 14,
80 15,
81 8,
82 14,
83 13,
84 15,
85 11,
86 15,
87 15,
88 16,
89)
91#: The names of each type of triad. The order of the elements is
92#: important: it corresponds to the tricodes given in :data:`TRICODES`.
93TRIAD_NAMES = (
94 "003",
95 "012",
96 "102",
97 "021D",
98 "021U",
99 "021C",
100 "111D",
101 "111U",
102 "030T",
103 "030C",
104 "201",
105 "120D",
106 "120U",
107 "120C",
108 "210",
109 "300",
110)
113#: A dictionary mapping triad code to triad name.
114TRICODE_TO_NAME = {i: TRIAD_NAMES[code - 1] for i, code in enumerate(TRICODES)}
117def _tricode(G, v, u, w):
118 """Returns the integer code of the given triad.
120 This is some fancy magic that comes from Batagelj and Mrvar's paper. It
121 treats each edge joining a pair of `v`, `u`, and `w` as a bit in
122 the binary representation of an integer.
124 """
125 combos = ((v, u, 1), (u, v, 2), (v, w, 4), (w, v, 8), (u, w, 16), (w, u, 32))
126 return sum(x for u, v, x in combos if v in G[u])
129@not_implemented_for("undirected")
130@nx._dispatchable
131def triadic_census(G, nodelist=None):
132 """Determines the triadic census of a directed graph.
134 The triadic census is a count of how many of the 16 possible types of
135 triads are present in a directed graph. If a list of nodes is passed, then
136 only those triads are taken into account which have elements of nodelist in them.
138 Parameters
139 ----------
140 G : digraph
141 A NetworkX DiGraph
142 nodelist : list
143 List of nodes for which you want to calculate triadic census
145 Returns
146 -------
147 census : dict
148 Dictionary with triad type as keys and number of occurrences as values.
150 Examples
151 --------
152 >>> G = nx.DiGraph([(1, 2), (2, 3), (3, 1), (3, 4), (4, 1), (4, 2)])
153 >>> triadic_census = nx.triadic_census(G)
154 >>> for key, value in triadic_census.items():
155 ... print(f"{key}: {value}")
156 003: 0
157 012: 0
158 102: 0
159 021D: 0
160 021U: 0
161 021C: 0
162 111D: 0
163 111U: 0
164 030T: 2
165 030C: 2
166 201: 0
167 120D: 0
168 120U: 0
169 120C: 0
170 210: 0
171 300: 0
173 Notes
174 -----
175 This algorithm has complexity $O(m)$ where $m$ is the number of edges in
176 the graph.
178 For undirected graphs, the triadic census can be computed by first converting
179 the graph into a directed graph using the ``G.to_directed()`` method.
180 After this conversion, only the triad types 003, 102, 201 and 300 will be
181 present in the undirected scenario.
183 Raises
184 ------
185 ValueError
186 If `nodelist` contains duplicate nodes or nodes not in `G`.
187 If you want to ignore this you can preprocess with `set(nodelist) & G.nodes`
189 See also
190 --------
191 triad_graph
193 References
194 ----------
195 .. [1] Vladimir Batagelj and Andrej Mrvar, A subquadratic triad census
196 algorithm for large sparse networks with small maximum degree,
197 University of Ljubljana,
198 http://vlado.fmf.uni-lj.si/pub/networks/doc/triads/triads.pdf
200 """
201 nodeset = set(G.nbunch_iter(nodelist))
202 if nodelist is not None and len(nodelist) != len(nodeset):
203 raise ValueError("nodelist includes duplicate nodes or nodes not in G")
205 N = len(G)
206 Nnot = N - len(nodeset) # can signal special counting for subset of nodes
208 # create an ordering of nodes with nodeset nodes first
209 m = {n: i for i, n in enumerate(nodeset)}
210 if Nnot:
211 # add non-nodeset nodes later in the ordering
212 not_nodeset = G.nodes - nodeset
213 m.update((n, i + N) for i, n in enumerate(not_nodeset))
215 # build all_neighbor dicts for easy counting
216 # After Python 3.8 can leave off these keys(). Speedup also using G._pred
217 # nbrs = {n: G._pred[n].keys() | G._succ[n].keys() for n in G}
218 nbrs = {n: G.pred[n].keys() | G.succ[n].keys() for n in G}
219 dbl_nbrs = {n: G.pred[n].keys() & G.succ[n].keys() for n in G}
221 if Nnot:
222 sgl_nbrs = {n: G.pred[n].keys() ^ G.succ[n].keys() for n in not_nodeset}
223 # find number of edges not incident to nodes in nodeset
224 sgl = sum(1 for n in not_nodeset for nbr in sgl_nbrs[n] if nbr not in nodeset)
225 sgl_edges_outside = sgl // 2
226 dbl = sum(1 for n in not_nodeset for nbr in dbl_nbrs[n] if nbr not in nodeset)
227 dbl_edges_outside = dbl // 2
229 # Initialize the count for each triad to be zero.
230 census = {name: 0 for name in TRIAD_NAMES}
231 # Main loop over nodes
232 for v in nodeset:
233 vnbrs = nbrs[v]
234 dbl_vnbrs = dbl_nbrs[v]
235 if Nnot:
236 # set up counts of edges attached to v.
237 sgl_unbrs_bdy = sgl_unbrs_out = dbl_unbrs_bdy = dbl_unbrs_out = 0
238 for u in vnbrs:
239 if m[u] <= m[v]:
240 continue
241 unbrs = nbrs[u]
242 neighbors = (vnbrs | unbrs) - {u, v}
243 # Count connected triads.
244 for w in neighbors:
245 if m[u] < m[w] or (m[v] < m[w] < m[u] and v not in nbrs[w]):
246 code = _tricode(G, v, u, w)
247 census[TRICODE_TO_NAME[code]] += 1
249 # Use a formula for dyadic triads with edge incident to v
250 if u in dbl_vnbrs:
251 census["102"] += N - len(neighbors) - 2
252 else:
253 census["012"] += N - len(neighbors) - 2
255 # Count edges attached to v. Subtract later to get triads with v isolated
256 # _out are (u,unbr) for unbrs outside boundary of nodeset
257 # _bdy are (u,unbr) for unbrs on boundary of nodeset (get double counted)
258 if Nnot and u not in nodeset:
259 sgl_unbrs = sgl_nbrs[u]
260 sgl_unbrs_bdy += len(sgl_unbrs & vnbrs - nodeset)
261 sgl_unbrs_out += len(sgl_unbrs - vnbrs - nodeset)
262 dbl_unbrs = dbl_nbrs[u]
263 dbl_unbrs_bdy += len(dbl_unbrs & vnbrs - nodeset)
264 dbl_unbrs_out += len(dbl_unbrs - vnbrs - nodeset)
265 # if nodeset == G.nodes, skip this b/c we will find the edge later.
266 if Nnot:
267 # Count edges outside nodeset not connected with v (v isolated triads)
268 census["012"] += sgl_edges_outside - (sgl_unbrs_out + sgl_unbrs_bdy // 2)
269 census["102"] += dbl_edges_outside - (dbl_unbrs_out + dbl_unbrs_bdy // 2)
271 # calculate null triads: "003"
272 # null triads = total number of possible triads - all found triads
273 total_triangles = (N * (N - 1) * (N - 2)) // 6
274 triangles_without_nodeset = (Nnot * (Nnot - 1) * (Nnot - 2)) // 6
275 total_census = total_triangles - triangles_without_nodeset
276 census["003"] = total_census - sum(census.values())
278 return census
281@nx._dispatchable
282def is_triad(G):
283 """Returns True if the graph G is a triad, else False.
285 Parameters
286 ----------
287 G : graph
288 A NetworkX Graph
290 Returns
291 -------
292 istriad : boolean
293 Whether G is a valid triad
295 Examples
296 --------
297 >>> G = nx.DiGraph([(1, 2), (2, 3), (3, 1)])
298 >>> nx.is_triad(G)
299 True
300 >>> G.add_edge(0, 1)
301 >>> nx.is_triad(G)
302 False
303 """
304 if isinstance(G, nx.Graph):
305 if G.order() == 3 and nx.is_directed(G):
306 if not any((n, n) in G.edges() for n in G.nodes()):
307 return True
308 return False
311@not_implemented_for("undirected")
312@nx._dispatchable(returns_graph=True)
313def all_triads(G):
314 """A generator of all possible triads in G.
316 Parameters
317 ----------
318 G : digraph
319 A NetworkX DiGraph
321 Returns
322 -------
323 all_triads : generator of DiGraphs
324 Generator of triads (order-3 DiGraphs)
326 Examples
327 --------
328 >>> G = nx.DiGraph([(1, 2), (2, 3), (3, 1), (3, 4), (4, 1), (4, 2)])
329 >>> for triad in nx.all_triads(G):
330 ... print(triad.edges)
331 [(1, 2), (2, 3), (3, 1)]
332 [(1, 2), (4, 1), (4, 2)]
333 [(3, 1), (3, 4), (4, 1)]
334 [(2, 3), (3, 4), (4, 2)]
336 """
337 triplets = combinations(G.nodes(), 3)
338 for triplet in triplets:
339 yield G.subgraph(triplet).copy()
342@not_implemented_for("undirected")
343@nx._dispatchable
344def triads_by_type(G):
345 """Returns a list of all triads for each triad type in a directed graph.
346 There are exactly 16 different types of triads possible. Suppose 1, 2, 3 are three
347 nodes, they will be classified as a particular triad type if their connections
348 are as follows:
350 - 003: 1, 2, 3
351 - 012: 1 -> 2, 3
352 - 102: 1 <-> 2, 3
353 - 021D: 1 <- 2 -> 3
354 - 021U: 1 -> 2 <- 3
355 - 021C: 1 -> 2 -> 3
356 - 111D: 1 <-> 2 <- 3
357 - 111U: 1 <-> 2 -> 3
358 - 030T: 1 -> 2 -> 3, 1 -> 3
359 - 030C: 1 <- 2 <- 3, 1 -> 3
360 - 201: 1 <-> 2 <-> 3
361 - 120D: 1 <- 2 -> 3, 1 <-> 3
362 - 120U: 1 -> 2 <- 3, 1 <-> 3
363 - 120C: 1 -> 2 -> 3, 1 <-> 3
364 - 210: 1 -> 2 <-> 3, 1 <-> 3
365 - 300: 1 <-> 2 <-> 3, 1 <-> 3
367 Refer to the :doc:`example gallery </auto_examples/graph/plot_triad_types>`
368 for visual examples of the triad types.
370 Parameters
371 ----------
372 G : digraph
373 A NetworkX DiGraph
375 Returns
376 -------
377 tri_by_type : dict
378 Dictionary with triad types as keys and lists of triads as values.
380 Examples
381 --------
382 >>> G = nx.DiGraph([(1, 2), (1, 3), (2, 3), (3, 1), (5, 6), (5, 4), (6, 7)])
383 >>> dict = nx.triads_by_type(G)
384 >>> dict["120C"][0].edges()
385 OutEdgeView([(1, 2), (1, 3), (2, 3), (3, 1)])
386 >>> dict["012"][0].edges()
387 OutEdgeView([(1, 2)])
389 References
390 ----------
391 .. [1] Snijders, T. (2012). "Transitivity and triads." University of
392 Oxford.
393 https://web.archive.org/web/20170830032057/http://www.stats.ox.ac.uk/~snijders/Trans_Triads_ha.pdf
394 """
395 # num_triads = o * (o - 1) * (o - 2) // 6
396 # if num_triads > TRIAD_LIMIT: print(WARNING)
397 all_tri = all_triads(G)
398 tri_by_type = defaultdict(list)
399 for triad in all_tri:
400 name = triad_type(triad)
401 tri_by_type[name].append(triad)
402 return tri_by_type
405@not_implemented_for("undirected")
406@nx._dispatchable
407def triad_type(G):
408 """Returns the sociological triad type for a triad.
410 Parameters
411 ----------
412 G : digraph
413 A NetworkX DiGraph with 3 nodes
415 Returns
416 -------
417 triad_type : str
418 A string identifying the triad type
420 Examples
421 --------
422 >>> G = nx.DiGraph([(1, 2), (2, 3), (3, 1)])
423 >>> nx.triad_type(G)
424 '030C'
425 >>> G.add_edge(1, 3)
426 >>> nx.triad_type(G)
427 '120C'
429 Notes
430 -----
431 There can be 6 unique edges in a triad (order-3 DiGraph) (so 2^^6=64 unique
432 triads given 3 nodes). These 64 triads each display exactly 1 of 16
433 topologies of triads (topologies can be permuted). These topologies are
434 identified by the following notation:
436 {m}{a}{n}{type} (for example: 111D, 210, 102)
438 Here:
440 {m} = number of mutual ties (takes 0, 1, 2, 3); a mutual tie is (0,1)
441 AND (1,0)
442 {a} = number of asymmetric ties (takes 0, 1, 2, 3); an asymmetric tie
443 is (0,1) BUT NOT (1,0) or vice versa
444 {n} = number of null ties (takes 0, 1, 2, 3); a null tie is NEITHER
445 (0,1) NOR (1,0)
446 {type} = a letter (takes U, D, C, T) corresponding to up, down, cyclical
447 and transitive. This is only used for topologies that can have
448 more than one form (eg: 021D and 021U).
450 References
451 ----------
452 .. [1] Snijders, T. (2012). "Transitivity and triads." University of
453 Oxford.
454 https://web.archive.org/web/20170830032057/http://www.stats.ox.ac.uk/~snijders/Trans_Triads_ha.pdf
455 """
456 if not is_triad(G):
457 raise nx.NetworkXAlgorithmError("G is not a triad (order-3 DiGraph)")
458 num_edges = len(G.edges())
459 if num_edges == 0:
460 return "003"
461 elif num_edges == 1:
462 return "012"
463 elif num_edges == 2:
464 e1, e2 = G.edges()
465 if set(e1) == set(e2):
466 return "102"
467 elif e1[0] == e2[0]:
468 return "021D"
469 elif e1[1] == e2[1]:
470 return "021U"
471 elif e1[1] == e2[0] or e2[1] == e1[0]:
472 return "021C"
473 elif num_edges == 3:
474 for e1, e2, e3 in permutations(G.edges(), 3):
475 if set(e1) == set(e2):
476 if e3[0] in e1:
477 return "111U"
478 # e3[1] in e1:
479 return "111D"
480 elif set(e1).symmetric_difference(set(e2)) == set(e3):
481 if {e1[0], e2[0], e3[0]} == {e1[0], e2[0], e3[0]} == set(G.nodes()):
482 return "030C"
483 # e3 == (e1[0], e2[1]) and e2 == (e1[1], e3[1]):
484 return "030T"
485 elif num_edges == 4:
486 for e1, e2, e3, e4 in permutations(G.edges(), 4):
487 if set(e1) == set(e2):
488 # identify pair of symmetric edges (which necessarily exists)
489 if set(e3) == set(e4):
490 return "201"
491 if {e3[0]} == {e4[0]} == set(e3).intersection(set(e4)):
492 return "120D"
493 if {e3[1]} == {e4[1]} == set(e3).intersection(set(e4)):
494 return "120U"
495 if e3[1] == e4[0]:
496 return "120C"
497 elif num_edges == 5:
498 return "210"
499 elif num_edges == 6:
500 return "300"