Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/generators/directed.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 some directed graphs, including growing network (GN) graphs and | |
3 scale-free graphs. | |
4 | |
5 """ | |
6 | |
7 from collections import Counter | |
8 | |
9 import networkx as nx | |
10 from networkx.generators.classic import empty_graph | |
11 from networkx.utils import discrete_sequence | |
12 from networkx.utils import weighted_choice | |
13 from networkx.utils import py_random_state | |
14 | |
15 __all__ = [ | |
16 "gn_graph", | |
17 "gnc_graph", | |
18 "gnr_graph", | |
19 "random_k_out_graph", | |
20 "scale_free_graph", | |
21 ] | |
22 | |
23 | |
24 @py_random_state(3) | |
25 def gn_graph(n, kernel=None, create_using=None, seed=None): | |
26 """Returns the growing network (GN) digraph with `n` nodes. | |
27 | |
28 The GN graph is built by adding nodes one at a time with a link to one | |
29 previously added node. The target node for the link is chosen with | |
30 probability based on degree. The default attachment kernel is a linear | |
31 function of the degree of a node. | |
32 | |
33 The graph is always a (directed) tree. | |
34 | |
35 Parameters | |
36 ---------- | |
37 n : int | |
38 The number of nodes for the generated graph. | |
39 kernel : function | |
40 The attachment kernel. | |
41 create_using : NetworkX graph constructor, optional (default DiGraph) | |
42 Graph type to create. If graph instance, then cleared before populated. | |
43 seed : integer, random_state, or None (default) | |
44 Indicator of random number generation state. | |
45 See :ref:`Randomness<randomness>`. | |
46 | |
47 Examples | |
48 -------- | |
49 To create the undirected GN graph, use the :meth:`~DiGraph.to_directed` | |
50 method:: | |
51 | |
52 >>> D = nx.gn_graph(10) # the GN graph | |
53 >>> G = D.to_undirected() # the undirected version | |
54 | |
55 To specify an attachment kernel, use the `kernel` keyword argument:: | |
56 | |
57 >>> D = nx.gn_graph(10, kernel=lambda x: x ** 1.5) # A_k = k^1.5 | |
58 | |
59 References | |
60 ---------- | |
61 .. [1] P. L. Krapivsky and S. Redner, | |
62 Organization of Growing Random Networks, | |
63 Phys. Rev. E, 63, 066123, 2001. | |
64 """ | |
65 G = empty_graph(1, create_using, default=nx.DiGraph) | |
66 if not G.is_directed(): | |
67 raise nx.NetworkXError("create_using must indicate a Directed Graph") | |
68 | |
69 if kernel is None: | |
70 | |
71 def kernel(x): | |
72 return x | |
73 | |
74 if n == 1: | |
75 return G | |
76 | |
77 G.add_edge(1, 0) # get started | |
78 ds = [1, 1] # degree sequence | |
79 | |
80 for source in range(2, n): | |
81 # compute distribution from kernel and degree | |
82 dist = [kernel(d) for d in ds] | |
83 # choose target from discrete distribution | |
84 target = discrete_sequence(1, distribution=dist, seed=seed)[0] | |
85 G.add_edge(source, target) | |
86 ds.append(1) # the source has only one link (degree one) | |
87 ds[target] += 1 # add one to the target link degree | |
88 return G | |
89 | |
90 | |
91 @py_random_state(3) | |
92 def gnr_graph(n, p, create_using=None, seed=None): | |
93 """Returns the growing network with redirection (GNR) digraph with `n` | |
94 nodes and redirection probability `p`. | |
95 | |
96 The GNR graph is built by adding nodes one at a time with a link to one | |
97 previously added node. The previous target node is chosen uniformly at | |
98 random. With probabiliy `p` the link is instead "redirected" to the | |
99 successor node of the target. | |
100 | |
101 The graph is always a (directed) tree. | |
102 | |
103 Parameters | |
104 ---------- | |
105 n : int | |
106 The number of nodes for the generated graph. | |
107 p : float | |
108 The redirection probability. | |
109 create_using : NetworkX graph constructor, optional (default DiGraph) | |
110 Graph type to create. If graph instance, then cleared before populated. | |
111 seed : integer, random_state, or None (default) | |
112 Indicator of random number generation state. | |
113 See :ref:`Randomness<randomness>`. | |
114 | |
115 Examples | |
116 -------- | |
117 To create the undirected GNR graph, use the :meth:`~DiGraph.to_directed` | |
118 method:: | |
119 | |
120 >>> D = nx.gnr_graph(10, 0.5) # the GNR graph | |
121 >>> G = D.to_undirected() # the undirected version | |
122 | |
123 References | |
124 ---------- | |
125 .. [1] P. L. Krapivsky and S. Redner, | |
126 Organization of Growing Random Networks, | |
127 Phys. Rev. E, 63, 066123, 2001. | |
128 """ | |
129 G = empty_graph(1, create_using, default=nx.DiGraph) | |
130 if not G.is_directed(): | |
131 raise nx.NetworkXError("create_using must indicate a Directed Graph") | |
132 | |
133 if n == 1: | |
134 return G | |
135 | |
136 for source in range(1, n): | |
137 target = seed.randrange(0, source) | |
138 if seed.random() < p and target != 0: | |
139 target = next(G.successors(target)) | |
140 G.add_edge(source, target) | |
141 return G | |
142 | |
143 | |
144 @py_random_state(2) | |
145 def gnc_graph(n, create_using=None, seed=None): | |
146 """Returns the growing network with copying (GNC) digraph with `n` nodes. | |
147 | |
148 The GNC graph is built by adding nodes one at a time with a link to one | |
149 previously added node (chosen uniformly at random) and to all of that | |
150 node's successors. | |
151 | |
152 Parameters | |
153 ---------- | |
154 n : int | |
155 The number of nodes for the generated graph. | |
156 create_using : NetworkX graph constructor, optional (default DiGraph) | |
157 Graph type to create. If graph instance, then cleared before populated. | |
158 seed : integer, random_state, or None (default) | |
159 Indicator of random number generation state. | |
160 See :ref:`Randomness<randomness>`. | |
161 | |
162 References | |
163 ---------- | |
164 .. [1] P. L. Krapivsky and S. Redner, | |
165 Network Growth by Copying, | |
166 Phys. Rev. E, 71, 036118, 2005k.}, | |
167 """ | |
168 G = empty_graph(1, create_using, default=nx.DiGraph) | |
169 if not G.is_directed(): | |
170 raise nx.NetworkXError("create_using must indicate a Directed Graph") | |
171 | |
172 if n == 1: | |
173 return G | |
174 | |
175 for source in range(1, n): | |
176 target = seed.randrange(0, source) | |
177 for succ in G.successors(target): | |
178 G.add_edge(source, succ) | |
179 G.add_edge(source, target) | |
180 return G | |
181 | |
182 | |
183 @py_random_state(7) | |
184 def scale_free_graph( | |
185 n, | |
186 alpha=0.41, | |
187 beta=0.54, | |
188 gamma=0.05, | |
189 delta_in=0.2, | |
190 delta_out=0, | |
191 create_using=None, | |
192 seed=None, | |
193 ): | |
194 """Returns a scale-free directed graph. | |
195 | |
196 Parameters | |
197 ---------- | |
198 n : integer | |
199 Number of nodes in graph | |
200 alpha : float | |
201 Probability for adding a new node connected to an existing node | |
202 chosen randomly according to the in-degree distribution. | |
203 beta : float | |
204 Probability for adding an edge between two existing nodes. | |
205 One existing node is chosen randomly according the in-degree | |
206 distribution and the other chosen randomly according to the out-degree | |
207 distribution. | |
208 gamma : float | |
209 Probability for adding a new node connected to an existing node | |
210 chosen randomly according to the out-degree distribution. | |
211 delta_in : float | |
212 Bias for choosing nodes from in-degree distribution. | |
213 delta_out : float | |
214 Bias for choosing nodes from out-degree distribution. | |
215 create_using : NetworkX graph constructor, optional | |
216 The default is a MultiDiGraph 3-cycle. | |
217 If a graph instance, use it without clearing first. | |
218 If a graph constructor, call it to construct an empty graph. | |
219 seed : integer, random_state, or None (default) | |
220 Indicator of random number generation state. | |
221 See :ref:`Randomness<randomness>`. | |
222 | |
223 Examples | |
224 -------- | |
225 Create a scale-free graph on one hundred nodes:: | |
226 | |
227 >>> G = nx.scale_free_graph(100) | |
228 | |
229 Notes | |
230 ----- | |
231 The sum of `alpha`, `beta`, and `gamma` must be 1. | |
232 | |
233 References | |
234 ---------- | |
235 .. [1] B. Bollobás, C. Borgs, J. Chayes, and O. Riordan, | |
236 Directed scale-free graphs, | |
237 Proceedings of the fourteenth annual ACM-SIAM Symposium on | |
238 Discrete Algorithms, 132--139, 2003. | |
239 """ | |
240 | |
241 def _choose_node(G, distribution, delta, psum): | |
242 cumsum = 0.0 | |
243 # normalization | |
244 r = seed.random() | |
245 for n, d in distribution: | |
246 cumsum += (d + delta) / psum | |
247 if r < cumsum: | |
248 break | |
249 return n | |
250 | |
251 if create_using is None or not hasattr(create_using, "_adj"): | |
252 # start with 3-cycle | |
253 G = nx.empty_graph(3, create_using, default=nx.MultiDiGraph) | |
254 G.add_edges_from([(0, 1), (1, 2), (2, 0)]) | |
255 else: | |
256 G = create_using | |
257 if not (G.is_directed() and G.is_multigraph()): | |
258 raise nx.NetworkXError("MultiDiGraph required in create_using") | |
259 | |
260 if alpha <= 0: | |
261 raise ValueError("alpha must be > 0.") | |
262 if beta <= 0: | |
263 raise ValueError("beta must be > 0.") | |
264 if gamma <= 0: | |
265 raise ValueError("gamma must be > 0.") | |
266 | |
267 if abs(alpha + beta + gamma - 1.0) >= 1e-9: | |
268 raise ValueError("alpha+beta+gamma must equal 1.") | |
269 | |
270 number_of_edges = G.number_of_edges() | |
271 while len(G) < n: | |
272 psum_in = number_of_edges + delta_in * len(G) | |
273 psum_out = number_of_edges + delta_out * len(G) | |
274 r = seed.random() | |
275 # random choice in alpha,beta,gamma ranges | |
276 if r < alpha: | |
277 # alpha | |
278 # add new node v | |
279 v = len(G) | |
280 # choose w according to in-degree and delta_in | |
281 w = _choose_node(G, G.in_degree(), delta_in, psum_in) | |
282 elif r < alpha + beta: | |
283 # beta | |
284 # choose v according to out-degree and delta_out | |
285 v = _choose_node(G, G.out_degree(), delta_out, psum_out) | |
286 # choose w according to in-degree and delta_in | |
287 w = _choose_node(G, G.in_degree(), delta_in, psum_in) | |
288 else: | |
289 # gamma | |
290 # choose v according to out-degree and delta_out | |
291 v = _choose_node(G, G.out_degree(), delta_out, psum_out) | |
292 # add new node w | |
293 w = len(G) | |
294 G.add_edge(v, w) | |
295 number_of_edges += 1 | |
296 return G | |
297 | |
298 | |
299 @py_random_state(4) | |
300 def random_uniform_k_out_graph(n, k, self_loops=True, with_replacement=True, seed=None): | |
301 """Returns a random `k`-out graph with uniform attachment. | |
302 | |
303 A random `k`-out graph with uniform attachment is a multidigraph | |
304 generated by the following algorithm. For each node *u*, choose | |
305 `k` nodes *v* uniformly at random (with replacement). Add a | |
306 directed edge joining *u* to *v*. | |
307 | |
308 Parameters | |
309 ---------- | |
310 n : int | |
311 The number of nodes in the returned graph. | |
312 | |
313 k : int | |
314 The out-degree of each node in the returned graph. | |
315 | |
316 self_loops : bool | |
317 If True, self-loops are allowed when generating the graph. | |
318 | |
319 with_replacement : bool | |
320 If True, neighbors are chosen with replacement and the | |
321 returned graph will be a directed multigraph. Otherwise, | |
322 neighbors are chosen without replacement and the returned graph | |
323 will be a directed graph. | |
324 | |
325 seed : integer, random_state, or None (default) | |
326 Indicator of random number generation state. | |
327 See :ref:`Randomness<randomness>`. | |
328 | |
329 Returns | |
330 ------- | |
331 NetworkX graph | |
332 A `k`-out-regular directed graph generated according to the | |
333 above algorithm. It will be a multigraph if and only if | |
334 `with_replacement` is True. | |
335 | |
336 Raises | |
337 ------ | |
338 ValueError | |
339 If `with_replacement` is False and `k` is greater than | |
340 `n`. | |
341 | |
342 See also | |
343 -------- | |
344 random_k_out_graph | |
345 | |
346 Notes | |
347 ----- | |
348 The return digraph or multidigraph may not be strongly connected, or | |
349 even weakly connected. | |
350 | |
351 If `with_replacement` is True, this function is similar to | |
352 :func:`random_k_out_graph`, if that function had parameter `alpha` | |
353 set to positive infinity. | |
354 | |
355 """ | |
356 if with_replacement: | |
357 create_using = nx.MultiDiGraph() | |
358 | |
359 def sample(v, nodes): | |
360 if not self_loops: | |
361 nodes = nodes - {v} | |
362 return (seed.choice(list(nodes)) for i in range(k)) | |
363 | |
364 else: | |
365 create_using = nx.DiGraph() | |
366 | |
367 def sample(v, nodes): | |
368 if not self_loops: | |
369 nodes = nodes - {v} | |
370 return seed.sample(nodes, k) | |
371 | |
372 G = nx.empty_graph(n, create_using) | |
373 nodes = set(G) | |
374 for u in G: | |
375 G.add_edges_from((u, v) for v in sample(u, nodes)) | |
376 return G | |
377 | |
378 | |
379 @py_random_state(4) | |
380 def random_k_out_graph(n, k, alpha, self_loops=True, seed=None): | |
381 """Returns a random `k`-out graph with preferential attachment. | |
382 | |
383 A random `k`-out graph with preferential attachment is a | |
384 multidigraph generated by the following algorithm. | |
385 | |
386 1. Begin with an empty digraph, and initially set each node to have | |
387 weight `alpha`. | |
388 2. Choose a node `u` with out-degree less than `k` uniformly at | |
389 random. | |
390 3. Choose a node `v` from with probability proportional to its | |
391 weight. | |
392 4. Add a directed edge from `u` to `v`, and increase the weight | |
393 of `v` by one. | |
394 5. If each node has out-degree `k`, halt, otherwise repeat from | |
395 step 2. | |
396 | |
397 For more information on this model of random graph, see [1]. | |
398 | |
399 Parameters | |
400 ---------- | |
401 n : int | |
402 The number of nodes in the returned graph. | |
403 | |
404 k : int | |
405 The out-degree of each node in the returned graph. | |
406 | |
407 alpha : float | |
408 A positive :class:`float` representing the initial weight of | |
409 each vertex. A higher number means that in step 3 above, nodes | |
410 will be chosen more like a true uniformly random sample, and a | |
411 lower number means that nodes are more likely to be chosen as | |
412 their in-degree increases. If this parameter is not positive, a | |
413 :exc:`ValueError` is raised. | |
414 | |
415 self_loops : bool | |
416 If True, self-loops are allowed when generating the graph. | |
417 | |
418 seed : integer, random_state, or None (default) | |
419 Indicator of random number generation state. | |
420 See :ref:`Randomness<randomness>`. | |
421 | |
422 Returns | |
423 ------- | |
424 :class:`~networkx.classes.MultiDiGraph` | |
425 A `k`-out-regular multidigraph generated according to the above | |
426 algorithm. | |
427 | |
428 Raises | |
429 ------ | |
430 ValueError | |
431 If `alpha` is not positive. | |
432 | |
433 Notes | |
434 ----- | |
435 The returned multidigraph may not be strongly connected, or even | |
436 weakly connected. | |
437 | |
438 References | |
439 ---------- | |
440 [1]: Peterson, Nicholas R., and Boris Pittel. | |
441 "Distance between two random `k`-out digraphs, with and without | |
442 preferential attachment." | |
443 arXiv preprint arXiv:1311.5961 (2013). | |
444 <https://arxiv.org/abs/1311.5961> | |
445 | |
446 """ | |
447 if alpha < 0: | |
448 raise ValueError("alpha must be positive") | |
449 G = nx.empty_graph(n, create_using=nx.MultiDiGraph) | |
450 weights = Counter({v: alpha for v in G}) | |
451 for i in range(k * n): | |
452 u = seed.choice([v for v, d in G.out_degree() if d < k]) | |
453 # If self-loops are not allowed, make the source node `u` have | |
454 # weight zero. | |
455 if not self_loops: | |
456 adjustment = Counter({u: weights[u]}) | |
457 else: | |
458 adjustment = Counter() | |
459 v = weighted_choice(weights - adjustment, seed=seed) | |
460 G.add_edge(u, v) | |
461 weights[v] += 1 | |
462 return G |