Mercurial > repos > shellac > sam_consensus_v3

comparison env/lib/python3.9/site-packages/networkx/generators/joint_degree_seq.py @ 0:4f3585e2f14b draft default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"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 """Generate graphs with a given joint degree and directed joint degree"""
2
3 import networkx as nx
4 from networkx.utils import py_random_state
5
6 __all__ = [
7 "is_valid_joint_degree",
8 "is_valid_directed_joint_degree",
9 "joint_degree_graph",
10 "directed_joint_degree_graph",
11 ]
12
13
14 def is_valid_joint_degree(joint_degrees):
15 """ Checks whether the given joint degree dictionary is realizable.
16
17 A *joint degree dictionary* is a dictionary of dictionaries, in
18 which entry ``joint_degrees[k][l]`` is an integer representing the
19 number of edges joining nodes of degree *k* with nodes of degree
20 *l*. Such a dictionary is realizable as a simple graph if and only
21 if the following conditions are satisfied.
22
23 - each entry must be an integer,
24 - the total number of nodes of degree *k*, computed by
25 ``sum(joint_degrees[k].values()) / k``, must be an integer,
26 - the total number of edges joining nodes of degree *k* with
27 nodes of degree *l* cannot exceed the total number of possible edges,
28 - each diagonal entry ``joint_degrees[k][k]`` must be even (this is
29 a convention assumed by the :func:`joint_degree_graph` function).
30
31
32 Parameters
33 ----------
34 joint_degrees : dictionary of dictionary of integers
35 A joint degree dictionary in which entry ``joint_degrees[k][l]``
36 is the number of edges joining nodes of degree *k* with nodes of
37 degree *l*.
38
39 Returns
40 -------
41 bool
42 Whether the given joint degree dictionary is realizable as a
43 simple graph.
44
45 References
46 ----------
47 .. [1] M. Gjoka, M. Kurant, A. Markopoulou, "2.5K Graphs: from Sampling
48 to Generation", IEEE Infocom, 2013.
49 .. [2] I. Stanton, A. Pinar, "Constructing and sampling graphs with a
50 prescribed joint degree distribution", Journal of Experimental
51 Algorithmics, 2012.
52 """
53
54 degree_count = {}
55 for k in joint_degrees:
56 if k > 0:
57 k_size = sum(joint_degrees[k].values()) / k
58 if not k_size.is_integer():
59 return False
60 degree_count[k] = k_size
61
62 for k in joint_degrees:
63 for l in joint_degrees[k]:
64 if not float(joint_degrees[k][l]).is_integer():
65 return False
66
67 if (k != l) and (joint_degrees[k][l] > degree_count[k] * degree_count[l]):
68 return False
69 elif k == l:
70 if joint_degrees[k][k] > degree_count[k] * (degree_count[k] - 1):
71 return False
72 if joint_degrees[k][k] % 2 != 0:
73 return False
74
75 # if all above conditions have been satisfied then the input
76 # joint degree is realizable as a simple graph.
77 return True
78
79
80 def _neighbor_switch(G, w, unsat, h_node_residual, avoid_node_id=None):
81 """ Releases one free stub for ``w``, while preserving joint degree in G.
82
83 Parameters
84 ----------
85 G : NetworkX graph
86 Graph in which the neighbor switch will take place.
87 w : integer
88 Node id for which we will execute this neighbor switch.
89 unsat : set of integers
90 Set of unsaturated node ids that have the same degree as w.
91 h_node_residual: dictionary of integers
92 Keeps track of the remaining stubs for a given node.
93 avoid_node_id: integer
94 Node id to avoid when selecting w_prime.
95
96 Notes
97 -----
98 First, it selects *w_prime*, an unsaturated node that has the same degree
99 as ``w``. Second, it selects *switch_node*, a neighbor node of ``w`` that
100 is not connected to *w_prime*. Then it executes an edge swap i.e. removes
101 (``w``,*switch_node*) and adds (*w_prime*,*switch_node*). Gjoka et. al. [1]
102 prove that such an edge swap is always possible.
103
104 References
105 ----------
106 .. [1] M. Gjoka, B. Tillman, A. Markopoulou, "Construction of Simple
107 Graphs with a Target Joint Degree Matrix and Beyond", IEEE Infocom, '15
108 """
109
110 if (avoid_node_id is None) or (h_node_residual[avoid_node_id] > 1):
111 # select unsatured node w_prime that has the same degree as w
112 w_prime = next(iter(unsat))
113 else:
114 # assume that the node pair (v,w) has been selected for connection. if
115 # - neighbor_switch is called for node w,
116 # - nodes v and w have the same degree,
117 # - node v=avoid_node_id has only one stub left,
118 # then prevent v=avoid_node_id from being selected as w_prime.
119
120 iter_var = iter(unsat)
121 while True:
122 w_prime = next(iter_var)
123 if w_prime != avoid_node_id:
124 break
125
126 # select switch_node, a neighbor of w, that is not connected to w_prime
127 w_prime_neighbs = G[w_prime] # slightly faster declaring this variable
128 for v in G[w]:
129 if (v not in w_prime_neighbs) and (v != w_prime):
130 switch_node = v
131 break
132
133 # remove edge (w,switch_node), add edge (w_prime,switch_node) and update
134 # data structures
135 G.remove_edge(w, switch_node)
136 G.add_edge(w_prime, switch_node)
137 h_node_residual[w] += 1
138 h_node_residual[w_prime] -= 1
139 if h_node_residual[w_prime] == 0:
140 unsat.remove(w_prime)
141
142
143 @py_random_state(1)
144 def joint_degree_graph(joint_degrees, seed=None):
145 """ Generates a random simple graph with the given joint degree dictionary.
146
147 Parameters
148 ----------
149 joint_degrees : dictionary of dictionary of integers
150 A joint degree dictionary in which entry ``joint_degrees[k][l]`` is the
151 number of edges joining nodes of degree *k* with nodes of degree *l*.
152 seed : integer, random_state, or None (default)
153 Indicator of random number generation state.
154 See :ref:`Randomness<randomness>`.
155
156 Returns
157 -------
158 G : Graph
159 A graph with the specified joint degree dictionary.
160
161 Raises
162 ------
163 NetworkXError
164 If *joint_degrees* dictionary is not realizable.
165
166 Notes
167 -----
168 In each iteration of the "while loop" the algorithm picks two disconnected
169 nodes *v* and *w*, of degree *k* and *l* correspondingly, for which
170 ``joint_degrees[k][l]`` has not reached its target yet. It then adds
171 edge (*v*, *w*) and increases the number of edges in graph G by one.
172
173 The intelligence of the algorithm lies in the fact that it is always
174 possible to add an edge between such disconnected nodes *v* and *w*,
175 even if one or both nodes do not have free stubs. That is made possible by
176 executing a "neighbor switch", an edge rewiring move that releases
177 a free stub while keeping the joint degree of G the same.
178
179 The algorithm continues for E (number of edges) iterations of
180 the "while loop", at the which point all entries of the given
181 ``joint_degrees[k][l]`` have reached their target values and the
182 construction is complete.
183
184 References
185 ----------
186 .. [1] M. Gjoka, B. Tillman, A. Markopoulou, "Construction of Simple
187 Graphs with a Target Joint Degree Matrix and Beyond", IEEE Infocom, '15
188
189 Examples
190 --------
191 >>> joint_degrees = {
192 ... 1: {4: 1},
193 ... 2: {2: 2, 3: 2, 4: 2},
194 ... 3: {2: 2, 4: 1},
195 ... 4: {1: 1, 2: 2, 3: 1},
196 ... }
197 >>> G = nx.joint_degree_graph(joint_degrees)
198 >>>
199 """
200
201 if not is_valid_joint_degree(joint_degrees):
202 msg = "Input joint degree dict not realizable as a simple graph"
203 raise nx.NetworkXError(msg)
204
205 # compute degree count from joint_degrees
206 degree_count = {k: sum(l.values()) // k for k, l in joint_degrees.items() if k > 0}
207
208 # start with empty N-node graph
209 N = sum(degree_count.values())
210 G = nx.empty_graph(N)
211
212 # for a given degree group, keep the list of all node ids
213 h_degree_nodelist = {}
214
215 # for a given node, keep track of the remaining stubs
216 h_node_residual = {}
217
218 # populate h_degree_nodelist and h_node_residual
219 nodeid = 0
220 for degree, num_nodes in degree_count.items():
221 h_degree_nodelist[degree] = range(nodeid, nodeid + num_nodes)
222 for v in h_degree_nodelist[degree]:
223 h_node_residual[v] = degree
224 nodeid += int(num_nodes)
225
226 # iterate over every degree pair (k,l) and add the number of edges given
227 # for each pair
228 for k in joint_degrees:
229 for l in joint_degrees[k]:
230
231 # n_edges_add is the number of edges to add for the
232 # degree pair (k,l)
233 n_edges_add = joint_degrees[k][l]
234
235 if (n_edges_add > 0) and (k >= l):
236
237 # number of nodes with degree k and l
238 k_size = degree_count[k]
239 l_size = degree_count[l]
240
241 # k_nodes and l_nodes consist of all nodes of degree k and l
242 k_nodes = h_degree_nodelist[k]
243 l_nodes = h_degree_nodelist[l]
244
245 # k_unsat and l_unsat consist of nodes of degree k and l that
246 # are unsaturated (nodes that have at least 1 available stub)
247 k_unsat = {v for v in k_nodes if h_node_residual[v] > 0}
248
249 if k != l:
250 l_unsat = {w for w in l_nodes if h_node_residual[w] > 0}
251 else:
252 l_unsat = k_unsat
253 n_edges_add = joint_degrees[k][l] // 2
254
255 while n_edges_add > 0:
256
257 # randomly pick nodes v and w that have degrees k and l
258 v = k_nodes[seed.randrange(k_size)]
259 w = l_nodes[seed.randrange(l_size)]
260
261 # if nodes v and w are disconnected then attempt to connect
262 if not G.has_edge(v, w) and (v != w):
263
264 # if node v has no free stubs then do neighbor switch
265 if h_node_residual[v] == 0:
266 _neighbor_switch(G, v, k_unsat, h_node_residual)
267
268 # if node w has no free stubs then do neighbor switch
269 if h_node_residual[w] == 0:
270 if k != l:
271 _neighbor_switch(G, w, l_unsat, h_node_residual)
272 else:
273 _neighbor_switch(
274 G, w, l_unsat, h_node_residual, avoid_node_id=v
275 )
276
277 # add edge (v, w) and update data structures
278 G.add_edge(v, w)
279 h_node_residual[v] -= 1
280 h_node_residual[w] -= 1
281 n_edges_add -= 1
282
283 if h_node_residual[v] == 0:
284 k_unsat.discard(v)
285 if h_node_residual[w] == 0:
286 l_unsat.discard(w)
287 return G
288
289
290 def is_valid_directed_joint_degree(in_degrees, out_degrees, nkk):
291 """ Checks whether the given directed joint degree input is realizable
292
293 Parameters
294 ----------
295 in_degrees : list of integers
296 in degree sequence contains the in degrees of nodes.
297 out_degrees : list of integers
298 out degree sequence contains the out degrees of nodes.
299 nkk : dictionary of dictionary of integers
300 directed joint degree dictionary. for nodes of out degree k (first
301 level of dict) and nodes of in degree l (seconnd level of dict)
302 describes the number of edges.
303
304 Returns
305 -------
306 boolean
307 returns true if given input is realizable, else returns false.
308
309 Notes
310 -----
311 Here is the list of conditions that the inputs (in/out degree sequences,
312 nkk) need to satisfy for simple directed graph realizability:
313
314 - Condition 0: in_degrees and out_degrees have the same length
315 - Condition 1: nkk[k][l] is integer for all k,l
316 - Condition 2: sum(nkk[k])/k = number of nodes with partition id k, is an
317 integer and matching degree sequence
318 - Condition 3: number of edges and non-chords between k and l cannot exceed
319 maximum possible number of edges
320
321
322 References
323 ----------
324 [1] B. Tillman, A. Markopoulou, C. T. Butts & M. Gjoka,
325 "Construction of Directed 2K Graphs". In Proc. of KDD 2017.
326 """
327 V = {} # number of nodes with in/out degree.
328 forbidden = {}
329 if len(in_degrees) != len(out_degrees):
330 return False
331
332 for idx in range(0, len(in_degrees)):
333 i = in_degrees[idx]
334 o = out_degrees[idx]
335 V[(i, 0)] = V.get((i, 0), 0) + 1
336 V[(o, 1)] = V.get((o, 1), 0) + 1
337
338 forbidden[(o, i)] = forbidden.get((o, i), 0) + 1
339
340 S = {} # number of edges going from in/out degree nodes.
341 for k in nkk:
342 for l in nkk[k]:
343 val = nkk[k][l]
344 if not float(val).is_integer(): # condition 1
345 return False
346
347 if val > 0:
348 S[(k, 1)] = S.get((k, 1), 0) + val
349 S[(l, 0)] = S.get((l, 0), 0) + val
350 # condition 3
351 if val + forbidden.get((k, l), 0) > V[(k, 1)] * V[(l, 0)]:
352 return False
353
354 for s in S:
355 if not float(S[s]) / s[0] == V[s]: # condition 2
356 return False
357
358 # if all conditions abive have been satisfied then the input nkk is
359 # realizable as a simple graph.
360 return True
361
362
363 def _directed_neighbor_switch(
364 G, w, unsat, h_node_residual_out, chords, h_partition_in, partition
365 ):
366 """ Releases one free stub for node w, while preserving joint degree in G.
367
368 Parameters
369 ----------
370 G : networkx directed graph
371 graph within which the edge swap will take place.
372 w : integer
373 node id for which we need to perform a neighbor switch.
374 unsat: set of integers
375 set of node ids that have the same degree as w and are unsaturated.
376 h_node_residual_out: dict of integers
377 for a given node, keeps track of the remaining stubs to be added.
378 chords: set of tuples
379 keeps track of available positions to add edges.
380 h_partition_in: dict of integers
381 for a given node, keeps track of its partition id (in degree).
382 partition: integer
383 partition id to check if chords have to be updated.
384
385 Notes
386 -----
387 First, it selects node w_prime that (1) has the same degree as w and
388 (2) is unsaturated. Then, it selects node v, a neighbor of w, that is
389 not connected to w_prime and does an edge swap i.e. removes (w,v) and
390 adds (w_prime,v). If neighbor switch is not possible for w using
391 w_prime and v, then return w_prime; in [1] it's proven that
392 such unsaturated nodes can be used.
393
394 References
395 ----------
396 [1] B. Tillman, A. Markopoulou, C. T. Butts & M. Gjoka,
397 "Construction of Directed 2K Graphs". In Proc. of KDD 2017.
398 """
399 w_prime = unsat.pop()
400 unsat.add(w_prime)
401 # select node t, a neighbor of w, that is not connected to w_prime
402 w_neighbs = list(G.successors(w))
403 # slightly faster declaring this variable
404 w_prime_neighbs = list(G.successors(w_prime))
405
406 for v in w_neighbs:
407 if (v not in w_prime_neighbs) and w_prime != v:
408 # removes (w,v), add (w_prime,v) and update data structures
409 G.remove_edge(w, v)
410 G.add_edge(w_prime, v)
411
412 if h_partition_in[v] == partition:
413 chords.add((w, v))
414 chords.discard((w_prime, v))
415
416 h_node_residual_out[w] += 1
417 h_node_residual_out[w_prime] -= 1
418 if h_node_residual_out[w_prime] == 0:
419 unsat.remove(w_prime)
420 return None
421
422 # If neighbor switch didn't work, use unsaturated node
423 return w_prime
424
425
426 def _directed_neighbor_switch_rev(
427 G, w, unsat, h_node_residual_in, chords, h_partition_out, partition
428 ):
429 """ The reverse of directed_neighbor_switch.
430
431 Parameters
432 ----------
433 G : networkx directed graph
434 graph within which the edge swap will take place.
435 w : integer
436 node id for which we need to perform a neighbor switch.
437 unsat: set of integers
438 set of node ids that have the same degree as w and are unsaturated.
439 h_node_residual_in: dict of integers
440 for a given node, keeps track of the remaining stubs to be added.
441 chords: set of tuples
442 keeps track of available positions to add edges.
443 h_partition_out: dict of integers
444 for a given node, keeps track of its partition id (out degree).
445 partition: integer
446 partition id to check if chords have to be updated.
447
448 Notes
449 -----
450 Same operation as directed_neighbor_switch except it handles this operation
451 for incoming edges instead of outgoing.
452 """
453 w_prime = unsat.pop()
454 unsat.add(w_prime)
455 # slightly faster declaring these as variables.
456 w_neighbs = list(G.predecessors(w))
457 w_prime_neighbs = list(G.predecessors(w_prime))
458 # select node v, a neighbor of w, that is not connected to w_prime.
459 for v in w_neighbs:
460 if (v not in w_prime_neighbs) and w_prime != v:
461 # removes (v,w), add (v,w_prime) and update data structures.
462 G.remove_edge(v, w)
463 G.add_edge(v, w_prime)
464 if h_partition_out[v] == partition:
465 chords.add((v, w))
466 chords.discard((v, w_prime))
467
468 h_node_residual_in[w] += 1
469 h_node_residual_in[w_prime] -= 1
470 if h_node_residual_in[w_prime] == 0:
471 unsat.remove(w_prime)
472 return None
473
474 # If neighbor switch didn't work, use the unsaturated node.
475 return w_prime
476
477
478 @py_random_state(3)
479 def directed_joint_degree_graph(in_degrees, out_degrees, nkk, seed=None):
480 """ Generates a random simple directed graph with the joint degree.
481
482 Parameters
483 ----------
484 degree_seq : list of tuples (of size 3)
485 degree sequence contains tuples of nodes with node id, in degree and
486 out degree.
487 nkk : dictionary of dictionary of integers
488 directed joint degree dictionary, for nodes of out degree k (first
489 level of dict) and nodes of in degree l (second level of dict)
490 describes the number of edges.
491 seed : hashable object, optional
492 Seed for random number generator.
493
494 Returns
495 -------
496 G : Graph
497 A directed graph with the specified inputs.
498
499 Raises
500 ------
501 NetworkXError
502 If degree_seq and nkk are not realizable as a simple directed graph.
503
504
505 Notes
506 -----
507 Similarly to the undirected version:
508 In each iteration of the "while loop" the algorithm picks two disconnected
509 nodes v and w, of degree k and l correspondingly, for which nkk[k][l] has
510 not reached its target yet i.e. (for given k,l): n_edges_add < nkk[k][l].
511 It then adds edge (v,w) and always increases the number of edges in graph G
512 by one.
513
514 The intelligence of the algorithm lies in the fact that it is always
515 possible to add an edge between disconnected nodes v and w, for which
516 nkk[degree(v)][degree(w)] has not reached its target, even if one or both
517 nodes do not have free stubs. If either node v or w does not have a free
518 stub, we perform a "neighbor switch", an edge rewiring move that releases a
519 free stub while keeping nkk the same.
520
521 The difference for the directed version lies in the fact that neighbor
522 switches might not be able to rewire, but in these cases unsaturated nodes
523 can be reassigned to use instead, see [1] for detailed description and
524 proofs.
525
526 The algorithm continues for E (number of edges in the graph) iterations of
527 the "while loop", at which point all entries of the given nkk[k][l] have
528 reached their target values and the construction is complete.
529
530 References
531 ----------
532 [1] B. Tillman, A. Markopoulou, C. T. Butts & M. Gjoka,
533 "Construction of Directed 2K Graphs". In Proc. of KDD 2017.
534
535 Examples
536 --------
537 >>> in_degrees = [0, 1, 1, 2]
538 >>> out_degrees = [1, 1, 1, 1]
539 >>> nkk = {1: {1: 2, 2: 2}}
540 >>> G = nx.directed_joint_degree_graph(in_degrees, out_degrees, nkk)
541 >>>
542 """
543 if not is_valid_directed_joint_degree(in_degrees, out_degrees, nkk):
544 msg = "Input is not realizable as a simple graph"
545 raise nx.NetworkXError(msg)
546
547 # start with an empty directed graph.
548 G = nx.DiGraph()
549
550 # for a given group, keep the list of all node ids.
551 h_degree_nodelist_in = {}
552 h_degree_nodelist_out = {}
553 # for a given group, keep the list of all unsaturated node ids.
554 h_degree_nodelist_in_unsat = {}
555 h_degree_nodelist_out_unsat = {}
556 # for a given node, keep track of the remaining stubs to be added.
557 h_node_residual_out = {}
558 h_node_residual_in = {}
559 # for a given node, keep track of the partition id.
560 h_partition_out = {}
561 h_partition_in = {}
562 # keep track of non-chords between pairs of partition ids.
563 non_chords = {}
564
565 # populate data structures
566 for idx, i in enumerate(in_degrees):
567 idx = int(idx)
568 if i > 0:
569 h_degree_nodelist_in.setdefault(i, [])
570 h_degree_nodelist_in_unsat.setdefault(i, set())
571 h_degree_nodelist_in[i].append(idx)
572 h_degree_nodelist_in_unsat[i].add(idx)
573 h_node_residual_in[idx] = i
574 h_partition_in[idx] = i
575
576 for idx, o in enumerate(out_degrees):
577 o = out_degrees[idx]
578 non_chords[(o, in_degrees[idx])] = non_chords.get((o, in_degrees[idx]), 0) + 1
579 idx = int(idx)
580 if o > 0:
581 h_degree_nodelist_out.setdefault(o, [])
582 h_degree_nodelist_out_unsat.setdefault(o, set())
583 h_degree_nodelist_out[o].append(idx)
584 h_degree_nodelist_out_unsat[o].add(idx)
585 h_node_residual_out[idx] = o
586 h_partition_out[idx] = o
587
588 G.add_node(idx)
589
590 nk_in = {}
591 nk_out = {}
592 for p in h_degree_nodelist_in:
593 nk_in[p] = len(h_degree_nodelist_in[p])
594 for p in h_degree_nodelist_out:
595 nk_out[p] = len(h_degree_nodelist_out[p])
596
597 # iterate over every degree pair (k,l) and add the number of edges given
598 # for each pair.
599 for k in nkk:
600 for l in nkk[k]:
601 n_edges_add = nkk[k][l]
602
603 if n_edges_add > 0:
604 # chords contains a random set of potential edges.
605 chords = set()
606
607 k_len = nk_out[k]
608 l_len = nk_in[l]
609 chords_sample = seed.sample(
610 range(k_len * l_len), n_edges_add + non_chords.get((k, l), 0)
611 )
612
613 num = 0
614 while len(chords) < n_edges_add:
615 i = h_degree_nodelist_out[k][chords_sample[num] % k_len]
616 j = h_degree_nodelist_in[l][chords_sample[num] // k_len]
617 num += 1
618 if i != j:
619 chords.add((i, j))
620
621 # k_unsat and l_unsat consist of nodes of in/out degree k and l
622 # that are unsaturated i.e. those nodes that have at least one
623 # available stub
624 k_unsat = h_degree_nodelist_out_unsat[k]
625 l_unsat = h_degree_nodelist_in_unsat[l]
626
627 while n_edges_add > 0:
628 v, w = chords.pop()
629 chords.add((v, w))
630
631 # if node v has no free stubs then do neighbor switch.
632 if h_node_residual_out[v] == 0:
633 _v = _directed_neighbor_switch(
634 G,
635 v,
636 k_unsat,
637 h_node_residual_out,
638 chords,
639 h_partition_in,
640 l,
641 )
642 if _v is not None:
643 v = _v
644
645 # if node w has no free stubs then do neighbor switch.
646 if h_node_residual_in[w] == 0:
647 _w = _directed_neighbor_switch_rev(
648 G,
649 w,
650 l_unsat,
651 h_node_residual_in,
652 chords,
653 h_partition_out,
654 k,
655 )
656 if _w is not None:
657 w = _w
658
659 # add edge (v,w) and update data structures.
660 G.add_edge(v, w)
661 h_node_residual_out[v] -= 1
662 h_node_residual_in[w] -= 1
663 n_edges_add -= 1
664 chords.discard((v, w))
665
666 if h_node_residual_out[v] == 0:
667 k_unsat.discard(v)
668 if h_node_residual_in[w] == 0:
669 l_unsat.discard(w)
670 return G