Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/generators/random_graphs.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 """ | |
2 Generators for random graphs. | |
3 | |
4 """ | |
5 | |
6 import itertools | |
7 import math | |
8 | |
9 import networkx as nx | |
10 from networkx.utils import py_random_state | |
11 from .classic import empty_graph, path_graph, complete_graph | |
12 from .degree_seq import degree_sequence_tree | |
13 from collections import defaultdict | |
14 | |
15 __all__ = [ | |
16 "fast_gnp_random_graph", | |
17 "gnp_random_graph", | |
18 "dense_gnm_random_graph", | |
19 "gnm_random_graph", | |
20 "erdos_renyi_graph", | |
21 "binomial_graph", | |
22 "newman_watts_strogatz_graph", | |
23 "watts_strogatz_graph", | |
24 "connected_watts_strogatz_graph", | |
25 "random_regular_graph", | |
26 "barabasi_albert_graph", | |
27 "dual_barabasi_albert_graph", | |
28 "extended_barabasi_albert_graph", | |
29 "powerlaw_cluster_graph", | |
30 "random_lobster", | |
31 "random_shell_graph", | |
32 "random_powerlaw_tree", | |
33 "random_powerlaw_tree_sequence", | |
34 "random_kernel_graph", | |
35 ] | |
36 | |
37 | |
38 @py_random_state(2) | |
39 def fast_gnp_random_graph(n, p, seed=None, directed=False): | |
40 """Returns a $G_{n,p}$ random graph, also known as an Erdős-Rényi graph or | |
41 a binomial graph. | |
42 | |
43 Parameters | |
44 ---------- | |
45 n : int | |
46 The number of nodes. | |
47 p : float | |
48 Probability for edge creation. | |
49 seed : integer, random_state, or None (default) | |
50 Indicator of random number generation state. | |
51 See :ref:`Randomness<randomness>`. | |
52 directed : bool, optional (default=False) | |
53 If True, this function returns a directed graph. | |
54 | |
55 Notes | |
56 ----- | |
57 The $G_{n,p}$ graph algorithm chooses each of the $[n (n - 1)] / 2$ | |
58 (undirected) or $n (n - 1)$ (directed) possible edges with probability $p$. | |
59 | |
60 This algorithm [1]_ runs in $O(n + m)$ time, where `m` is the expected number of | |
61 edges, which equals $p n (n - 1) / 2$. This should be faster than | |
62 :func:`gnp_random_graph` when $p$ is small and the expected number of edges | |
63 is small (that is, the graph is sparse). | |
64 | |
65 See Also | |
66 -------- | |
67 gnp_random_graph | |
68 | |
69 References | |
70 ---------- | |
71 .. [1] Vladimir Batagelj and Ulrik Brandes, | |
72 "Efficient generation of large random networks", | |
73 Phys. Rev. E, 71, 036113, 2005. | |
74 """ | |
75 G = empty_graph(n) | |
76 | |
77 if p <= 0 or p >= 1: | |
78 return nx.gnp_random_graph(n, p, seed=seed, directed=directed) | |
79 | |
80 w = -1 | |
81 lp = math.log(1.0 - p) | |
82 | |
83 if directed: | |
84 G = nx.DiGraph(G) | |
85 # Nodes in graph are from 0,n-1 (start with v as the first node index). | |
86 v = 0 | |
87 while v < n: | |
88 lr = math.log(1.0 - seed.random()) | |
89 w = w + 1 + int(lr / lp) | |
90 if v == w: # avoid self loops | |
91 w = w + 1 | |
92 while v < n <= w: | |
93 w = w - n | |
94 v = v + 1 | |
95 if v == w: # avoid self loops | |
96 w = w + 1 | |
97 if v < n: | |
98 G.add_edge(v, w) | |
99 else: | |
100 # Nodes in graph are from 0,n-1 (start with v as the second node index). | |
101 v = 1 | |
102 while v < n: | |
103 lr = math.log(1.0 - seed.random()) | |
104 w = w + 1 + int(lr / lp) | |
105 while w >= v and v < n: | |
106 w = w - v | |
107 v = v + 1 | |
108 if v < n: | |
109 G.add_edge(v, w) | |
110 return G | |
111 | |
112 | |
113 @py_random_state(2) | |
114 def gnp_random_graph(n, p, seed=None, directed=False): | |
115 """Returns a $G_{n,p}$ random graph, also known as an Erdős-Rényi graph | |
116 or a binomial graph. | |
117 | |
118 The $G_{n,p}$ model chooses each of the possible edges with probability $p$. | |
119 | |
120 Parameters | |
121 ---------- | |
122 n : int | |
123 The number of nodes. | |
124 p : float | |
125 Probability for edge creation. | |
126 seed : integer, random_state, or None (default) | |
127 Indicator of random number generation state. | |
128 See :ref:`Randomness<randomness>`. | |
129 directed : bool, optional (default=False) | |
130 If True, this function returns a directed graph. | |
131 | |
132 See Also | |
133 -------- | |
134 fast_gnp_random_graph | |
135 | |
136 Notes | |
137 ----- | |
138 This algorithm [2]_ runs in $O(n^2)$ time. For sparse graphs (that is, for | |
139 small values of $p$), :func:`fast_gnp_random_graph` is a faster algorithm. | |
140 | |
141 :func:`binomial_graph` and :func:`erdos_renyi_graph` are | |
142 aliases for :func:`gnp_random_graph`. | |
143 | |
144 >>> nx.binomial_graph is nx.gnp_random_graph | |
145 True | |
146 >>> nx.erdos_renyi_graph is nx.gnp_random_graph | |
147 True | |
148 | |
149 References | |
150 ---------- | |
151 .. [1] P. Erdős and A. Rényi, On Random Graphs, Publ. Math. 6, 290 (1959). | |
152 .. [2] E. N. Gilbert, Random Graphs, Ann. Math. Stat., 30, 1141 (1959). | |
153 """ | |
154 if directed: | |
155 edges = itertools.permutations(range(n), 2) | |
156 G = nx.DiGraph() | |
157 else: | |
158 edges = itertools.combinations(range(n), 2) | |
159 G = nx.Graph() | |
160 G.add_nodes_from(range(n)) | |
161 if p <= 0: | |
162 return G | |
163 if p >= 1: | |
164 return complete_graph(n, create_using=G) | |
165 | |
166 for e in edges: | |
167 if seed.random() < p: | |
168 G.add_edge(*e) | |
169 return G | |
170 | |
171 | |
172 # add some aliases to common names | |
173 binomial_graph = gnp_random_graph | |
174 erdos_renyi_graph = gnp_random_graph | |
175 | |
176 | |
177 @py_random_state(2) | |
178 def dense_gnm_random_graph(n, m, seed=None): | |
179 """Returns a $G_{n,m}$ random graph. | |
180 | |
181 In the $G_{n,m}$ model, a graph is chosen uniformly at random from the set | |
182 of all graphs with $n$ nodes and $m$ edges. | |
183 | |
184 This algorithm should be faster than :func:`gnm_random_graph` for dense | |
185 graphs. | |
186 | |
187 Parameters | |
188 ---------- | |
189 n : int | |
190 The number of nodes. | |
191 m : int | |
192 The number of edges. | |
193 seed : integer, random_state, or None (default) | |
194 Indicator of random number generation state. | |
195 See :ref:`Randomness<randomness>`. | |
196 | |
197 See Also | |
198 -------- | |
199 gnm_random_graph() | |
200 | |
201 Notes | |
202 ----- | |
203 Algorithm by Keith M. Briggs Mar 31, 2006. | |
204 Inspired by Knuth's Algorithm S (Selection sampling technique), | |
205 in section 3.4.2 of [1]_. | |
206 | |
207 References | |
208 ---------- | |
209 .. [1] Donald E. Knuth, The Art of Computer Programming, | |
210 Volume 2/Seminumerical algorithms, Third Edition, Addison-Wesley, 1997. | |
211 """ | |
212 mmax = n * (n - 1) / 2 | |
213 if m >= mmax: | |
214 G = complete_graph(n) | |
215 else: | |
216 G = empty_graph(n) | |
217 | |
218 if n == 1 or m >= mmax: | |
219 return G | |
220 | |
221 u = 0 | |
222 v = 1 | |
223 t = 0 | |
224 k = 0 | |
225 while True: | |
226 if seed.randrange(mmax - t) < m - k: | |
227 G.add_edge(u, v) | |
228 k += 1 | |
229 if k == m: | |
230 return G | |
231 t += 1 | |
232 v += 1 | |
233 if v == n: # go to next row of adjacency matrix | |
234 u += 1 | |
235 v = u + 1 | |
236 | |
237 | |
238 @py_random_state(2) | |
239 def gnm_random_graph(n, m, seed=None, directed=False): | |
240 """Returns a $G_{n,m}$ random graph. | |
241 | |
242 In the $G_{n,m}$ model, a graph is chosen uniformly at random from the set | |
243 of all graphs with $n$ nodes and $m$ edges. | |
244 | |
245 This algorithm should be faster than :func:`dense_gnm_random_graph` for | |
246 sparse graphs. | |
247 | |
248 Parameters | |
249 ---------- | |
250 n : int | |
251 The number of nodes. | |
252 m : int | |
253 The number of edges. | |
254 seed : integer, random_state, or None (default) | |
255 Indicator of random number generation state. | |
256 See :ref:`Randomness<randomness>`. | |
257 directed : bool, optional (default=False) | |
258 If True return a directed graph | |
259 | |
260 See also | |
261 -------- | |
262 dense_gnm_random_graph | |
263 | |
264 """ | |
265 if directed: | |
266 G = nx.DiGraph() | |
267 else: | |
268 G = nx.Graph() | |
269 G.add_nodes_from(range(n)) | |
270 | |
271 if n == 1: | |
272 return G | |
273 max_edges = n * (n - 1) | |
274 if not directed: | |
275 max_edges /= 2.0 | |
276 if m >= max_edges: | |
277 return complete_graph(n, create_using=G) | |
278 | |
279 nlist = list(G) | |
280 edge_count = 0 | |
281 while edge_count < m: | |
282 # generate random edge,u,v | |
283 u = seed.choice(nlist) | |
284 v = seed.choice(nlist) | |
285 if u == v or G.has_edge(u, v): | |
286 continue | |
287 else: | |
288 G.add_edge(u, v) | |
289 edge_count = edge_count + 1 | |
290 return G | |
291 | |
292 | |
293 @py_random_state(3) | |
294 def newman_watts_strogatz_graph(n, k, p, seed=None): | |
295 """Returns a Newman–Watts–Strogatz small-world graph. | |
296 | |
297 Parameters | |
298 ---------- | |
299 n : int | |
300 The number of nodes. | |
301 k : int | |
302 Each node is joined with its `k` nearest neighbors in a ring | |
303 topology. | |
304 p : float | |
305 The probability of adding a new edge for each edge. | |
306 seed : integer, random_state, or None (default) | |
307 Indicator of random number generation state. | |
308 See :ref:`Randomness<randomness>`. | |
309 | |
310 Notes | |
311 ----- | |
312 First create a ring over $n$ nodes [1]_. Then each node in the ring is | |
313 connected with its $k$ nearest neighbors (or $k - 1$ neighbors if $k$ | |
314 is odd). Then shortcuts are created by adding new edges as follows: for | |
315 each edge $(u, v)$ in the underlying "$n$-ring with $k$ nearest | |
316 neighbors" with probability $p$ add a new edge $(u, w)$ with | |
317 randomly-chosen existing node $w$. In contrast with | |
318 :func:`watts_strogatz_graph`, no edges are removed. | |
319 | |
320 See Also | |
321 -------- | |
322 watts_strogatz_graph() | |
323 | |
324 References | |
325 ---------- | |
326 .. [1] M. E. J. Newman and D. J. Watts, | |
327 Renormalization group analysis of the small-world network model, | |
328 Physics Letters A, 263, 341, 1999. | |
329 https://doi.org/10.1016/S0375-9601(99)00757-4 | |
330 """ | |
331 if k > n: | |
332 raise nx.NetworkXError("k>=n, choose smaller k or larger n") | |
333 | |
334 # If k == n the graph return is a complete graph | |
335 if k == n: | |
336 return nx.complete_graph(n) | |
337 | |
338 G = empty_graph(n) | |
339 nlist = list(G.nodes()) | |
340 fromv = nlist | |
341 # connect the k/2 neighbors | |
342 for j in range(1, k // 2 + 1): | |
343 tov = fromv[j:] + fromv[0:j] # the first j are now last | |
344 for i in range(len(fromv)): | |
345 G.add_edge(fromv[i], tov[i]) | |
346 # for each edge u-v, with probability p, randomly select existing | |
347 # node w and add new edge u-w | |
348 e = list(G.edges()) | |
349 for (u, v) in e: | |
350 if seed.random() < p: | |
351 w = seed.choice(nlist) | |
352 # no self-loops and reject if edge u-w exists | |
353 # is that the correct NWS model? | |
354 while w == u or G.has_edge(u, w): | |
355 w = seed.choice(nlist) | |
356 if G.degree(u) >= n - 1: | |
357 break # skip this rewiring | |
358 else: | |
359 G.add_edge(u, w) | |
360 return G | |
361 | |
362 | |
363 @py_random_state(3) | |
364 def watts_strogatz_graph(n, k, p, seed=None): | |
365 """Returns a Watts–Strogatz small-world graph. | |
366 | |
367 Parameters | |
368 ---------- | |
369 n : int | |
370 The number of nodes | |
371 k : int | |
372 Each node is joined with its `k` nearest neighbors in a ring | |
373 topology. | |
374 p : float | |
375 The probability of rewiring each edge | |
376 seed : integer, random_state, or None (default) | |
377 Indicator of random number generation state. | |
378 See :ref:`Randomness<randomness>`. | |
379 | |
380 See Also | |
381 -------- | |
382 newman_watts_strogatz_graph() | |
383 connected_watts_strogatz_graph() | |
384 | |
385 Notes | |
386 ----- | |
387 First create a ring over $n$ nodes [1]_. Then each node in the ring is joined | |
388 to its $k$ nearest neighbors (or $k - 1$ neighbors if $k$ is odd). | |
389 Then shortcuts are created by replacing some edges as follows: for each | |
390 edge $(u, v)$ in the underlying "$n$-ring with $k$ nearest neighbors" | |
391 with probability $p$ replace it with a new edge $(u, w)$ with uniformly | |
392 random choice of existing node $w$. | |
393 | |
394 In contrast with :func:`newman_watts_strogatz_graph`, the random rewiring | |
395 does not increase the number of edges. The rewired graph is not guaranteed | |
396 to be connected as in :func:`connected_watts_strogatz_graph`. | |
397 | |
398 References | |
399 ---------- | |
400 .. [1] Duncan J. Watts and Steven H. Strogatz, | |
401 Collective dynamics of small-world networks, | |
402 Nature, 393, pp. 440--442, 1998. | |
403 """ | |
404 if k > n: | |
405 raise nx.NetworkXError("k>n, choose smaller k or larger n") | |
406 | |
407 # If k == n, the graph is complete not Watts-Strogatz | |
408 if k == n: | |
409 return nx.complete_graph(n) | |
410 | |
411 G = nx.Graph() | |
412 nodes = list(range(n)) # nodes are labeled 0 to n-1 | |
413 # connect each node to k/2 neighbors | |
414 for j in range(1, k // 2 + 1): | |
415 targets = nodes[j:] + nodes[0:j] # first j nodes are now last in list | |
416 G.add_edges_from(zip(nodes, targets)) | |
417 # rewire edges from each node | |
418 # loop over all nodes in order (label) and neighbors in order (distance) | |
419 # no self loops or multiple edges allowed | |
420 for j in range(1, k // 2 + 1): # outer loop is neighbors | |
421 targets = nodes[j:] + nodes[0:j] # first j nodes are now last in list | |
422 # inner loop in node order | |
423 for u, v in zip(nodes, targets): | |
424 if seed.random() < p: | |
425 w = seed.choice(nodes) | |
426 # Enforce no self-loops or multiple edges | |
427 while w == u or G.has_edge(u, w): | |
428 w = seed.choice(nodes) | |
429 if G.degree(u) >= n - 1: | |
430 break # skip this rewiring | |
431 else: | |
432 G.remove_edge(u, v) | |
433 G.add_edge(u, w) | |
434 return G | |
435 | |
436 | |
437 @py_random_state(4) | |
438 def connected_watts_strogatz_graph(n, k, p, tries=100, seed=None): | |
439 """Returns a connected Watts–Strogatz small-world graph. | |
440 | |
441 Attempts to generate a connected graph by repeated generation of | |
442 Watts–Strogatz small-world graphs. An exception is raised if the maximum | |
443 number of tries is exceeded. | |
444 | |
445 Parameters | |
446 ---------- | |
447 n : int | |
448 The number of nodes | |
449 k : int | |
450 Each node is joined with its `k` nearest neighbors in a ring | |
451 topology. | |
452 p : float | |
453 The probability of rewiring each edge | |
454 tries : int | |
455 Number of attempts to generate a connected graph. | |
456 seed : integer, random_state, or None (default) | |
457 Indicator of random number generation state. | |
458 See :ref:`Randomness<randomness>`. | |
459 | |
460 Notes | |
461 ----- | |
462 First create a ring over $n$ nodes [1]_. Then each node in the ring is joined | |
463 to its $k$ nearest neighbors (or $k - 1$ neighbors if $k$ is odd). | |
464 Then shortcuts are created by replacing some edges as follows: for each | |
465 edge $(u, v)$ in the underlying "$n$-ring with $k$ nearest neighbors" | |
466 with probability $p$ replace it with a new edge $(u, w)$ with uniformly | |
467 random choice of existing node $w$. | |
468 The entire process is repeated until a connected graph results. | |
469 | |
470 See Also | |
471 -------- | |
472 newman_watts_strogatz_graph() | |
473 watts_strogatz_graph() | |
474 | |
475 References | |
476 ---------- | |
477 .. [1] Duncan J. Watts and Steven H. Strogatz, | |
478 Collective dynamics of small-world networks, | |
479 Nature, 393, pp. 440--442, 1998. | |
480 """ | |
481 for i in range(tries): | |
482 # seed is an RNG so should change sequence each call | |
483 G = watts_strogatz_graph(n, k, p, seed) | |
484 if nx.is_connected(G): | |
485 return G | |
486 raise nx.NetworkXError("Maximum number of tries exceeded") | |
487 | |
488 | |
489 @py_random_state(2) | |
490 def random_regular_graph(d, n, seed=None): | |
491 r"""Returns a random $d$-regular graph on $n$ nodes. | |
492 | |
493 The resulting graph has no self-loops or parallel edges. | |
494 | |
495 Parameters | |
496 ---------- | |
497 d : int | |
498 The degree of each node. | |
499 n : integer | |
500 The number of nodes. The value of $n \times d$ must be even. | |
501 seed : integer, random_state, or None (default) | |
502 Indicator of random number generation state. | |
503 See :ref:`Randomness<randomness>`. | |
504 | |
505 Notes | |
506 ----- | |
507 The nodes are numbered from $0$ to $n - 1$. | |
508 | |
509 Kim and Vu's paper [2]_ shows that this algorithm samples in an | |
510 asymptotically uniform way from the space of random graphs when | |
511 $d = O(n^{1 / 3 - \epsilon})$. | |
512 | |
513 Raises | |
514 ------ | |
515 | |
516 NetworkXError | |
517 If $n \times d$ is odd or $d$ is greater than or equal to $n$. | |
518 | |
519 References | |
520 ---------- | |
521 .. [1] A. Steger and N. Wormald, | |
522 Generating random regular graphs quickly, | |
523 Probability and Computing 8 (1999), 377-396, 1999. | |
524 http://citeseer.ist.psu.edu/steger99generating.html | |
525 | |
526 .. [2] Jeong Han Kim and Van H. Vu, | |
527 Generating random regular graphs, | |
528 Proceedings of the thirty-fifth ACM symposium on Theory of computing, | |
529 San Diego, CA, USA, pp 213--222, 2003. | |
530 http://portal.acm.org/citation.cfm?id=780542.780576 | |
531 """ | |
532 if (n * d) % 2 != 0: | |
533 raise nx.NetworkXError("n * d must be even") | |
534 | |
535 if not 0 <= d < n: | |
536 raise nx.NetworkXError("the 0 <= d < n inequality must be satisfied") | |
537 | |
538 if d == 0: | |
539 return empty_graph(n) | |
540 | |
541 def _suitable(edges, potential_edges): | |
542 # Helper subroutine to check if there are suitable edges remaining | |
543 # If False, the generation of the graph has failed | |
544 if not potential_edges: | |
545 return True | |
546 for s1 in potential_edges: | |
547 for s2 in potential_edges: | |
548 # Two iterators on the same dictionary are guaranteed | |
549 # to visit it in the same order if there are no | |
550 # intervening modifications. | |
551 if s1 == s2: | |
552 # Only need to consider s1-s2 pair one time | |
553 break | |
554 if s1 > s2: | |
555 s1, s2 = s2, s1 | |
556 if (s1, s2) not in edges: | |
557 return True | |
558 return False | |
559 | |
560 def _try_creation(): | |
561 # Attempt to create an edge set | |
562 | |
563 edges = set() | |
564 stubs = list(range(n)) * d | |
565 | |
566 while stubs: | |
567 potential_edges = defaultdict(lambda: 0) | |
568 seed.shuffle(stubs) | |
569 stubiter = iter(stubs) | |
570 for s1, s2 in zip(stubiter, stubiter): | |
571 if s1 > s2: | |
572 s1, s2 = s2, s1 | |
573 if s1 != s2 and ((s1, s2) not in edges): | |
574 edges.add((s1, s2)) | |
575 else: | |
576 potential_edges[s1] += 1 | |
577 potential_edges[s2] += 1 | |
578 | |
579 if not _suitable(edges, potential_edges): | |
580 return None # failed to find suitable edge set | |
581 | |
582 stubs = [ | |
583 node | |
584 for node, potential in potential_edges.items() | |
585 for _ in range(potential) | |
586 ] | |
587 return edges | |
588 | |
589 # Even though a suitable edge set exists, | |
590 # the generation of such a set is not guaranteed. | |
591 # Try repeatedly to find one. | |
592 edges = _try_creation() | |
593 while edges is None: | |
594 edges = _try_creation() | |
595 | |
596 G = nx.Graph() | |
597 G.add_edges_from(edges) | |
598 | |
599 return G | |
600 | |
601 | |
602 def _random_subset(seq, m, rng): | |
603 """ Return m unique elements from seq. | |
604 | |
605 This differs from random.sample which can return repeated | |
606 elements if seq holds repeated elements. | |
607 | |
608 Note: rng is a random.Random or numpy.random.RandomState instance. | |
609 """ | |
610 targets = set() | |
611 while len(targets) < m: | |
612 x = rng.choice(seq) | |
613 targets.add(x) | |
614 return targets | |
615 | |
616 | |
617 @py_random_state(2) | |
618 def barabasi_albert_graph(n, m, seed=None): | |
619 """Returns a random graph according to the Barabási–Albert preferential | |
620 attachment model. | |
621 | |
622 A graph of $n$ nodes is grown by attaching new nodes each with $m$ | |
623 edges that are preferentially attached to existing nodes with high degree. | |
624 | |
625 Parameters | |
626 ---------- | |
627 n : int | |
628 Number of nodes | |
629 m : int | |
630 Number of edges to attach from a new node to existing nodes | |
631 seed : integer, random_state, or None (default) | |
632 Indicator of random number generation state. | |
633 See :ref:`Randomness<randomness>`. | |
634 | |
635 Returns | |
636 ------- | |
637 G : Graph | |
638 | |
639 Raises | |
640 ------ | |
641 NetworkXError | |
642 If `m` does not satisfy ``1 <= m < n``. | |
643 | |
644 References | |
645 ---------- | |
646 .. [1] A. L. Barabási and R. Albert "Emergence of scaling in | |
647 random networks", Science 286, pp 509-512, 1999. | |
648 """ | |
649 | |
650 if m < 1 or m >= n: | |
651 raise nx.NetworkXError( | |
652 f"Barabási–Albert network must have m >= 1 and m < n, m = {m}, n = {n}" | |
653 ) | |
654 | |
655 # Add m initial nodes (m0 in barabasi-speak) | |
656 G = empty_graph(m) | |
657 # Target nodes for new edges | |
658 targets = list(range(m)) | |
659 # List of existing nodes, with nodes repeated once for each adjacent edge | |
660 repeated_nodes = [] | |
661 # Start adding the other n-m nodes. The first node is m. | |
662 source = m | |
663 while source < n: | |
664 # Add edges to m nodes from the source. | |
665 G.add_edges_from(zip([source] * m, targets)) | |
666 # Add one node to the list for each new edge just created. | |
667 repeated_nodes.extend(targets) | |
668 # And the new node "source" has m edges to add to the list. | |
669 repeated_nodes.extend([source] * m) | |
670 # Now choose m unique nodes from the existing nodes | |
671 # Pick uniformly from repeated_nodes (preferential attachment) | |
672 targets = _random_subset(repeated_nodes, m, seed) | |
673 source += 1 | |
674 return G | |
675 | |
676 | |
677 @py_random_state(4) | |
678 def dual_barabasi_albert_graph(n, m1, m2, p, seed=None): | |
679 """Returns a random graph according to the dual Barabási–Albert preferential | |
680 attachment model. | |
681 | |
682 A graph of $n$ nodes is grown by attaching new nodes each with either $m_1$ | |
683 edges (with probability $p$) or $m_2$ edges (with probability $1-p$) that | |
684 are preferentially attached to existing nodes with high degree. | |
685 | |
686 Parameters | |
687 ---------- | |
688 n : int | |
689 Number of nodes | |
690 m1 : int | |
691 Number of edges to attach from a new node to existing nodes with probability $p$ | |
692 m2 : int | |
693 Number of edges to attach from a new node to existing nodes with probability $1-p$ | |
694 p : float | |
695 The probability of attaching $m_1$ edges (as opposed to $m_2$ edges) | |
696 seed : integer, random_state, or None (default) | |
697 Indicator of random number generation state. | |
698 See :ref:`Randomness<randomness>`. | |
699 | |
700 Returns | |
701 ------- | |
702 G : Graph | |
703 | |
704 Raises | |
705 ------ | |
706 NetworkXError | |
707 If `m1` and `m2` do not satisfy ``1 <= m1,m2 < n`` or `p` does not satisfy ``0 <= p <= 1``. | |
708 | |
709 References | |
710 ---------- | |
711 .. [1] N. Moshiri "The dual-Barabasi-Albert model", arXiv:1810.10538. | |
712 """ | |
713 | |
714 if m1 < 1 or m1 >= n: | |
715 raise nx.NetworkXError( | |
716 f"Dual Barabási–Albert network must have m1 >= 1 and m1 < n, m1 = {m1}, n = {n}" | |
717 ) | |
718 if m2 < 1 or m2 >= n: | |
719 raise nx.NetworkXError( | |
720 f"Dual Barabási–Albert network must have m2 >= 1 and m2 < n, m2 = {m2}, n = {n}" | |
721 ) | |
722 if p < 0 or p > 1: | |
723 raise nx.NetworkXError( | |
724 f"Dual Barabási–Albert network must have 0 <= p <= 1, p = {p}" | |
725 ) | |
726 | |
727 # For simplicity, if p == 0 or 1, just return BA | |
728 if p == 1: | |
729 return barabasi_albert_graph(n, m1, seed) | |
730 elif p == 0: | |
731 return barabasi_albert_graph(n, m2, seed) | |
732 | |
733 # Add max(m1,m2) initial nodes (m0 in barabasi-speak) | |
734 G = empty_graph(max(m1, m2)) | |
735 # Target nodes for new edges | |
736 targets = list(range(max(m1, m2))) | |
737 # List of existing nodes, with nodes repeated once for each adjacent edge | |
738 repeated_nodes = [] | |
739 # Start adding the remaining nodes. | |
740 source = max(m1, m2) | |
741 # Pick which m to use first time (m1 or m2) | |
742 if seed.random() < p: | |
743 m = m1 | |
744 else: | |
745 m = m2 | |
746 while source < n: | |
747 # Add edges to m nodes from the source. | |
748 G.add_edges_from(zip([source] * m, targets)) | |
749 # Add one node to the list for each new edge just created. | |
750 repeated_nodes.extend(targets) | |
751 # And the new node "source" has m edges to add to the list. | |
752 repeated_nodes.extend([source] * m) | |
753 # Pick which m to use next time (m1 or m2) | |
754 if seed.random() < p: | |
755 m = m1 | |
756 else: | |
757 m = m2 | |
758 # Now choose m unique nodes from the existing nodes | |
759 # Pick uniformly from repeated_nodes (preferential attachment) | |
760 targets = _random_subset(repeated_nodes, m, seed) | |
761 source += 1 | |
762 return G | |
763 | |
764 | |
765 @py_random_state(4) | |
766 def extended_barabasi_albert_graph(n, m, p, q, seed=None): | |
767 """Returns an extended Barabási–Albert model graph. | |
768 | |
769 An extended Barabási–Albert model graph is a random graph constructed | |
770 using preferential attachment. The extended model allows new edges, | |
771 rewired edges or new nodes. Based on the probabilities $p$ and $q$ | |
772 with $p + q < 1$, the growing behavior of the graph is determined as: | |
773 | |
774 1) With $p$ probability, $m$ new edges are added to the graph, | |
775 starting from randomly chosen existing nodes and attached preferentially at the other end. | |
776 | |
777 2) With $q$ probability, $m$ existing edges are rewired | |
778 by randomly choosing an edge and rewiring one end to a preferentially chosen node. | |
779 | |
780 3) With $(1 - p - q)$ probability, $m$ new nodes are added to the graph | |
781 with edges attached preferentially. | |
782 | |
783 When $p = q = 0$, the model behaves just like the Barabási–Alber model. | |
784 | |
785 Parameters | |
786 ---------- | |
787 n : int | |
788 Number of nodes | |
789 m : int | |
790 Number of edges with which a new node attaches to existing nodes | |
791 p : float | |
792 Probability value for adding an edge between existing nodes. p + q < 1 | |
793 q : float | |
794 Probability value of rewiring of existing edges. p + q < 1 | |
795 seed : integer, random_state, or None (default) | |
796 Indicator of random number generation state. | |
797 See :ref:`Randomness<randomness>`. | |
798 | |
799 Returns | |
800 ------- | |
801 G : Graph | |
802 | |
803 Raises | |
804 ------ | |
805 NetworkXError | |
806 If `m` does not satisfy ``1 <= m < n`` or ``1 >= p + q`` | |
807 | |
808 References | |
809 ---------- | |
810 .. [1] Albert, R., & Barabási, A. L. (2000) | |
811 Topology of evolving networks: local events and universality | |
812 Physical review letters, 85(24), 5234. | |
813 """ | |
814 if m < 1 or m >= n: | |
815 msg = f"Extended Barabasi-Albert network needs m>=1 and m<n, m={m}, n={n}" | |
816 raise nx.NetworkXError(msg) | |
817 if p + q >= 1: | |
818 msg = f"Extended Barabasi-Albert network needs p + q <= 1, p={p}, q={q}" | |
819 raise nx.NetworkXError(msg) | |
820 | |
821 # Add m initial nodes (m0 in barabasi-speak) | |
822 G = empty_graph(m) | |
823 | |
824 # List of nodes to represent the preferential attachment random selection. | |
825 # At the creation of the graph, all nodes are added to the list | |
826 # so that even nodes that are not connected have a chance to get selected, | |
827 # for rewiring and adding of edges. | |
828 # With each new edge, nodes at the ends of the edge are added to the list. | |
829 attachment_preference = [] | |
830 attachment_preference.extend(range(m)) | |
831 | |
832 # Start adding the other n-m nodes. The first node is m. | |
833 new_node = m | |
834 while new_node < n: | |
835 a_probability = seed.random() | |
836 | |
837 # Total number of edges of a Clique of all the nodes | |
838 clique_degree = len(G) - 1 | |
839 clique_size = (len(G) * clique_degree) / 2 | |
840 | |
841 # Adding m new edges, if there is room to add them | |
842 if a_probability < p and G.size() <= clique_size - m: | |
843 # Select the nodes where an edge can be added | |
844 elligible_nodes = [nd for nd, deg in G.degree() if deg < clique_degree] | |
845 for i in range(m): | |
846 # Choosing a random source node from elligible_nodes | |
847 src_node = seed.choice(elligible_nodes) | |
848 | |
849 # Picking a possible node that is not 'src_node' or | |
850 # neighbor with 'src_node', with preferential attachment | |
851 prohibited_nodes = list(G[src_node]) | |
852 prohibited_nodes.append(src_node) | |
853 # This will raise an exception if the sequence is empty | |
854 dest_node = seed.choice( | |
855 [nd for nd in attachment_preference if nd not in prohibited_nodes] | |
856 ) | |
857 # Adding the new edge | |
858 G.add_edge(src_node, dest_node) | |
859 | |
860 # Appending both nodes to add to their preferential attachment | |
861 attachment_preference.append(src_node) | |
862 attachment_preference.append(dest_node) | |
863 | |
864 # Adjusting the elligible nodes. Degree may be saturated. | |
865 if G.degree(src_node) == clique_degree: | |
866 elligible_nodes.remove(src_node) | |
867 if ( | |
868 G.degree(dest_node) == clique_degree | |
869 and dest_node in elligible_nodes | |
870 ): | |
871 elligible_nodes.remove(dest_node) | |
872 | |
873 # Rewiring m edges, if there are enough edges | |
874 elif p <= a_probability < (p + q) and m <= G.size() < clique_size: | |
875 # Selecting nodes that have at least 1 edge but that are not | |
876 # fully connected to ALL other nodes (center of star). | |
877 # These nodes are the pivot nodes of the edges to rewire | |
878 elligible_nodes = [nd for nd, deg in G.degree() if 0 < deg < clique_degree] | |
879 for i in range(m): | |
880 # Choosing a random source node | |
881 node = seed.choice(elligible_nodes) | |
882 | |
883 # The available nodes do have a neighbor at least. | |
884 neighbor_nodes = list(G[node]) | |
885 | |
886 # Choosing the other end that will get dettached | |
887 src_node = seed.choice(neighbor_nodes) | |
888 | |
889 # Picking a target node that is not 'node' or | |
890 # neighbor with 'node', with preferential attachment | |
891 neighbor_nodes.append(node) | |
892 dest_node = seed.choice( | |
893 [nd for nd in attachment_preference if nd not in neighbor_nodes] | |
894 ) | |
895 # Rewire | |
896 G.remove_edge(node, src_node) | |
897 G.add_edge(node, dest_node) | |
898 | |
899 # Adjusting the preferential attachment list | |
900 attachment_preference.remove(src_node) | |
901 attachment_preference.append(dest_node) | |
902 | |
903 # Adjusting the elligible nodes. | |
904 # nodes may be saturated or isolated. | |
905 if G.degree(src_node) == 0 and src_node in elligible_nodes: | |
906 elligible_nodes.remove(src_node) | |
907 if dest_node in elligible_nodes: | |
908 if G.degree(dest_node) == clique_degree: | |
909 elligible_nodes.remove(dest_node) | |
910 else: | |
911 if G.degree(dest_node) == 1: | |
912 elligible_nodes.append(dest_node) | |
913 | |
914 # Adding new node with m edges | |
915 else: | |
916 # Select the edges' nodes by preferential attachment | |
917 targets = _random_subset(attachment_preference, m, seed) | |
918 G.add_edges_from(zip([new_node] * m, targets)) | |
919 | |
920 # Add one node to the list for each new edge just created. | |
921 attachment_preference.extend(targets) | |
922 # The new node has m edges to it, plus itself: m + 1 | |
923 attachment_preference.extend([new_node] * (m + 1)) | |
924 new_node += 1 | |
925 return G | |
926 | |
927 | |
928 @py_random_state(3) | |
929 def powerlaw_cluster_graph(n, m, p, seed=None): | |
930 """Holme and Kim algorithm for growing graphs with powerlaw | |
931 degree distribution and approximate average clustering. | |
932 | |
933 Parameters | |
934 ---------- | |
935 n : int | |
936 the number of nodes | |
937 m : int | |
938 the number of random edges to add for each new node | |
939 p : float, | |
940 Probability of adding a triangle after adding a random edge | |
941 seed : integer, random_state, or None (default) | |
942 Indicator of random number generation state. | |
943 See :ref:`Randomness<randomness>`. | |
944 | |
945 Notes | |
946 ----- | |
947 The average clustering has a hard time getting above a certain | |
948 cutoff that depends on `m`. This cutoff is often quite low. The | |
949 transitivity (fraction of triangles to possible triangles) seems to | |
950 decrease with network size. | |
951 | |
952 It is essentially the Barabási–Albert (BA) growth model with an | |
953 extra step that each random edge is followed by a chance of | |
954 making an edge to one of its neighbors too (and thus a triangle). | |
955 | |
956 This algorithm improves on BA in the sense that it enables a | |
957 higher average clustering to be attained if desired. | |
958 | |
959 It seems possible to have a disconnected graph with this algorithm | |
960 since the initial `m` nodes may not be all linked to a new node | |
961 on the first iteration like the BA model. | |
962 | |
963 Raises | |
964 ------ | |
965 NetworkXError | |
966 If `m` does not satisfy ``1 <= m <= n`` or `p` does not | |
967 satisfy ``0 <= p <= 1``. | |
968 | |
969 References | |
970 ---------- | |
971 .. [1] P. Holme and B. J. Kim, | |
972 "Growing scale-free networks with tunable clustering", | |
973 Phys. Rev. E, 65, 026107, 2002. | |
974 """ | |
975 | |
976 if m < 1 or n < m: | |
977 raise nx.NetworkXError(f"NetworkXError must have m>1 and m<n, m={m},n={n}") | |
978 | |
979 if p > 1 or p < 0: | |
980 raise nx.NetworkXError(f"NetworkXError p must be in [0,1], p={p}") | |
981 | |
982 G = empty_graph(m) # add m initial nodes (m0 in barabasi-speak) | |
983 repeated_nodes = list(G.nodes()) # list of existing nodes to sample from | |
984 # with nodes repeated once for each adjacent edge | |
985 source = m # next node is m | |
986 while source < n: # Now add the other n-1 nodes | |
987 possible_targets = _random_subset(repeated_nodes, m, seed) | |
988 # do one preferential attachment for new node | |
989 target = possible_targets.pop() | |
990 G.add_edge(source, target) | |
991 repeated_nodes.append(target) # add one node to list for each new link | |
992 count = 1 | |
993 while count < m: # add m-1 more new links | |
994 if seed.random() < p: # clustering step: add triangle | |
995 neighborhood = [ | |
996 nbr | |
997 for nbr in G.neighbors(target) | |
998 if not G.has_edge(source, nbr) and not nbr == source | |
999 ] | |
1000 if neighborhood: # if there is a neighbor without a link | |
1001 nbr = seed.choice(neighborhood) | |
1002 G.add_edge(source, nbr) # add triangle | |
1003 repeated_nodes.append(nbr) | |
1004 count = count + 1 | |
1005 continue # go to top of while loop | |
1006 # else do preferential attachment step if above fails | |
1007 target = possible_targets.pop() | |
1008 G.add_edge(source, target) | |
1009 repeated_nodes.append(target) | |
1010 count = count + 1 | |
1011 | |
1012 repeated_nodes.extend([source] * m) # add source node to list m times | |
1013 source += 1 | |
1014 return G | |
1015 | |
1016 | |
1017 @py_random_state(3) | |
1018 def random_lobster(n, p1, p2, seed=None): | |
1019 """Returns a random lobster graph. | |
1020 | |
1021 A lobster is a tree that reduces to a caterpillar when pruning all | |
1022 leaf nodes. A caterpillar is a tree that reduces to a path graph | |
1023 when pruning all leaf nodes; setting `p2` to zero produces a caterpillar. | |
1024 | |
1025 This implementation iterates on the probabilities `p1` and `p2` to add | |
1026 edges at levels 1 and 2, respectively. Graphs are therefore constructed | |
1027 iteratively with uniform randomness at each level rather than being selected | |
1028 uniformly at random from the set of all possible lobsters. | |
1029 | |
1030 Parameters | |
1031 ---------- | |
1032 n : int | |
1033 The expected number of nodes in the backbone | |
1034 p1 : float | |
1035 Probability of adding an edge to the backbone | |
1036 p2 : float | |
1037 Probability of adding an edge one level beyond backbone | |
1038 seed : integer, random_state, or None (default) | |
1039 Indicator of random number generation state. | |
1040 See :ref:`Randomness<randomness>`. | |
1041 | |
1042 Raises | |
1043 ------ | |
1044 NetworkXError | |
1045 If `p1` or `p2` parameters are >= 1 because the while loops would never finish. | |
1046 """ | |
1047 p1, p2 = abs(p1), abs(p2) | |
1048 if any([p >= 1 for p in [p1, p2]]): | |
1049 raise nx.NetworkXError("Probability values for `p1` and `p2` must both be < 1.") | |
1050 | |
1051 # a necessary ingredient in any self-respecting graph library | |
1052 llen = int(2 * seed.random() * n + 0.5) | |
1053 L = path_graph(llen) | |
1054 # build caterpillar: add edges to path graph with probability p1 | |
1055 current_node = llen - 1 | |
1056 for n in range(llen): | |
1057 while seed.random() < p1: # add fuzzy caterpillar parts | |
1058 current_node += 1 | |
1059 L.add_edge(n, current_node) | |
1060 cat_node = current_node | |
1061 while seed.random() < p2: # add crunchy lobster bits | |
1062 current_node += 1 | |
1063 L.add_edge(cat_node, current_node) | |
1064 return L # voila, un lobster! | |
1065 | |
1066 | |
1067 @py_random_state(1) | |
1068 def random_shell_graph(constructor, seed=None): | |
1069 """Returns a random shell graph for the constructor given. | |
1070 | |
1071 Parameters | |
1072 ---------- | |
1073 constructor : list of three-tuples | |
1074 Represents the parameters for a shell, starting at the center | |
1075 shell. Each element of the list must be of the form `(n, m, | |
1076 d)`, where `n` is the number of nodes in the shell, `m` is | |
1077 the number of edges in the shell, and `d` is the ratio of | |
1078 inter-shell (next) edges to intra-shell edges. If `d` is zero, | |
1079 there will be no intra-shell edges, and if `d` is one there | |
1080 will be all possible intra-shell edges. | |
1081 seed : integer, random_state, or None (default) | |
1082 Indicator of random number generation state. | |
1083 See :ref:`Randomness<randomness>`. | |
1084 | |
1085 Examples | |
1086 -------- | |
1087 >>> constructor = [(10, 20, 0.8), (20, 40, 0.8)] | |
1088 >>> G = nx.random_shell_graph(constructor) | |
1089 | |
1090 """ | |
1091 G = empty_graph(0) | |
1092 | |
1093 glist = [] | |
1094 intra_edges = [] | |
1095 nnodes = 0 | |
1096 # create gnm graphs for each shell | |
1097 for (n, m, d) in constructor: | |
1098 inter_edges = int(m * d) | |
1099 intra_edges.append(m - inter_edges) | |
1100 g = nx.convert_node_labels_to_integers( | |
1101 gnm_random_graph(n, inter_edges, seed=seed), first_label=nnodes | |
1102 ) | |
1103 glist.append(g) | |
1104 nnodes += n | |
1105 G = nx.operators.union(G, g) | |
1106 | |
1107 # connect the shells randomly | |
1108 for gi in range(len(glist) - 1): | |
1109 nlist1 = list(glist[gi]) | |
1110 nlist2 = list(glist[gi + 1]) | |
1111 total_edges = intra_edges[gi] | |
1112 edge_count = 0 | |
1113 while edge_count < total_edges: | |
1114 u = seed.choice(nlist1) | |
1115 v = seed.choice(nlist2) | |
1116 if u == v or G.has_edge(u, v): | |
1117 continue | |
1118 else: | |
1119 G.add_edge(u, v) | |
1120 edge_count = edge_count + 1 | |
1121 return G | |
1122 | |
1123 | |
1124 @py_random_state(2) | |
1125 def random_powerlaw_tree(n, gamma=3, seed=None, tries=100): | |
1126 """Returns a tree with a power law degree distribution. | |
1127 | |
1128 Parameters | |
1129 ---------- | |
1130 n : int | |
1131 The number of nodes. | |
1132 gamma : float | |
1133 Exponent of the power law. | |
1134 seed : integer, random_state, or None (default) | |
1135 Indicator of random number generation state. | |
1136 See :ref:`Randomness<randomness>`. | |
1137 tries : int | |
1138 Number of attempts to adjust the sequence to make it a tree. | |
1139 | |
1140 Raises | |
1141 ------ | |
1142 NetworkXError | |
1143 If no valid sequence is found within the maximum number of | |
1144 attempts. | |
1145 | |
1146 Notes | |
1147 ----- | |
1148 A trial power law degree sequence is chosen and then elements are | |
1149 swapped with new elements from a powerlaw distribution until the | |
1150 sequence makes a tree (by checking, for example, that the number of | |
1151 edges is one smaller than the number of nodes). | |
1152 | |
1153 """ | |
1154 # This call may raise a NetworkXError if the number of tries is succeeded. | |
1155 seq = random_powerlaw_tree_sequence(n, gamma=gamma, seed=seed, tries=tries) | |
1156 G = degree_sequence_tree(seq) | |
1157 return G | |
1158 | |
1159 | |
1160 @py_random_state(2) | |
1161 def random_powerlaw_tree_sequence(n, gamma=3, seed=None, tries=100): | |
1162 """Returns a degree sequence for a tree with a power law distribution. | |
1163 | |
1164 Parameters | |
1165 ---------- | |
1166 n : int, | |
1167 The number of nodes. | |
1168 gamma : float | |
1169 Exponent of the power law. | |
1170 seed : integer, random_state, or None (default) | |
1171 Indicator of random number generation state. | |
1172 See :ref:`Randomness<randomness>`. | |
1173 tries : int | |
1174 Number of attempts to adjust the sequence to make it a tree. | |
1175 | |
1176 Raises | |
1177 ------ | |
1178 NetworkXError | |
1179 If no valid sequence is found within the maximum number of | |
1180 attempts. | |
1181 | |
1182 Notes | |
1183 ----- | |
1184 A trial power law degree sequence is chosen and then elements are | |
1185 swapped with new elements from a power law distribution until | |
1186 the sequence makes a tree (by checking, for example, that the number of | |
1187 edges is one smaller than the number of nodes). | |
1188 | |
1189 """ | |
1190 # get trial sequence | |
1191 z = nx.utils.powerlaw_sequence(n, exponent=gamma, seed=seed) | |
1192 # round to integer values in the range [0,n] | |
1193 zseq = [min(n, max(int(round(s)), 0)) for s in z] | |
1194 | |
1195 # another sequence to swap values from | |
1196 z = nx.utils.powerlaw_sequence(tries, exponent=gamma, seed=seed) | |
1197 # round to integer values in the range [0,n] | |
1198 swap = [min(n, max(int(round(s)), 0)) for s in z] | |
1199 | |
1200 for deg in swap: | |
1201 # If this degree sequence can be the degree sequence of a tree, return | |
1202 # it. It can be a tree if the number of edges is one fewer than the | |
1203 # number of nodes, or in other words, `n - sum(zseq) / 2 == 1`. We | |
1204 # use an equivalent condition below that avoids floating point | |
1205 # operations. | |
1206 if 2 * n - sum(zseq) == 2: | |
1207 return zseq | |
1208 index = seed.randint(0, n - 1) | |
1209 zseq[index] = swap.pop() | |
1210 | |
1211 raise nx.NetworkXError( | |
1212 f"Exceeded max ({tries}) attempts for a valid tree sequence." | |
1213 ) | |
1214 | |
1215 | |
1216 @py_random_state(3) | |
1217 def random_kernel_graph(n, kernel_integral, kernel_root=None, seed=None): | |
1218 r"""Returns an random graph based on the specified kernel. | |
1219 | |
1220 The algorithm chooses each of the $[n(n-1)]/2$ possible edges with | |
1221 probability specified by a kernel $\kappa(x,y)$ [1]_. The kernel | |
1222 $\kappa(x,y)$ must be a symmetric (in $x,y$), non-negative, | |
1223 bounded function. | |
1224 | |
1225 Parameters | |
1226 ---------- | |
1227 n : int | |
1228 The number of nodes | |
1229 kernal_integral : function | |
1230 Function that returns the definite integral of the kernel $\kappa(x,y)$, | |
1231 $F(y,a,b) := \int_a^b \kappa(x,y)dx$ | |
1232 kernel_root: function (optional) | |
1233 Function that returns the root $b$ of the equation $F(y,a,b) = r$. | |
1234 If None, the root is found using :func:`scipy.optimize.brentq` | |
1235 (this requires SciPy). | |
1236 seed : integer, random_state, or None (default) | |
1237 Indicator of random number generation state. | |
1238 See :ref:`Randomness<randomness>`. | |
1239 | |
1240 Notes | |
1241 ----- | |
1242 The kernel is specified through its definite integral which must be | |
1243 provided as one of the arguments. If the integral and root of the | |
1244 kernel integral can be found in $O(1)$ time then this algorithm runs in | |
1245 time $O(n+m)$ where m is the expected number of edges [2]_. | |
1246 | |
1247 The nodes are set to integers from $0$ to $n-1$. | |
1248 | |
1249 Examples | |
1250 -------- | |
1251 Generate an Erdős–Rényi random graph $G(n,c/n)$, with kernel | |
1252 $\kappa(x,y)=c$ where $c$ is the mean expected degree. | |
1253 | |
1254 >>> def integral(u, w, z): | |
1255 ... return c * (z - w) | |
1256 >>> def root(u, w, r): | |
1257 ... return r / c + w | |
1258 >>> c = 1 | |
1259 >>> graph = nx.random_kernel_graph(1000, integral, root) | |
1260 | |
1261 See Also | |
1262 -------- | |
1263 gnp_random_graph | |
1264 expected_degree_graph | |
1265 | |
1266 References | |
1267 ---------- | |
1268 .. [1] Bollobás, Béla, Janson, S. and Riordan, O. | |
1269 "The phase transition in inhomogeneous random graphs", | |
1270 *Random Structures Algorithms*, 31, 3--122, 2007. | |
1271 | |
1272 .. [2] Hagberg A, Lemons N (2015), | |
1273 "Fast Generation of Sparse Random Kernel Graphs". | |
1274 PLoS ONE 10(9): e0135177, 2015. doi:10.1371/journal.pone.0135177 | |
1275 """ | |
1276 if kernel_root is None: | |
1277 import scipy.optimize as optimize | |
1278 | |
1279 def kernel_root(y, a, r): | |
1280 def my_function(b): | |
1281 return kernel_integral(y, a, b) - r | |
1282 | |
1283 return optimize.brentq(my_function, a, 1) | |
1284 | |
1285 graph = nx.Graph() | |
1286 graph.add_nodes_from(range(n)) | |
1287 (i, j) = (1, 1) | |
1288 while i < n: | |
1289 r = -math.log(1 - seed.random()) # (1-seed.random()) in (0, 1] | |
1290 if kernel_integral(i / n, j / n, 1) <= r: | |
1291 i, j = i + 1, i + 1 | |
1292 else: | |
1293 j = int(math.ceil(n * kernel_root(i / n, j / n, r))) | |
1294 graph.add_edge(i - 1, j - 1) | |
1295 return graph |