Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / generators / directed.py @ 5cef0f13

History | View | Annotate | Download (14.7 KB)

1
# -*- coding: utf-8 -*-
2
# Copyright (C) 2006-2019 by
3
#   Aric Hagberg <hagberg@lanl.gov>
4
#   Dan Schult <dschult@colgate.edu>
5
#   Pieter Swart <swart@lanl.gov>
6
# Copyright (C) 2009 by Willem Ligtenberg <W.P.A.Ligtenberg@tue.nl>
7
# All rights reserved.
8
# BSD license.
9
#
10
# Authors: Aric Hagberg (hagberg@lanl.gov)
11
#          Willem Ligtenberg (W.P.A.Ligtenberg@tue.nl)
12
"""
13
Generators for some directed graphs, including growing network (GN) graphs and
14
scale-free graphs.
15

16
"""
17
from __future__ import division
18

    
19
from collections import Counter
20

    
21
import networkx as nx
22
from networkx.generators.classic import empty_graph
23
from networkx.utils import discrete_sequence
24
from networkx.utils import weighted_choice
25
from networkx.utils import py_random_state
26

    
27
__all__ = ['gn_graph', 'gnc_graph', 'gnr_graph', 'random_k_out_graph',
28
           'scale_free_graph']
29

    
30

    
31
@py_random_state(3)
32
def gn_graph(n, kernel=None, create_using=None, seed=None):
33
    """Returns the growing network (GN) digraph with `n` nodes.
34

35
    The GN graph is built by adding nodes one at a time with a link to one
36
    previously added node.  The target node for the link is chosen with
37
    probability based on degree.  The default attachment kernel is a linear
38
    function of the degree of a node.
39

40
    The graph is always a (directed) tree.
41

42
    Parameters
43
    ----------
44
    n : int
45
        The number of nodes for the generated graph.
46
    kernel : function
47
        The attachment kernel.
48
    create_using : NetworkX graph constructor, optional (default DiGraph)
49
        Graph type to create. If graph instance, then cleared before populated.
50
    seed : integer, random_state, or None (default)
51
        Indicator of random number generation state.
52
        See :ref:`Randomness<randomness>`.
53

54
    Examples
55
    --------
56
    To create the undirected GN graph, use the :meth:`~DiGraph.to_directed`
57
    method::
58

59
    >>> D = nx.gn_graph(10)  # the GN graph
60
    >>> G = D.to_undirected()  # the undirected version
61

62
    To specify an attachment kernel, use the `kernel` keyword argument::
63

64
    >>> D = nx.gn_graph(10, kernel=lambda x: x ** 1.5)  # A_k = k^1.5
65

66
    References
67
    ----------
68
    .. [1] P. L. Krapivsky and S. Redner,
69
           Organization of Growing Random Networks,
70
           Phys. Rev. E, 63, 066123, 2001.
71
    """
72
    G = empty_graph(1, create_using, default=nx.DiGraph)
73
    if not G.is_directed():
74
        raise nx.NetworkXError("create_using must indicate a Directed Graph")
75

    
76
    if kernel is None:
77
        def kernel(x): return x
78

    
79
    if n == 1:
80
        return G
81

    
82
    G.add_edge(1, 0)  # get started
83
    ds = [1, 1]  # degree sequence
84

    
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
94

    
95

    
96
@py_random_state(3)
97
def gnr_graph(n, p, create_using=None, seed=None):
98
    """Returns the growing network with redirection (GNR) digraph with `n`
99
    nodes and redirection probability `p`.
100

101
    The GNR graph is built by adding nodes one at a time with a link to one
102
    previously added node.  The previous target node is chosen uniformly at
103
    random.  With probabiliy `p` the link is instead "redirected" to the
104
    successor node of the target.
105

106
    The graph is always a (directed) tree.
107

108
    Parameters
109
    ----------
110
    n : int
111
        The number of nodes for the generated graph.
112
    p : float
113
        The redirection probability.
114
    create_using : NetworkX graph constructor, optional (default DiGraph)
115
        Graph type to create. If graph instance, then cleared before populated.
116
    seed : integer, random_state, or None (default)
117
        Indicator of random number generation state.
118
        See :ref:`Randomness<randomness>`.
119

120
    Examples
121
    --------
122
    To create the undirected GNR graph, use the :meth:`~DiGraph.to_directed`
123
    method::
124

125
    >>> D = nx.gnr_graph(10, 0.5)  # the GNR graph
126
    >>> G = D.to_undirected()  # the undirected version
127

128
    References
129
    ----------
130
    .. [1] P. L. Krapivsky and S. Redner,
131
           Organization of Growing Random Networks,
132
           Phys. Rev. E, 63, 066123, 2001.
133
    """
134
    G = empty_graph(1, create_using, default=nx.DiGraph)
135
    if not G.is_directed():
136
        raise nx.NetworkXError("create_using must indicate a Directed Graph")
137

    
138
    if n == 1:
139
        return G
140

    
141
    for source in range(1, n):
142
        target = seed.randrange(0, source)
143
        if seed.random() < p and target != 0:
144
            target = next(G.successors(target))
145
        G.add_edge(source, target)
146
    return G
147

    
148

    
149
@py_random_state(2)
150
def gnc_graph(n, create_using=None, seed=None):
151
    """Returns the growing network with copying (GNC) digraph with `n` nodes.
152

153
    The GNC graph is built by adding nodes one at a time with a link to one
154
    previously added node (chosen uniformly at random) and to all of that
155
    node's successors.
156

157
    Parameters
158
    ----------
159
    n : int
160
        The number of nodes for the generated graph.
161
    create_using : NetworkX graph constructor, optional (default DiGraph)
162
        Graph type to create. If graph instance, then cleared before populated.
163
    seed : integer, random_state, or None (default)
164
        Indicator of random number generation state.
165
        See :ref:`Randomness<randomness>`.
166

167
    References
168
    ----------
169
    .. [1] P. L. Krapivsky and S. Redner,
170
           Network Growth by Copying,
171
           Phys. Rev. E, 71, 036118, 2005k.},
172
    """
173
    G = empty_graph(1, create_using, default=nx.DiGraph)
174
    if not G.is_directed():
175
        raise nx.NetworkXError("create_using must indicate a Directed Graph")
176

    
177
    if n == 1:
178
        return G
179

    
180
    for source in range(1, n):
181
        target = seed.randrange(0, source)
182
        for succ in G.successors(target):
183
            G.add_edge(source, succ)
184
        G.add_edge(source, target)
185
    return G
186

    
187

    
188
@py_random_state(7)
189
def scale_free_graph(n, alpha=0.41, beta=0.54, gamma=0.05, delta_in=0.2,
190
                     delta_out=0, create_using=None, seed=None):
191
    """Returns a scale-free directed graph.
192

193
    Parameters
194
    ----------
195
    n : integer
196
        Number of nodes in graph
197
    alpha : float
198
        Probability for adding a new node connected to an existing node
199
        chosen randomly according to the in-degree distribution.
200
    beta : float
201
        Probability for adding an edge between two existing nodes.
202
        One existing node is chosen randomly according the in-degree
203
        distribution and the other chosen randomly according to the out-degree
204
        distribution.
205
    gamma : float
206
        Probability for adding a new node connected to an existing node
207
        chosen randomly according to the out-degree distribution.
208
    delta_in : float
209
        Bias for choosing nodes from in-degree distribution.
210
    delta_out : float
211
        Bias for choosing nodes from out-degree distribution.
212
    create_using : NetworkX graph constructor, optional
213
        The default is a MultiDiGraph 3-cycle.
214
        If a graph instance, use it without clearing first.
215
        If a graph constructor, call it to construct an empty graph.
216
    seed : integer, random_state, or None (default)
217
        Indicator of random number generation state.
218
        See :ref:`Randomness<randomness>`.
219

220
    Examples
221
    --------
222
    Create a scale-free graph on one hundred nodes::
223

224
    >>> G = nx.scale_free_graph(100)
225

226
    Notes
227
    -----
228
    The sum of `alpha`, `beta`, and `gamma` must be 1.
229

230
    References
231
    ----------
232
    .. [1] B. Bollobás, C. Borgs, J. Chayes, and O. Riordan,
233
           Directed scale-free graphs,
234
           Proceedings of the fourteenth annual ACM-SIAM Symposium on
235
           Discrete Algorithms, 132--139, 2003.
236
    """
237

    
238
    def _choose_node(G, distribution, delta, psum):
239
        cumsum = 0.0
240
        # normalization
241
        r = seed.random()
242
        for n, d in distribution:
243
            cumsum += (d + delta) / psum
244
            if r < cumsum:
245
                break
246
        return n
247

    
248
    if create_using is None or not hasattr(create_using, '_adj'):
249
        # start with 3-cycle
250
        G = nx.empty_graph(3, create_using, default=nx.MultiDiGraph)
251
        G.add_edges_from([(0, 1), (1, 2), (2, 0)])
252
    else:
253
        G = create_using
254
    if not (G.is_directed() and G.is_multigraph()):
255
        raise nx.NetworkXError("MultiDiGraph required in create_using")
256

    
257
    if alpha <= 0:
258
        raise ValueError('alpha must be > 0.')
259
    if beta <= 0:
260
        raise ValueError('beta must be > 0.')
261
    if gamma <= 0:
262
        raise ValueError('gamma must be > 0.')
263

    
264
    if abs(alpha + beta + gamma - 1.0) >= 1e-9:
265
        raise ValueError('alpha+beta+gamma must equal 1.')
266

    
267
    number_of_edges = G.number_of_edges()
268
    while len(G) < n:
269
        psum_in = number_of_edges + delta_in * len(G)
270
        psum_out = number_of_edges + delta_out * len(G)
271
        r = seed.random()
272
        # random choice in alpha,beta,gamma ranges
273
        if r < alpha:
274
            # alpha
275
            # add new node v
276
            v = len(G)
277
            # choose w according to in-degree and delta_in
278
            w = _choose_node(G, G.in_degree(), delta_in, psum_in)
279
        elif r < alpha + beta:
280
            # beta
281
            # choose v according to out-degree and delta_out
282
            v = _choose_node(G, G.out_degree(), delta_out, psum_out)
283
            # choose w according to in-degree and delta_in
284
            w = _choose_node(G, G.in_degree(), delta_in, psum_in)
285
        else:
286
            # gamma
287
            # choose v according to out-degree and delta_out
288
            v = _choose_node(G, G.out_degree(), delta_out, psum_out)
289
            # add new node w
290
            w = len(G)
291
        G.add_edge(v, w)
292
        number_of_edges += 1
293
    return G
294

    
295

    
296
@py_random_state(4)
297
def random_uniform_k_out_graph(n, k, self_loops=True, with_replacement=True,
298
                               seed=None):
299
    """Returns a random `k`-out graph with uniform attachment.
300

301
    A random `k`-out graph with uniform attachment is a multidigraph
302
    generated by the following algorithm. For each node *u*, choose
303
    `k` nodes *v* uniformly at random (with replacement). Add a
304
    directed edge joining *u* to *v*.
305

306
    Parameters
307
    ----------
308
    n : int
309
        The number of nodes in the returned graph.
310

311
    k : int
312
        The out-degree of each node in the returned graph.
313

314
    self_loops : bool
315
        If True, self-loops are allowed when generating the graph.
316

317
    with_replacement : bool
318
        If True, neighbors are chosen with replacement and the
319
        returned graph will be a directed multigraph. Otherwise,
320
        neighbors are chosen without replacement and the returned graph
321
        will be a directed graph.
322

323
    seed : integer, random_state, or None (default)
324
        Indicator of random number generation state.
325
        See :ref:`Randomness<randomness>`.
326

327
    Returns
328
    -------
329
    NetworkX graph
330
        A `k`-out-regular directed graph generated according to the
331
        above algorithm. It will be a multigraph if and only if
332
        `with_replacement` is True.
333

334
    Raises
335
    ------
336
    ValueError
337
        If `with_replacement` is False and `k` is greater than
338
        `n`.
339

340
    See also
341
    --------
342
    random_k_out_graph
343

344
    Notes
345
    -----
346
    The return digraph or multidigraph may not be strongly connected, or
347
    even weakly connected.
348

349
    If `with_replacement` is True, this function is similar to
350
    :func:`random_k_out_graph`, if that function had parameter `alpha`
351
    set to positive infinity.
352

353
    """
354
    if with_replacement:
355
        create_using = nx.MultiDiGraph()
356

    
357
        def sample(v, nodes):
358
            if not self_loops:
359
                nodes = nodes - {v}
360
            return (seed.choice(list(nodes)) for i in range(k))
361

    
362
    else:
363
        create_using = nx.DiGraph()
364

    
365
        def sample(v, nodes):
366
            if not self_loops:
367
                nodes = nodes - {v}
368
            return seed.sample(nodes, k)
369

    
370
    G = nx.empty_graph(n, create_using)
371
    nodes = set(G)
372
    for u in G:
373
        G.add_edges_from((u, v) for v in sample(u, nodes))
374
    return G
375

    
376

    
377
@py_random_state(4)
378
def random_k_out_graph(n, k, alpha, self_loops=True, seed=None):
379
    """Returns a random `k`-out graph with preferential attachment.
380

381
    A random `k`-out graph with preferential attachment is a
382
    multidigraph generated by the following algorithm.
383

384
    1. Begin with an empty digraph, and initially set each node to have
385
       weight `alpha`.
386
    2. Choose a node `u` with out-degree less than `k` uniformly at
387
       random.
388
    3. Choose a node `v` from with probability proportional to its
389
       weight.
390
    4. Add a directed edge from `u` to `v`, and increase the weight
391
       of `v` by one.
392
    5. If each node has out-degree `k`, halt, otherwise repeat from
393
       step 2.
394

395
    For more information on this model of random graph, see [1].
396

397
    Parameters
398
    ----------
399
    n : int
400
        The number of nodes in the returned graph.
401

402
    k : int
403
        The out-degree of each node in the returned graph.
404

405
    alpha : float
406
        A positive :class:`float` representing the initial weight of
407
        each vertex. A higher number means that in step 3 above, nodes
408
        will be chosen more like a true uniformly random sample, and a
409
        lower number means that nodes are more likely to be chosen as
410
        their in-degree increases. If this parameter is not positive, a
411
        :exc:`ValueError` is raised.
412

413
    self_loops : bool
414
        If True, self-loops are allowed when generating the graph.
415

416
    seed : integer, random_state, or None (default)
417
        Indicator of random number generation state.
418
        See :ref:`Randomness<randomness>`.
419

420
    Returns
421
    -------
422
    :class:`~networkx.classes.MultiDiGraph`
423
        A `k`-out-regular multidigraph generated according to the above
424
        algorithm.
425

426
    Raises
427
    ------
428
    ValueError
429
        If `alpha` is not positive.
430

431
    Notes
432
    -----
433
    The returned multidigraph may not be strongly connected, or even
434
    weakly connected.
435

436
    References
437
    ----------
438
    [1]: Peterson, Nicholas R., and Boris Pittel.
439
         "Distance between two random `k`-out digraphs, with and without
440
         preferential attachment."
441
         arXiv preprint arXiv:1311.5961 (2013).
442
         <https://arxiv.org/abs/1311.5961>
443

444
    """
445
    if alpha < 0:
446
        raise ValueError('alpha must be positive')
447
    G = nx.empty_graph(n, create_using=nx.MultiDiGraph)
448
    weights = Counter({v: alpha for v in G})
449
    for i in range(k * n):
450
        u = seed.choice([v for v, d in G.out_degree() if d < k])
451
        # If self-loops are not allowed, make the source node `u` have
452
        # weight zero.
453
        if not self_loops:
454
            adjustment = Counter({u: weights[u]})
455
        else:
456
            adjustment = Counter()
457
        v = weighted_choice(weights - adjustment, seed=seed)
458
        G.add_edge(u, v)
459
        weights[v] += 1
460
    return G