Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/generators/directed.py: 17%
141 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""
2Generators for some directed graphs, including growing network (GN) graphs and
3scale-free graphs.
5"""
7import numbers
8from collections import Counter
10import networkx as nx
11from networkx.generators.classic import empty_graph
12from networkx.utils import discrete_sequence, py_random_state, weighted_choice
14__all__ = [
15 "gn_graph",
16 "gnc_graph",
17 "gnr_graph",
18 "random_k_out_graph",
19 "scale_free_graph",
20]
23@py_random_state(3)
24@nx._dispatch(graphs=None)
25def gn_graph(n, kernel=None, create_using=None, seed=None):
26 """Returns the growing network (GN) digraph with `n` nodes.
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.
33 The graph is always a (directed) tree.
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>`.
47 Examples
48 --------
49 To create the undirected GN graph, use the :meth:`~DiGraph.to_directed`
50 method::
52 >>> D = nx.gn_graph(10) # the GN graph
53 >>> G = D.to_undirected() # the undirected version
55 To specify an attachment kernel, use the `kernel` keyword argument::
57 >>> D = nx.gn_graph(10, kernel=lambda x: x ** 1.5) # A_k = k^1.5
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")
69 if kernel is None:
71 def kernel(x):
72 return x
74 if n == 1:
75 return G
77 G.add_edge(1, 0) # get started
78 ds = [1, 1] # degree sequence
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
91@py_random_state(3)
92@nx._dispatch(graphs=None)
93def gnr_graph(n, p, create_using=None, seed=None):
94 """Returns the growing network with redirection (GNR) digraph with `n`
95 nodes and redirection probability `p`.
97 The GNR graph is built by adding nodes one at a time with a link to one
98 previously added node. The previous target node is chosen uniformly at
99 random. With probability `p` the link is instead "redirected" to the
100 successor node of the target.
102 The graph is always a (directed) tree.
104 Parameters
105 ----------
106 n : int
107 The number of nodes for the generated graph.
108 p : float
109 The redirection probability.
110 create_using : NetworkX graph constructor, optional (default DiGraph)
111 Graph type to create. If graph instance, then cleared before populated.
112 seed : integer, random_state, or None (default)
113 Indicator of random number generation state.
114 See :ref:`Randomness<randomness>`.
116 Examples
117 --------
118 To create the undirected GNR graph, use the :meth:`~DiGraph.to_directed`
119 method::
121 >>> D = nx.gnr_graph(10, 0.5) # the GNR graph
122 >>> G = D.to_undirected() # the undirected version
124 References
125 ----------
126 .. [1] P. L. Krapivsky and S. Redner,
127 Organization of Growing Random Networks,
128 Phys. Rev. E, 63, 066123, 2001.
129 """
130 G = empty_graph(1, create_using, default=nx.DiGraph)
131 if not G.is_directed():
132 raise nx.NetworkXError("create_using must indicate a Directed Graph")
134 if n == 1:
135 return G
137 for source in range(1, n):
138 target = seed.randrange(0, source)
139 if seed.random() < p and target != 0:
140 target = next(G.successors(target))
141 G.add_edge(source, target)
142 return G
145@py_random_state(2)
146@nx._dispatch(graphs=None)
147def gnc_graph(n, create_using=None, seed=None):
148 """Returns the growing network with copying (GNC) digraph with `n` nodes.
150 The GNC graph is built by adding nodes one at a time with a link to one
151 previously added node (chosen uniformly at random) and to all of that
152 node's successors.
154 Parameters
155 ----------
156 n : int
157 The number of nodes for the generated graph.
158 create_using : NetworkX graph constructor, optional (default DiGraph)
159 Graph type to create. If graph instance, then cleared before populated.
160 seed : integer, random_state, or None (default)
161 Indicator of random number generation state.
162 See :ref:`Randomness<randomness>`.
164 References
165 ----------
166 .. [1] P. L. Krapivsky and S. Redner,
167 Network Growth by Copying,
168 Phys. Rev. E, 71, 036118, 2005k.},
169 """
170 G = empty_graph(1, create_using, default=nx.DiGraph)
171 if not G.is_directed():
172 raise nx.NetworkXError("create_using must indicate a Directed Graph")
174 if n == 1:
175 return G
177 for source in range(1, n):
178 target = seed.randrange(0, source)
179 for succ in G.successors(target):
180 G.add_edge(source, succ)
181 G.add_edge(source, target)
182 return G
185@py_random_state(6)
186@nx._dispatch(graphs=None)
187def scale_free_graph(
188 n,
189 alpha=0.41,
190 beta=0.54,
191 gamma=0.05,
192 delta_in=0.2,
193 delta_out=0,
194 seed=None,
195 initial_graph=None,
196):
197 """Returns a scale-free directed graph.
199 Parameters
200 ----------
201 n : integer
202 Number of nodes in graph
203 alpha : float
204 Probability for adding a new node connected to an existing node
205 chosen randomly according to the in-degree distribution.
206 beta : float
207 Probability for adding an edge between two existing nodes.
208 One existing node is chosen randomly according the in-degree
209 distribution and the other chosen randomly according to the out-degree
210 distribution.
211 gamma : float
212 Probability for adding a new node connected to an existing node
213 chosen randomly according to the out-degree distribution.
214 delta_in : float
215 Bias for choosing nodes from in-degree distribution.
216 delta_out : float
217 Bias for choosing nodes from out-degree distribution.
218 seed : integer, random_state, or None (default)
219 Indicator of random number generation state.
220 See :ref:`Randomness<randomness>`.
221 initial_graph : MultiDiGraph instance, optional
222 Build the scale-free graph starting from this initial MultiDiGraph,
223 if provided.
225 Returns
226 -------
227 MultiDiGraph
229 Examples
230 --------
231 Create a scale-free graph on one hundred nodes::
233 >>> G = nx.scale_free_graph(100)
235 Notes
236 -----
237 The sum of `alpha`, `beta`, and `gamma` must be 1.
239 References
240 ----------
241 .. [1] B. Bollobás, C. Borgs, J. Chayes, and O. Riordan,
242 Directed scale-free graphs,
243 Proceedings of the fourteenth annual ACM-SIAM Symposium on
244 Discrete Algorithms, 132--139, 2003.
245 """
247 def _choose_node(candidates, node_list, delta):
248 if delta > 0:
249 bias_sum = len(node_list) * delta
250 p_delta = bias_sum / (bias_sum + len(candidates))
251 if seed.random() < p_delta:
252 return seed.choice(node_list)
253 return seed.choice(candidates)
255 if initial_graph is not None and hasattr(initial_graph, "_adj"):
256 if not isinstance(initial_graph, nx.MultiDiGraph):
257 raise nx.NetworkXError("initial_graph must be a MultiDiGraph.")
258 G = initial_graph
259 else:
260 # Start with 3-cycle
261 G = nx.MultiDiGraph([(0, 1), (1, 2), (2, 0)])
263 if alpha <= 0:
264 raise ValueError("alpha must be > 0.")
265 if beta <= 0:
266 raise ValueError("beta must be > 0.")
267 if gamma <= 0:
268 raise ValueError("gamma must be > 0.")
270 if abs(alpha + beta + gamma - 1.0) >= 1e-9:
271 raise ValueError("alpha+beta+gamma must equal 1.")
273 if delta_in < 0:
274 raise ValueError("delta_in must be >= 0.")
276 if delta_out < 0:
277 raise ValueError("delta_out must be >= 0.")
279 # pre-populate degree states
280 vs = sum((count * [idx] for idx, count in G.out_degree()), [])
281 ws = sum((count * [idx] for idx, count in G.in_degree()), [])
283 # pre-populate node state
284 node_list = list(G.nodes())
286 # see if there already are number-based nodes
287 numeric_nodes = [n for n in node_list if isinstance(n, numbers.Number)]
288 if len(numeric_nodes) > 0:
289 # set cursor for new nodes appropriately
290 cursor = max(int(n.real) for n in numeric_nodes) + 1
291 else:
292 # or start at zero
293 cursor = 0
295 while len(G) < n:
296 r = seed.random()
298 # random choice in alpha,beta,gamma ranges
299 if r < alpha:
300 # alpha
301 # add new node v
302 v = cursor
303 cursor += 1
304 # also add to node state
305 node_list.append(v)
306 # choose w according to in-degree and delta_in
307 w = _choose_node(ws, node_list, delta_in)
309 elif r < alpha + beta:
310 # beta
311 # choose v according to out-degree and delta_out
312 v = _choose_node(vs, node_list, delta_out)
313 # choose w according to in-degree and delta_in
314 w = _choose_node(ws, node_list, delta_in)
316 else:
317 # gamma
318 # choose v according to out-degree and delta_out
319 v = _choose_node(vs, node_list, delta_out)
320 # add new node w
321 w = cursor
322 cursor += 1
323 # also add to node state
324 node_list.append(w)
326 # add edge to graph
327 G.add_edge(v, w)
329 # update degree states
330 vs.append(v)
331 ws.append(w)
333 return G
336@py_random_state(4)
337@nx._dispatch(graphs=None)
338def random_uniform_k_out_graph(n, k, self_loops=True, with_replacement=True, seed=None):
339 """Returns a random `k`-out graph with uniform attachment.
341 A random `k`-out graph with uniform attachment is a multidigraph
342 generated by the following algorithm. For each node *u*, choose
343 `k` nodes *v* uniformly at random (with replacement). Add a
344 directed edge joining *u* to *v*.
346 Parameters
347 ----------
348 n : int
349 The number of nodes in the returned graph.
351 k : int
352 The out-degree of each node in the returned graph.
354 self_loops : bool
355 If True, self-loops are allowed when generating the graph.
357 with_replacement : bool
358 If True, neighbors are chosen with replacement and the
359 returned graph will be a directed multigraph. Otherwise,
360 neighbors are chosen without replacement and the returned graph
361 will be a directed graph.
363 seed : integer, random_state, or None (default)
364 Indicator of random number generation state.
365 See :ref:`Randomness<randomness>`.
367 Returns
368 -------
369 NetworkX graph
370 A `k`-out-regular directed graph generated according to the
371 above algorithm. It will be a multigraph if and only if
372 `with_replacement` is True.
374 Raises
375 ------
376 ValueError
377 If `with_replacement` is False and `k` is greater than
378 `n`.
380 See also
381 --------
382 random_k_out_graph
384 Notes
385 -----
386 The return digraph or multidigraph may not be strongly connected, or
387 even weakly connected.
389 If `with_replacement` is True, this function is similar to
390 :func:`random_k_out_graph`, if that function had parameter `alpha`
391 set to positive infinity.
393 """
394 if with_replacement:
395 create_using = nx.MultiDiGraph()
397 def sample(v, nodes):
398 if not self_loops:
399 nodes = nodes - {v}
400 return (seed.choice(list(nodes)) for i in range(k))
402 else:
403 create_using = nx.DiGraph()
405 def sample(v, nodes):
406 if not self_loops:
407 nodes = nodes - {v}
408 return seed.sample(list(nodes), k)
410 G = nx.empty_graph(n, create_using)
411 nodes = set(G)
412 for u in G:
413 G.add_edges_from((u, v) for v in sample(u, nodes))
414 return G
417@py_random_state(4)
418@nx._dispatch(graphs=None)
419def random_k_out_graph(n, k, alpha, self_loops=True, seed=None):
420 """Returns a random `k`-out graph with preferential attachment.
422 A random `k`-out graph with preferential attachment is a
423 multidigraph generated by the following algorithm.
425 1. Begin with an empty digraph, and initially set each node to have
426 weight `alpha`.
427 2. Choose a node `u` with out-degree less than `k` uniformly at
428 random.
429 3. Choose a node `v` from with probability proportional to its
430 weight.
431 4. Add a directed edge from `u` to `v`, and increase the weight
432 of `v` by one.
433 5. If each node has out-degree `k`, halt, otherwise repeat from
434 step 2.
436 For more information on this model of random graph, see [1].
438 Parameters
439 ----------
440 n : int
441 The number of nodes in the returned graph.
443 k : int
444 The out-degree of each node in the returned graph.
446 alpha : float
447 A positive :class:`float` representing the initial weight of
448 each vertex. A higher number means that in step 3 above, nodes
449 will be chosen more like a true uniformly random sample, and a
450 lower number means that nodes are more likely to be chosen as
451 their in-degree increases. If this parameter is not positive, a
452 :exc:`ValueError` is raised.
454 self_loops : bool
455 If True, self-loops are allowed when generating the graph.
457 seed : integer, random_state, or None (default)
458 Indicator of random number generation state.
459 See :ref:`Randomness<randomness>`.
461 Returns
462 -------
463 :class:`~networkx.classes.MultiDiGraph`
464 A `k`-out-regular multidigraph generated according to the above
465 algorithm.
467 Raises
468 ------
469 ValueError
470 If `alpha` is not positive.
472 Notes
473 -----
474 The returned multidigraph may not be strongly connected, or even
475 weakly connected.
477 References
478 ----------
479 [1]: Peterson, Nicholas R., and Boris Pittel.
480 "Distance between two random `k`-out digraphs, with and without
481 preferential attachment."
482 arXiv preprint arXiv:1311.5961 (2013).
483 <https://arxiv.org/abs/1311.5961>
485 """
486 if alpha < 0:
487 raise ValueError("alpha must be positive")
488 G = nx.empty_graph(n, create_using=nx.MultiDiGraph)
489 weights = Counter({v: alpha for v in G})
490 for i in range(k * n):
491 u = seed.choice([v for v, d in G.out_degree() if d < k])
492 # If self-loops are not allowed, make the source node `u` have
493 # weight zero.
494 if not self_loops:
495 adjustment = Counter({u: weights[u]})
496 else:
497 adjustment = Counter()
498 v = weighted_choice(weights - adjustment, seed=seed)
499 G.add_edge(u, v)
500 weights[v] += 1
501 return G