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