Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/triads.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
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.""" | |
6 | |
7 from itertools import combinations, permutations | |
8 from collections import defaultdict | |
9 from random import sample | |
10 | |
11 import networkx as nx | |
12 from networkx.utils import not_implemented_for | |
13 | |
14 __all__ = [ | |
15 "triadic_census", | |
16 "is_triad", | |
17 "all_triplets", | |
18 "all_triads", | |
19 "triads_by_type", | |
20 "triad_type", | |
21 "random_triad", | |
22 ] | |
23 | |
24 #: The integer codes representing each type of triad. | |
25 #: | |
26 #: Triads that are the same up to symmetry have the same code. | |
27 TRICODES = ( | |
28 1, | |
29 2, | |
30 2, | |
31 3, | |
32 2, | |
33 4, | |
34 6, | |
35 8, | |
36 2, | |
37 6, | |
38 5, | |
39 7, | |
40 3, | |
41 8, | |
42 7, | |
43 11, | |
44 2, | |
45 6, | |
46 4, | |
47 8, | |
48 5, | |
49 9, | |
50 9, | |
51 13, | |
52 6, | |
53 10, | |
54 9, | |
55 14, | |
56 7, | |
57 14, | |
58 12, | |
59 15, | |
60 2, | |
61 5, | |
62 6, | |
63 7, | |
64 6, | |
65 9, | |
66 10, | |
67 14, | |
68 4, | |
69 9, | |
70 9, | |
71 12, | |
72 8, | |
73 13, | |
74 14, | |
75 15, | |
76 3, | |
77 7, | |
78 8, | |
79 11, | |
80 7, | |
81 12, | |
82 14, | |
83 15, | |
84 8, | |
85 14, | |
86 13, | |
87 15, | |
88 11, | |
89 15, | |
90 15, | |
91 16, | |
92 ) | |
93 | |
94 #: The names of each type of triad. The order of the elements is | |
95 #: important: it corresponds to the tricodes given in :data:`TRICODES`. | |
96 TRIAD_NAMES = ( | |
97 "003", | |
98 "012", | |
99 "102", | |
100 "021D", | |
101 "021U", | |
102 "021C", | |
103 "111D", | |
104 "111U", | |
105 "030T", | |
106 "030C", | |
107 "201", | |
108 "120D", | |
109 "120U", | |
110 "120C", | |
111 "210", | |
112 "300", | |
113 ) | |
114 | |
115 | |
116 #: A dictionary mapping triad code to triad name. | |
117 TRICODE_TO_NAME = {i: TRIAD_NAMES[code - 1] for i, code in enumerate(TRICODES)} | |
118 | |
119 | |
120 def _tricode(G, v, u, w): | |
121 """Returns the integer code of the given triad. | |
122 | |
123 This is some fancy magic that comes from Batagelj and Mrvar's paper. It | |
124 treats each edge joining a pair of `v`, `u`, and `w` as a bit in | |
125 the binary representation of an integer. | |
126 | |
127 """ | |
128 combos = ((v, u, 1), (u, v, 2), (v, w, 4), (w, v, 8), (u, w, 16), (w, u, 32)) | |
129 return sum(x for u, v, x in combos if v in G[u]) | |
130 | |
131 | |
132 @not_implemented_for("undirected") | |
133 def triadic_census(G): | |
134 """Determines the triadic census of a directed graph. | |
135 | |
136 The triadic census is a count of how many of the 16 possible types of | |
137 triads are present in a directed graph. | |
138 | |
139 Parameters | |
140 ---------- | |
141 G : digraph | |
142 A NetworkX DiGraph | |
143 | |
144 Returns | |
145 ------- | |
146 census : dict | |
147 Dictionary with triad type as keys and number of occurrences as values. | |
148 | |
149 Notes | |
150 ----- | |
151 This algorithm has complexity $O(m)$ where $m$ is the number of edges in | |
152 the graph. | |
153 | |
154 See also | |
155 -------- | |
156 triad_graph | |
157 | |
158 References | |
159 ---------- | |
160 .. [1] Vladimir Batagelj and Andrej Mrvar, A subquadratic triad census | |
161 algorithm for large sparse networks with small maximum degree, | |
162 University of Ljubljana, | |
163 http://vlado.fmf.uni-lj.si/pub/networks/doc/triads/triads.pdf | |
164 | |
165 """ | |
166 # Initialize the count for each triad to be zero. | |
167 census = {name: 0 for name in TRIAD_NAMES} | |
168 n = len(G) | |
169 # m = dict(zip(G, range(n))) | |
170 m = {v: i for i, v in enumerate(G)} | |
171 for v in G: | |
172 vnbrs = set(G.pred[v]) | set(G.succ[v]) | |
173 for u in vnbrs: | |
174 if m[u] <= m[v]: | |
175 continue | |
176 neighbors = (vnbrs | set(G.succ[u]) | set(G.pred[u])) - {u, v} | |
177 # Calculate dyadic triads instead of counting them. | |
178 if v in G[u] and u in G[v]: | |
179 census["102"] += n - len(neighbors) - 2 | |
180 else: | |
181 census["012"] += n - len(neighbors) - 2 | |
182 # Count connected triads. | |
183 for w in neighbors: | |
184 if m[u] < m[w] or ( | |
185 m[v] < m[w] < m[u] and v not in G.pred[w] and v not in G.succ[w] | |
186 ): | |
187 code = _tricode(G, v, u, w) | |
188 census[TRICODE_TO_NAME[code]] += 1 | |
189 # null triads = total number of possible triads - all found triads | |
190 # | |
191 # Use integer division here, since we know this formula guarantees an | |
192 # integral value. | |
193 census["003"] = ((n * (n - 1) * (n - 2)) // 6) - sum(census.values()) | |
194 return census | |
195 | |
196 | |
197 def is_triad(G): | |
198 """Returns True if the graph G is a triad, else False. | |
199 | |
200 Parameters | |
201 ---------- | |
202 G : graph | |
203 A NetworkX Graph | |
204 | |
205 Returns | |
206 ------- | |
207 istriad : boolean | |
208 Whether G is a valid triad | |
209 """ | |
210 if isinstance(G, nx.Graph): | |
211 if G.order() == 3 and nx.is_directed(G): | |
212 if not any((n, n) in G.edges() for n in G.nodes()): | |
213 return True | |
214 return False | |
215 | |
216 | |
217 @not_implemented_for("undirected") | |
218 def all_triplets(G): | |
219 """Returns a generator of all possible sets of 3 nodes in a DiGraph. | |
220 | |
221 Parameters | |
222 ---------- | |
223 G : digraph | |
224 A NetworkX DiGraph | |
225 | |
226 Returns | |
227 ------- | |
228 triplets : generator of 3-tuples | |
229 Generator of tuples of 3 nodes | |
230 """ | |
231 triplets = combinations(G.nodes(), 3) | |
232 return triplets | |
233 | |
234 | |
235 @not_implemented_for("undirected") | |
236 def all_triads(G): | |
237 """A generator of all possible triads in G. | |
238 | |
239 Parameters | |
240 ---------- | |
241 G : digraph | |
242 A NetworkX DiGraph | |
243 | |
244 Returns | |
245 ------- | |
246 all_triads : generator of DiGraphs | |
247 Generator of triads (order-3 DiGraphs) | |
248 """ | |
249 triplets = combinations(G.nodes(), 3) | |
250 for triplet in triplets: | |
251 yield G.subgraph(triplet).copy() | |
252 | |
253 | |
254 @not_implemented_for("undirected") | |
255 def triads_by_type(G): | |
256 """Returns a list of all triads for each triad type in a directed graph. | |
257 | |
258 Parameters | |
259 ---------- | |
260 G : digraph | |
261 A NetworkX DiGraph | |
262 | |
263 Returns | |
264 ------- | |
265 tri_by_type : dict | |
266 Dictionary with triad types as keys and lists of triads as values. | |
267 """ | |
268 # num_triads = o * (o - 1) * (o - 2) // 6 | |
269 # if num_triads > TRIAD_LIMIT: print(WARNING) | |
270 all_tri = all_triads(G) | |
271 tri_by_type = defaultdict(list) | |
272 for triad in all_tri: | |
273 name = triad_type(triad) | |
274 tri_by_type[name].append(triad) | |
275 return tri_by_type | |
276 | |
277 | |
278 @not_implemented_for("undirected") | |
279 def triad_type(G): | |
280 """Returns the sociological triad type for a triad. | |
281 | |
282 Parameters | |
283 ---------- | |
284 G : digraph | |
285 A NetworkX DiGraph with 3 nodes | |
286 | |
287 Returns | |
288 ------- | |
289 triad_type : str | |
290 A string identifying the triad type | |
291 | |
292 Notes | |
293 ----- | |
294 There can be 6 unique edges in a triad (order-3 DiGraph) (so 2^^6=64 unique | |
295 triads given 3 nodes). These 64 triads each display exactly 1 of 16 | |
296 topologies of triads (topologies can be permuted). These topologies are | |
297 identified by the following notation: | |
298 | |
299 {m}{a}{n}{type} (for example: 111D, 210, 102) | |
300 | |
301 Here: | |
302 | |
303 {m} = number of mutual ties (takes 0, 1, 2, 3); a mutual tie is (0,1) | |
304 AND (1,0) | |
305 {a} = number of assymmetric ties (takes 0, 1, 2, 3); an assymmetric tie | |
306 is (0,1) BUT NOT (1,0) or vice versa | |
307 {n} = number of null ties (takes 0, 1, 2, 3); a null tie is NEITHER | |
308 (0,1) NOR (1,0) | |
309 {type} = a letter (takes U, D, C, T) corresponding to up, down, cyclical | |
310 and transitive. This is only used for topologies that can have | |
311 more than one form (eg: 021D and 021U). | |
312 | |
313 References | |
314 ---------- | |
315 .. [1] Snijders, T. (2012). "Transitivity and triads." University of | |
316 Oxford. | |
317 http://www.stats.ox.ac.uk/snijders/Trans_Triads_ha.pdf | |
318 """ | |
319 if not is_triad(G): | |
320 raise nx.NetworkXAlgorithmError("G is not a triad (order-3 DiGraph)") | |
321 num_edges = len(G.edges()) | |
322 if num_edges == 0: | |
323 return "003" | |
324 elif num_edges == 1: | |
325 return "012" | |
326 elif num_edges == 2: | |
327 e1, e2 = G.edges() | |
328 if set(e1) == set(e2): | |
329 return "102" | |
330 elif e1[0] == e2[0]: | |
331 return "021D" | |
332 elif e1[1] == e2[1]: | |
333 return "021U" | |
334 elif e1[1] == e2[0] or e2[1] == e1[0]: | |
335 return "021C" | |
336 elif num_edges == 3: | |
337 for (e1, e2, e3) in permutations(G.edges(), 3): | |
338 if set(e1) == set(e2): | |
339 if e3[0] in e1: | |
340 return "111U" | |
341 # e3[1] in e1: | |
342 return "111D" | |
343 elif set(e1).symmetric_difference(set(e2)) == set(e3): | |
344 if {e1[0], e2[0], e3[0]} == {e1[0], e2[0], e3[0]} == set(G.nodes()): | |
345 return "030C" | |
346 # e3 == (e1[0], e2[1]) and e2 == (e1[1], e3[1]): | |
347 return "030T" | |
348 elif num_edges == 4: | |
349 for (e1, e2, e3, e4) in permutations(G.edges(), 4): | |
350 if set(e1) == set(e2): | |
351 # identify pair of symmetric edges (which necessarily exists) | |
352 if set(e3) == set(e4): | |
353 return "201" | |
354 if {e3[0]} == {e4[0]} == set(e3).intersection(set(e4)): | |
355 return "120D" | |
356 if {e3[1]} == {e4[1]} == set(e3).intersection(set(e4)): | |
357 return "120U" | |
358 if e3[1] == e4[0]: | |
359 return "120C" | |
360 elif num_edges == 5: | |
361 return "210" | |
362 elif num_edges == 6: | |
363 return "300" | |
364 | |
365 | |
366 @not_implemented_for("undirected") | |
367 def random_triad(G): | |
368 """Returns a random triad from a directed graph. | |
369 | |
370 Parameters | |
371 ---------- | |
372 G : digraph | |
373 A NetworkX DiGraph | |
374 | |
375 Returns | |
376 ------- | |
377 G2 : subgraph | |
378 A randomly selected triad (order-3 NetworkX DiGraph) | |
379 """ | |
380 nodes = sample(G.nodes(), 3) | |
381 G2 = G.subgraph(nodes) | |
382 return G2 | |
383 | |
384 | |
385 """ | |
386 @not_implemented_for('undirected') | |
387 def triadic_closures(G): | |
388 '''Returns a list of order-3 subgraphs of G that are triadic closures. | |
389 | |
390 Parameters | |
391 ---------- | |
392 G : digraph | |
393 A NetworkX DiGraph | |
394 | |
395 Returns | |
396 ------- | |
397 closures : list | |
398 List of triads of G that are triadic closures | |
399 ''' | |
400 pass | |
401 | |
402 | |
403 @not_implemented_for('undirected') | |
404 def focal_closures(G, attr_name): | |
405 '''Returns a list of order-3 subgraphs of G that are focally closed. | |
406 | |
407 Parameters | |
408 ---------- | |
409 G : digraph | |
410 A NetworkX DiGraph | |
411 attr_name : str | |
412 An attribute name | |
413 | |
414 | |
415 Returns | |
416 ------- | |
417 closures : list | |
418 List of triads of G that are focally closed on attr_name | |
419 ''' | |
420 pass | |
421 | |
422 | |
423 @not_implemented_for('undirected') | |
424 def balanced_triads(G, crit_func): | |
425 '''Returns a list of order-3 subgraphs of G that are stable. | |
426 | |
427 Parameters | |
428 ---------- | |
429 G : digraph | |
430 A NetworkX DiGraph | |
431 crit_func : function | |
432 A function that determines if a triad (order-3 digraph) is stable | |
433 | |
434 Returns | |
435 ------- | |
436 triads : list | |
437 List of triads in G that are stable | |
438 ''' | |
439 pass | |
440 """ |