Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
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 (
13 discrete_sequence,
14 np_random_state,
15 py_random_state,
16 weighted_choice,
17)
19__all__ = [
20 "gn_graph",
21 "gnc_graph",
22 "gnr_graph",
23 "random_k_out_graph",
24 "scale_free_graph",
25]
28@py_random_state(3)
29@nx._dispatchable(graphs=None, returns_graph=True)
30def gn_graph(n, kernel=None, create_using=None, seed=None):
31 """Returns the growing network (GN) digraph with `n` nodes.
33 The GN graph is built by adding nodes one at a time with a link to one
34 previously added node. The target node for the link is chosen with
35 probability based on degree. The default attachment kernel is a linear
36 function of the degree of a node.
38 The graph is always a (directed) tree.
40 Parameters
41 ----------
42 n : int
43 The number of nodes for the generated graph.
44 kernel : function
45 The attachment kernel.
46 create_using : NetworkX graph constructor, optional (default DiGraph)
47 Graph type to create. If graph instance, then cleared before populated.
48 seed : integer, random_state, or None (default)
49 Indicator of random number generation state.
50 See :ref:`Randomness<randomness>`.
52 Examples
53 --------
54 To create the undirected GN graph, use the :meth:`~DiGraph.to_directed`
55 method::
57 >>> D = nx.gn_graph(10) # the GN graph
58 >>> G = D.to_undirected() # the undirected version
60 To specify an attachment kernel, use the `kernel` keyword argument::
62 >>> D = nx.gn_graph(10, kernel=lambda x: x**1.5) # A_k = k^1.5
64 References
65 ----------
66 .. [1] P. L. Krapivsky and S. Redner,
67 Organization of Growing Random Networks,
68 Phys. Rev. E, 63, 066123, 2001.
69 """
70 G = empty_graph(1, create_using, default=nx.DiGraph)
71 if not G.is_directed():
72 raise nx.NetworkXError("create_using must indicate a Directed Graph")
74 if kernel is None:
76 def kernel(x):
77 return x
79 if n == 1:
80 return G
82 G.add_edge(1, 0) # get started
83 ds = [1, 1] # degree sequence
85 for source in range(2, n):
86 # compute distribution from kernel and degree
87 dist = [kernel(d) for d in ds]
88 # choose target from discrete distribution
89 target = discrete_sequence(1, distribution=dist, seed=seed)[0]
90 G.add_edge(source, target)
91 ds.append(1) # the source has only one link (degree one)
92 ds[target] += 1 # add one to the target link degree
93 return G
96@py_random_state(3)
97@nx._dispatchable(graphs=None, returns_graph=True)
98def gnr_graph(n, p, create_using=None, seed=None):
99 """Returns the growing network with redirection (GNR) digraph with `n`
100 nodes and redirection probability `p`.
102 The GNR graph is built by adding nodes one at a time with a link to one
103 previously added node. The previous target node is chosen uniformly at
104 random. With probability `p` the link is instead "redirected" to the
105 successor node of the target.
107 The graph is always a (directed) tree.
109 Parameters
110 ----------
111 n : int
112 The number of nodes for the generated graph.
113 p : float
114 The redirection probability.
115 create_using : NetworkX graph constructor, optional (default DiGraph)
116 Graph type to create. If graph instance, then cleared before populated.
117 seed : integer, random_state, or None (default)
118 Indicator of random number generation state.
119 See :ref:`Randomness<randomness>`.
121 Examples
122 --------
123 To create the undirected GNR graph, use the :meth:`~DiGraph.to_directed`
124 method::
126 >>> D = nx.gnr_graph(10, 0.5) # the GNR graph
127 >>> G = D.to_undirected() # the undirected version
129 References
130 ----------
131 .. [1] P. L. Krapivsky and S. Redner,
132 Organization of Growing Random Networks,
133 Phys. Rev. E, 63, 066123, 2001.
134 """
135 G = empty_graph(1, create_using, default=nx.DiGraph)
136 if not G.is_directed():
137 raise nx.NetworkXError("create_using must indicate a Directed Graph")
139 if n == 1:
140 return G
142 for source in range(1, n):
143 target = seed.randrange(0, source)
144 if seed.random() < p and target != 0:
145 target = next(G.successors(target))
146 G.add_edge(source, target)
147 return G
150@py_random_state(2)
151@nx._dispatchable(graphs=None, returns_graph=True)
152def gnc_graph(n, create_using=None, seed=None):
153 """Returns the growing network with copying (GNC) digraph with `n` nodes.
155 The GNC graph is built by adding nodes one at a time with a link to one
156 previously added node (chosen uniformly at random) and to all of that
157 node's successors.
159 Parameters
160 ----------
161 n : int
162 The number of nodes for the generated graph.
163 create_using : NetworkX graph constructor, optional (default DiGraph)
164 Graph type to create. If graph instance, then cleared before populated.
165 seed : integer, random_state, or None (default)
166 Indicator of random number generation state.
167 See :ref:`Randomness<randomness>`.
169 References
170 ----------
171 .. [1] P. L. Krapivsky and S. Redner,
172 Network Growth by Copying,
173 Phys. Rev. E, 71, 036118, 2005k.},
174 """
175 G = empty_graph(1, create_using, default=nx.DiGraph)
176 if not G.is_directed():
177 raise nx.NetworkXError("create_using must indicate a Directed Graph")
179 if n == 1:
180 return G
182 for source in range(1, n):
183 target = seed.randrange(0, source)
184 for succ in G.successors(target):
185 G.add_edge(source, succ)
186 G.add_edge(source, target)
187 return G
190@py_random_state(6)
191@nx._dispatchable(graphs=None, returns_graph=True)
192def scale_free_graph(
193 n,
194 alpha=0.41,
195 beta=0.54,
196 gamma=0.05,
197 delta_in=0.2,
198 delta_out=0,
199 seed=None,
200 initial_graph=None,
201):
202 """Returns a scale-free directed graph.
204 Parameters
205 ----------
206 n : integer
207 Number of nodes in graph
208 alpha : float
209 Probability for adding a new node connected to an existing node
210 chosen randomly according to the in-degree distribution.
211 beta : float
212 Probability for adding an edge between two existing nodes.
213 One existing node is chosen randomly according the in-degree
214 distribution and the other chosen randomly according to the out-degree
215 distribution.
216 gamma : float
217 Probability for adding a new node connected to an existing node
218 chosen randomly according to the out-degree distribution.
219 delta_in : float
220 Bias for choosing nodes from in-degree distribution.
221 delta_out : float
222 Bias for choosing nodes from out-degree distribution.
223 seed : integer, random_state, or None (default)
224 Indicator of random number generation state.
225 See :ref:`Randomness<randomness>`.
226 initial_graph : MultiDiGraph instance, optional
227 Build the scale-free graph starting from this initial MultiDiGraph,
228 if provided.
230 Returns
231 -------
232 MultiDiGraph
234 Examples
235 --------
236 Create a scale-free graph on one hundred nodes::
238 >>> G = nx.scale_free_graph(100)
240 Notes
241 -----
242 The sum of `alpha`, `beta`, and `gamma` must be 1.
244 References
245 ----------
246 .. [1] B. Bollobás, C. Borgs, J. Chayes, and O. Riordan,
247 Directed scale-free graphs,
248 Proceedings of the fourteenth annual ACM-SIAM Symposium on
249 Discrete Algorithms, 132--139, 2003.
250 """
252 def _choose_node(candidates, node_list, delta):
253 if delta > 0:
254 bias_sum = len(node_list) * delta
255 p_delta = bias_sum / (bias_sum + len(candidates))
256 if seed.random() < p_delta:
257 return seed.choice(node_list)
258 return seed.choice(candidates)
260 if initial_graph is not None and hasattr(initial_graph, "_adj"):
261 if not isinstance(initial_graph, nx.MultiDiGraph):
262 raise nx.NetworkXError("initial_graph must be a MultiDiGraph.")
263 G = initial_graph
264 else:
265 # Start with 3-cycle
266 G = nx.MultiDiGraph([(0, 1), (1, 2), (2, 0)])
268 if alpha <= 0:
269 raise ValueError("alpha must be > 0.")
270 if beta <= 0:
271 raise ValueError("beta must be > 0.")
272 if gamma <= 0:
273 raise ValueError("gamma must be > 0.")
275 if abs(alpha + beta + gamma - 1.0) >= 1e-9:
276 raise ValueError("alpha+beta+gamma must equal 1.")
278 if delta_in < 0:
279 raise ValueError("delta_in must be >= 0.")
281 if delta_out < 0:
282 raise ValueError("delta_out must be >= 0.")
284 # pre-populate degree states
285 vs = sum((count * [idx] for idx, count in G.out_degree()), [])
286 ws = sum((count * [idx] for idx, count in G.in_degree()), [])
288 # pre-populate node state
289 node_list = list(G.nodes())
291 # see if there already are number-based nodes
292 numeric_nodes = [n for n in node_list if isinstance(n, numbers.Number)]
293 if len(numeric_nodes) > 0:
294 # set cursor for new nodes appropriately
295 cursor = max(int(n.real) for n in numeric_nodes) + 1
296 else:
297 # or start at zero
298 cursor = 0
300 while len(G) < n:
301 r = seed.random()
303 # random choice in alpha,beta,gamma ranges
304 if r < alpha:
305 # alpha
306 # add new node v
307 v = cursor
308 cursor += 1
309 # also add to node state
310 node_list.append(v)
311 # choose w according to in-degree and delta_in
312 w = _choose_node(ws, node_list, delta_in)
314 elif r < alpha + beta:
315 # beta
316 # choose v according to out-degree and delta_out
317 v = _choose_node(vs, node_list, delta_out)
318 # choose w according to in-degree and delta_in
319 w = _choose_node(ws, node_list, delta_in)
321 else:
322 # gamma
323 # choose v according to out-degree and delta_out
324 v = _choose_node(vs, node_list, delta_out)
325 # add new node w
326 w = cursor
327 cursor += 1
328 # also add to node state
329 node_list.append(w)
331 # add edge to graph
332 G.add_edge(v, w)
334 # update degree states
335 vs.append(v)
336 ws.append(w)
338 return G
341@py_random_state(4)
342@nx._dispatchable(graphs=None, returns_graph=True)
343def random_uniform_k_out_graph(n, k, self_loops=True, with_replacement=True, seed=None):
344 """Returns a random `k`-out graph with uniform attachment.
346 A random `k`-out graph with uniform attachment is a multidigraph
347 generated by the following algorithm. For each node *u*, choose
348 `k` nodes *v* uniformly at random (with replacement). Add a
349 directed edge joining *u* to *v*.
351 Parameters
352 ----------
353 n : int
354 The number of nodes in the returned graph.
356 k : int
357 The out-degree of each node in the returned graph.
359 self_loops : bool
360 If True, self-loops are allowed when generating the graph.
362 with_replacement : bool
363 If True, neighbors are chosen with replacement and the
364 returned graph will be a directed multigraph. Otherwise,
365 neighbors are chosen without replacement and the returned graph
366 will be a directed graph.
368 seed : integer, random_state, or None (default)
369 Indicator of random number generation state.
370 See :ref:`Randomness<randomness>`.
372 Returns
373 -------
374 NetworkX graph
375 A `k`-out-regular directed graph generated according to the
376 above algorithm. It will be a multigraph if and only if
377 `with_replacement` is True.
379 Raises
380 ------
381 ValueError
382 If `with_replacement` is False and `k` is greater than
383 `n`.
385 See also
386 --------
387 random_k_out_graph
389 Notes
390 -----
391 The return digraph or multidigraph may not be strongly connected, or
392 even weakly connected.
394 If `with_replacement` is True, this function is similar to
395 :func:`random_k_out_graph`, if that function had parameter `alpha`
396 set to positive infinity.
398 """
399 if with_replacement:
400 create_using = nx.MultiDiGraph()
402 def sample(v, nodes):
403 if not self_loops:
404 nodes = nodes - {v}
405 return (seed.choice(list(nodes)) for i in range(k))
407 else:
408 create_using = nx.DiGraph()
410 def sample(v, nodes):
411 if not self_loops:
412 nodes = nodes - {v}
413 return seed.sample(list(nodes), k)
415 G = nx.empty_graph(n, create_using)
416 nodes = set(G)
417 for u in G:
418 G.add_edges_from((u, v) for v in sample(u, nodes))
419 return G
422@nx._dispatchable(graphs=None, returns_graph=True)
423def random_k_out_graph(n, k, alpha, self_loops=True, seed=None):
424 """Returns a random `k`-out graph with preferential attachment.
426 .. versionchanged:: 3.5
427 Different implementations will be used based on whether NumPy is
428 available. See Notes for details.
430 A random `k`-out graph with preferential attachment is a
431 multidigraph generated by the following algorithm.
433 1. Begin with an empty digraph, and initially set each node to have
434 weight `alpha`.
435 2. Choose a node `u` with out-degree less than `k` uniformly at
436 random.
437 3. Choose a node `v` from with probability proportional to its
438 weight.
439 4. Add a directed edge from `u` to `v`, and increase the weight
440 of `v` by one.
441 5. If each node has out-degree `k`, halt, otherwise repeat from
442 step 2.
444 For more information on this model of random graph, see [1]_.
446 Parameters
447 ----------
448 n : int
449 The number of nodes in the returned graph.
451 k : int
452 The out-degree of each node in the returned graph.
454 alpha : float
455 A positive :class:`float` representing the initial weight of
456 each vertex. A higher number means that in step 3 above, nodes
457 will be chosen more like a true uniformly random sample, and a
458 lower number means that nodes are more likely to be chosen as
459 their in-degree increases. If this parameter is not positive, a
460 :exc:`ValueError` is raised.
462 self_loops : bool
463 If True, self-loops are allowed when generating the graph.
465 seed : integer, random_state, or None (default)
466 Indicator of random number generation state.
467 See :ref:`Randomness<randomness>`.
469 Returns
470 -------
471 :class:`~networkx.classes.MultiDiGraph`
472 A `k`-out-regular multidigraph generated according to the above
473 algorithm.
475 Raises
476 ------
477 ValueError
478 If `alpha` is not positive.
480 Notes
481 -----
482 The returned multidigraph may not be strongly connected, or even
483 weakly connected.
485 `random_k_out_graph` has two implementations: an array-based formulation that
486 uses `numpy` (``_random_k_out_graph_numpy``), and a pure-Python
487 implementation (``_random_k_out_graph_python``).
488 The NumPy implementation is more performant, especially for large `n`, and is
489 therefore used by default. If NumPy is not installed in the environment,
490 then the pure Python implementation is executed.
491 However, you can explicitly control which implementation is executed by directly
492 calling the corresponding function::
494 # Use numpy if available, else Python
495 nx.random_k_out_graph(1000, 5, alpha=1)
497 # Use the numpy-based implementation (raises ImportError if numpy not installed)
498 nx.generators.directed._random_k_out_graph_numpy(1000, 5, alpha=1)
500 # Use the Python-based implementation
501 nx.generators.directed._random_k_out_graph_python(1000, 5, alpha=1)
503 References
504 ----------
505 .. [1] Peterson, Nicholas R., and Boris Pittel.
506 "Distance between two random `k`-out digraphs, with and without preferential attachment."
507 arXiv preprint arXiv:1311.5961 (2013) <https://arxiv.org/abs/1311.5961>.
509 """
510 if alpha < 0:
511 raise ValueError("alpha must be positive")
512 try: # Use numpy if available, otherwise fall back to pure Python implementation
513 return _random_k_out_graph_numpy(n, k, alpha, self_loops, seed)
514 except ImportError:
515 return _random_k_out_graph_python(n, k, alpha, self_loops, seed)
518@np_random_state(4)
519def _random_k_out_graph_numpy(n, k, alpha, self_loops=True, seed=None):
520 import numpy as np
522 G = nx.empty_graph(n, create_using=nx.MultiDiGraph)
523 nodes = np.arange(n)
524 remaining_mask = np.full(n, True)
525 weights = np.full(n, alpha)
526 total_weight = n * alpha
527 out_strengths = np.zeros(n)
529 for i in range(k * n):
530 u = seed.choice(nodes[remaining_mask])
532 if self_loops:
533 v = seed.choice(nodes, p=weights / total_weight)
534 else: # Ignore weight of u when selecting v
535 u_weight = weights[u]
536 weights[u] = 0
537 v = seed.choice(nodes, p=weights / (total_weight - u_weight))
538 weights[u] = u_weight
540 G.add_edge(u.item(), v.item())
541 weights[v] += 1
542 total_weight += 1
543 out_strengths[u] += 1
544 if out_strengths[u] == k:
545 remaining_mask[u] = False
546 return G
549@py_random_state(4)
550def _random_k_out_graph_python(n, k, alpha, self_loops=True, seed=None):
551 G = nx.empty_graph(n, create_using=nx.MultiDiGraph)
552 weights = Counter({v: alpha for v in G})
553 out_strengths = Counter({v: 0 for v in G})
555 for i in range(k * n):
556 u = seed.choice(list(out_strengths.keys()))
557 # If self-loops are not allowed, make the source node `u` have
558 # weight zero.
559 if not self_loops:
560 uweight = weights.pop(u)
562 v = weighted_choice(weights, seed=seed)
564 if not self_loops:
565 weights[u] = uweight
567 G.add_edge(u, v)
568 weights[v] += 1
569 out_strengths[u] += 1
570 if out_strengths[u] == k:
571 out_strengths.pop(u)
572 return G