Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (42.1 KB)

1
# -*- coding: utf-8 -*-
2
#    Copyright (C) 2004-2019 by
3
#    Aric Hagberg <hagberg@lanl.gov>
4
#    Dan Schult <dschult@colgate.edu>
5
#    Pieter Swart <swart@lanl.gov>
6
#    All rights reserved.
7
#    BSD license.
8
"""
9
Generators for random graphs.
10

11
"""
12

    
13
from __future__ import division
14
import itertools
15
import math
16

    
17
import networkx as nx
18
from networkx.utils import py_random_state
19
from .classic import empty_graph, path_graph, complete_graph
20
from .degree_seq import degree_sequence_tree
21
from collections import defaultdict
22

    
23
__all__ = ['fast_gnp_random_graph',
24
           'gnp_random_graph',
25
           'dense_gnm_random_graph',
26
           'gnm_random_graph',
27
           'erdos_renyi_graph',
28
           'binomial_graph',
29
           'newman_watts_strogatz_graph',
30
           'watts_strogatz_graph',
31
           'connected_watts_strogatz_graph',
32
           'random_regular_graph',
33
           'barabasi_albert_graph',
34
           'dual_barabasi_albert_graph',
35
           'extended_barabasi_albert_graph',
36
           'powerlaw_cluster_graph',
37
           'random_lobster',
38
           'random_shell_graph',
39
           'random_powerlaw_tree',
40
           'random_powerlaw_tree_sequence',
41
           'random_kernel_graph']
42

    
43

    
44
#-------------------------------------------------------------------------
45
#  Some Famous Random Graphs
46
#-------------------------------------------------------------------------
47

    
48

    
49
@py_random_state(2)
50
def fast_gnp_random_graph(n, p, seed=None, directed=False):
51
    """Returns a $G_{n,p}$ random graph, also known as an Erdős-Rényi graph or
52
    a binomial graph.
53

54
    Parameters
55
    ----------
56
    n : int
57
        The number of nodes.
58
    p : float
59
        Probability for edge creation.
60
    seed : integer, random_state, or None (default)
61
        Indicator of random number generation state.
62
        See :ref:`Randomness<randomness>`.
63
    directed : bool, optional (default=False)
64
        If True, this function returns a directed graph.
65

66
    Notes
67
    -----
68
    The $G_{n,p}$ graph algorithm chooses each of the $[n (n - 1)] / 2$
69
    (undirected) or $n (n - 1)$ (directed) possible edges with probability $p$.
70

71
    This algorithm [1]_ runs in $O(n + m)$ time, where `m` is the expected number of
72
    edges, which equals $p n (n - 1) / 2$. This should be faster than
73
    :func:`gnp_random_graph` when $p$ is small and the expected number of edges
74
    is small (that is, the graph is sparse).
75

76
    See Also
77
    --------
78
    gnp_random_graph
79

80
    References
81
    ----------
82
    .. [1] Vladimir Batagelj and Ulrik Brandes,
83
       "Efficient generation of large random networks",
84
       Phys. Rev. E, 71, 036113, 2005.
85
    """
86
    G = empty_graph(n)
87

    
88
    if p <= 0 or p >= 1:
89
        return nx.gnp_random_graph(n, p, seed=seed, directed=directed)
90

    
91
    w = -1
92
    lp = math.log(1.0 - p)
93

    
94
    if directed:
95
        G = nx.DiGraph(G)
96
        # Nodes in graph are from 0,n-1 (start with v as the first node index).
97
        v = 0
98
        while v < n:
99
            lr = math.log(1.0 - seed.random())
100
            w = w + 1 + int(lr / lp)
101
            if v == w:  # avoid self loops
102
                w = w + 1
103
            while v < n <= w:
104
                w = w - n
105
                v = v + 1
106
                if v == w:  # avoid self loops
107
                    w = w + 1
108
            if v < n:
109
                G.add_edge(v, w)
110
    else:
111
        # Nodes in graph are from 0,n-1 (start with v as the second node index).
112
        v = 1
113
        while v < n:
114
            lr = math.log(1.0 - seed.random())
115
            w = w + 1 + int(lr / lp)
116
            while w >= v and v < n:
117
                w = w - v
118
                v = v + 1
119
            if v < n:
120
                G.add_edge(v, w)
121
    return G
122

    
123

    
124
@py_random_state(2)
125
def gnp_random_graph(n, p, seed=None, directed=False):
126
    """Returns a $G_{n,p}$ random graph, also known as an Erdős-Rényi graph
127
    or a binomial graph.
128

129
    The $G_{n,p}$ model chooses each of the possible edges with probability $p$.
130

131
    The functions :func:`binomial_graph` and :func:`erdos_renyi_graph` are
132
    aliases of this function.
133

134
    Parameters
135
    ----------
136
    n : int
137
        The number of nodes.
138
    p : float
139
        Probability for edge creation.
140
    seed : integer, random_state, or None (default)
141
        Indicator of random number generation state.
142
        See :ref:`Randomness<randomness>`.
143
    directed : bool, optional (default=False)
144
        If True, this function returns a directed graph.
145

146
    See Also
147
    --------
148
    fast_gnp_random_graph
149

150
    Notes
151
    -----
152
    This algorithm [2]_ runs in $O(n^2)$ time.  For sparse graphs (that is, for
153
    small values of $p$), :func:`fast_gnp_random_graph` is a faster algorithm.
154

155
    References
156
    ----------
157
    .. [1] P. Erdős and A. Rényi, On Random Graphs, Publ. Math. 6, 290 (1959).
158
    .. [2] E. N. Gilbert, Random Graphs, Ann. Math. Stat., 30, 1141 (1959).
159
    """
160
    if directed:
161
        edges = itertools.permutations(range(n), 2)
162
        G = nx.DiGraph()
163
    else:
164
        edges = itertools.combinations(range(n), 2)
165
        G = nx.Graph()
166
    G.add_nodes_from(range(n))
167
    if p <= 0:
168
        return G
169
    if p >= 1:
170
        return complete_graph(n, create_using=G)
171

    
172
    for e in edges:
173
        if seed.random() < p:
174
            G.add_edge(*e)
175
    return G
176

    
177

    
178
# add some aliases to common names
179
binomial_graph = gnp_random_graph
180
erdos_renyi_graph = gnp_random_graph
181

    
182

    
183
@py_random_state(2)
184
def dense_gnm_random_graph(n, m, seed=None):
185
    """Returns a $G_{n,m}$ random graph.
186

187
    In the $G_{n,m}$ model, a graph is chosen uniformly at random from the set
188
    of all graphs with $n$ nodes and $m$ edges.
189

190
    This algorithm should be faster than :func:`gnm_random_graph` for dense
191
    graphs.
192

193
    Parameters
194
    ----------
195
    n : int
196
        The number of nodes.
197
    m : int
198
        The number of edges.
199
    seed : integer, random_state, or None (default)
200
        Indicator of random number generation state.
201
        See :ref:`Randomness<randomness>`.
202

203
    See Also
204
    --------
205
    gnm_random_graph()
206

207
    Notes
208
    -----
209
    Algorithm by Keith M. Briggs Mar 31, 2006.
210
    Inspired by Knuth's Algorithm S (Selection sampling technique),
211
    in section 3.4.2 of [1]_.
212

213
    References
214
    ----------
215
    .. [1] Donald E. Knuth, The Art of Computer Programming,
216
        Volume 2/Seminumerical algorithms, Third Edition, Addison-Wesley, 1997.
217
    """
218
    mmax = n * (n - 1) / 2
219
    if m >= mmax:
220
        G = complete_graph(n)
221
    else:
222
        G = empty_graph(n)
223

    
224
    if n == 1 or m >= mmax:
225
        return G
226

    
227
    u = 0
228
    v = 1
229
    t = 0
230
    k = 0
231
    while True:
232
        if seed.randrange(mmax - t) < m - k:
233
            G.add_edge(u, v)
234
            k += 1
235
            if k == m:
236
                return G
237
        t += 1
238
        v += 1
239
        if v == n:  # go to next row of adjacency matrix
240
            u += 1
241
            v = u + 1
242

    
243

    
244
@py_random_state(2)
245
def gnm_random_graph(n, m, seed=None, directed=False):
246
    """Returns a $G_{n,m}$ random graph.
247

248
    In the $G_{n,m}$ model, a graph is chosen uniformly at random from the set
249
    of all graphs with $n$ nodes and $m$ edges.
250

251
    This algorithm should be faster than :func:`dense_gnm_random_graph` for
252
    sparse graphs.
253

254
    Parameters
255
    ----------
256
    n : int
257
        The number of nodes.
258
    m : int
259
        The number of edges.
260
    seed : integer, random_state, or None (default)
261
        Indicator of random number generation state.
262
        See :ref:`Randomness<randomness>`.
263
    directed : bool, optional (default=False)
264
        If True return a directed graph
265

266
    See also
267
    --------
268
    dense_gnm_random_graph
269

270
    """
271
    if directed:
272
        G = nx.DiGraph()
273
    else:
274
        G = nx.Graph()
275
    G.add_nodes_from(range(n))
276

    
277
    if n == 1:
278
        return G
279
    max_edges = n * (n - 1)
280
    if not directed:
281
        max_edges /= 2.0
282
    if m >= max_edges:
283
        return complete_graph(n, create_using=G)
284

    
285
    nlist = list(G)
286
    edge_count = 0
287
    while edge_count < m:
288
        # generate random edge,u,v
289
        u = seed.choice(nlist)
290
        v = seed.choice(nlist)
291
        if u == v or G.has_edge(u, v):
292
            continue
293
        else:
294
            G.add_edge(u, v)
295
            edge_count = edge_count + 1
296
    return G
297

    
298

    
299
@py_random_state(3)
300
def newman_watts_strogatz_graph(n, k, p, seed=None):
301
    """Returns a Newman–Watts–Strogatz small-world graph.
302

303
    Parameters
304
    ----------
305
    n : int
306
        The number of nodes.
307
    k : int
308
        Each node is joined with its `k` nearest neighbors in a ring
309
        topology.
310
    p : float
311
        The probability of adding a new edge for each edge.
312
    seed : integer, random_state, or None (default)
313
        Indicator of random number generation state.
314
        See :ref:`Randomness<randomness>`.
315

316
    Notes
317
    -----
318
    First create a ring over $n$ nodes [1]_.  Then each node in the ring is
319
    connected with its $k$ nearest neighbors (or $k - 1$ neighbors if $k$
320
    is odd).  Then shortcuts are created by adding new edges as follows: for
321
    each edge $(u, v)$ in the underlying "$n$-ring with $k$ nearest
322
    neighbors" with probability $p$ add a new edge $(u, w)$ with
323
    randomly-chosen existing node $w$.  In contrast with
324
    :func:`watts_strogatz_graph`, no edges are removed.
325

326
    See Also
327
    --------
328
    watts_strogatz_graph()
329

330
    References
331
    ----------
332
    .. [1] M. E. J. Newman and D. J. Watts,
333
       Renormalization group analysis of the small-world network model,
334
       Physics Letters A, 263, 341, 1999.
335
       https://doi.org/10.1016/S0375-9601(99)00757-4
336
    """
337
    if k >= n:
338
        raise nx.NetworkXError("k>=n, choose smaller k or larger n")
339
    G = empty_graph(n)
340
    nlist = list(G.nodes())
341
    fromv = nlist
342
    # connect the k/2 neighbors
343
    for j in range(1, k // 2 + 1):
344
        tov = fromv[j:] + fromv[0:j]  # the first j are now last
345
        for i in range(len(fromv)):
346
            G.add_edge(fromv[i], tov[i])
347
    # for each edge u-v, with probability p, randomly select existing
348
    # node w and add new edge u-w
349
    e = list(G.edges())
350
    for (u, v) in e:
351
        if seed.random() < p:
352
            w = seed.choice(nlist)
353
            # no self-loops and reject if edge u-w exists
354
            # is that the correct NWS model?
355
            while w == u or G.has_edge(u, w):
356
                w = seed.choice(nlist)
357
                if G.degree(u) >= n - 1:
358
                    break  # skip this rewiring
359
            else:
360
                G.add_edge(u, w)
361
    return G
362

    
363

    
364
@py_random_state(3)
365
def watts_strogatz_graph(n, k, p, seed=None):
366
    """Returns a Watts–Strogatz small-world graph.
367

368
    Parameters
369
    ----------
370
    n : int
371
        The number of nodes
372
    k : int
373
        Each node is joined with its `k` nearest neighbors in a ring
374
        topology.
375
    p : float
376
        The probability of rewiring each edge
377
    seed : integer, random_state, or None (default)
378
        Indicator of random number generation state.
379
        See :ref:`Randomness<randomness>`.
380

381
    See Also
382
    --------
383
    newman_watts_strogatz_graph()
384
    connected_watts_strogatz_graph()
385

386
    Notes
387
    -----
388
    First create a ring over $n$ nodes [1]_.  Then each node in the ring is joined
389
    to its $k$ nearest neighbors (or $k - 1$ neighbors if $k$ is odd).
390
    Then shortcuts are created by replacing some edges as follows: for each
391
    edge $(u, v)$ in the underlying "$n$-ring with $k$ nearest neighbors"
392
    with probability $p$ replace it with a new edge $(u, w)$ with uniformly
393
    random choice of existing node $w$.
394

395
    In contrast with :func:`newman_watts_strogatz_graph`, the random rewiring
396
    does not increase the number of edges. The rewired graph is not guaranteed
397
    to be connected as in :func:`connected_watts_strogatz_graph`.
398

399
    References
400
    ----------
401
    .. [1] Duncan J. Watts and Steven H. Strogatz,
402
       Collective dynamics of small-world networks,
403
       Nature, 393, pp. 440--442, 1998.
404
    """
405
    if k >= n:
406
        raise nx.NetworkXError("k>=n, choose smaller k or larger n")
407

    
408
    G = nx.Graph()
409
    nodes = list(range(n))  # nodes are labeled 0 to n-1
410
    # connect each node to k/2 neighbors
411
    for j in range(1, k // 2 + 1):
412
        targets = nodes[j:] + nodes[0:j]  # first j nodes are now last in list
413
        G.add_edges_from(zip(nodes, targets))
414
    # rewire edges from each node
415
    # loop over all nodes in order (label) and neighbors in order (distance)
416
    # no self loops or multiple edges allowed
417
    for j in range(1, k // 2 + 1):  # outer loop is neighbors
418
        targets = nodes[j:] + nodes[0:j]  # first j nodes are now last in list
419
        # inner loop in node order
420
        for u, v in zip(nodes, targets):
421
            if seed.random() < p:
422
                w = seed.choice(nodes)
423
                # Enforce no self-loops or multiple edges
424
                while w == u or G.has_edge(u, w):
425
                    w = seed.choice(nodes)
426
                    if G.degree(u) >= n - 1:
427
                        break  # skip this rewiring
428
                else:
429
                    G.remove_edge(u, v)
430
                    G.add_edge(u, w)
431
    return G
432

    
433

    
434
@py_random_state(4)
435
def connected_watts_strogatz_graph(n, k, p, tries=100, seed=None):
436
    """Returns a connected Watts–Strogatz small-world graph.
437

438
    Attempts to generate a connected graph by repeated generation of
439
    Watts–Strogatz small-world graphs.  An exception is raised if the maximum
440
    number of tries is exceeded.
441

442
    Parameters
443
    ----------
444
    n : int
445
        The number of nodes
446
    k : int
447
        Each node is joined with its `k` nearest neighbors in a ring
448
        topology.
449
    p : float
450
        The probability of rewiring each edge
451
    tries : int
452
        Number of attempts to generate a connected graph.
453
    seed : integer, random_state, or None (default)
454
        Indicator of random number generation state.
455
        See :ref:`Randomness<randomness>`.
456

457
    Notes
458
    -----
459
    First create a ring over $n$ nodes [1]_.  Then each node in the ring is joined
460
    to its $k$ nearest neighbors (or $k - 1$ neighbors if $k$ is odd).
461
    Then shortcuts are created by replacing some edges as follows: for each
462
    edge $(u, v)$ in the underlying "$n$-ring with $k$ nearest neighbors"
463
    with probability $p$ replace it with a new edge $(u, w)$ with uniformly
464
    random choice of existing node $w$.
465
    The entire process is repeated until a connected graph results.
466

467
    See Also
468
    --------
469
    newman_watts_strogatz_graph()
470
    watts_strogatz_graph()
471

472
    References
473
    ----------
474
    .. [1] Duncan J. Watts and Steven H. Strogatz,
475
       Collective dynamics of small-world networks,
476
       Nature, 393, pp. 440--442, 1998.
477
    """
478
    for i in range(tries):
479
        # seed is an RNG so should change sequence each call
480
        G = watts_strogatz_graph(n, k, p, seed)
481
        if nx.is_connected(G):
482
            return G
483
    raise nx.NetworkXError('Maximum number of tries exceeded')
484

    
485

    
486
@py_random_state(2)
487
def random_regular_graph(d, n, seed=None):
488
    r"""Returns a random $d$-regular graph on $n$ nodes.
489

490
    The resulting graph has no self-loops or parallel edges.
491

492
    Parameters
493
    ----------
494
    d : int
495
      The degree of each node.
496
    n : integer
497
      The number of nodes. The value of $n \times d$ must be even.
498
    seed : integer, random_state, or None (default)
499
        Indicator of random number generation state.
500
        See :ref:`Randomness<randomness>`.
501

502
    Notes
503
    -----
504
    The nodes are numbered from $0$ to $n - 1$.
505

506
    Kim and Vu's paper [2]_ shows that this algorithm samples in an
507
    asymptotically uniform way from the space of random graphs when
508
    $d = O(n^{1 / 3 - \epsilon})$.
509

510
    Raises
511
    ------
512

513
    NetworkXError
514
        If $n \times d$ is odd or $d$ is greater than or equal to $n$.
515

516
    References
517
    ----------
518
    .. [1] A. Steger and N. Wormald,
519
       Generating random regular graphs quickly,
520
       Probability and Computing 8 (1999), 377-396, 1999.
521
       http://citeseer.ist.psu.edu/steger99generating.html
522

523
    .. [2] Jeong Han Kim and Van H. Vu,
524
       Generating random regular graphs,
525
       Proceedings of the thirty-fifth ACM symposium on Theory of computing,
526
       San Diego, CA, USA, pp 213--222, 2003.
527
       http://portal.acm.org/citation.cfm?id=780542.780576
528
    """
529
    if (n * d) % 2 != 0:
530
        raise nx.NetworkXError("n * d must be even")
531

    
532
    if not 0 <= d < n:
533
        raise nx.NetworkXError("the 0 <= d < n inequality must be satisfied")
534

    
535
    if d == 0:
536
        return empty_graph(n)
537

    
538
    def _suitable(edges, potential_edges):
539
        # Helper subroutine to check if there are suitable edges remaining
540
        # If False, the generation of the graph has failed
541
        if not potential_edges:
542
            return True
543
        for s1 in potential_edges:
544
            for s2 in potential_edges:
545
                # Two iterators on the same dictionary are guaranteed
546
                # to visit it in the same order if there are no
547
                # intervening modifications.
548
                if s1 == s2:
549
                    # Only need to consider s1-s2 pair one time
550
                    break
551
                if s1 > s2:
552
                    s1, s2 = s2, s1
553
                if (s1, s2) not in edges:
554
                    return True
555
        return False
556

    
557
    def _try_creation():
558
        # Attempt to create an edge set
559

    
560
        edges = set()
561
        stubs = list(range(n)) * d
562

    
563
        while stubs:
564
            potential_edges = defaultdict(lambda: 0)
565
            seed.shuffle(stubs)
566
            stubiter = iter(stubs)
567
            for s1, s2 in zip(stubiter, stubiter):
568
                if s1 > s2:
569
                    s1, s2 = s2, s1
570
                if s1 != s2 and ((s1, s2) not in edges):
571
                    edges.add((s1, s2))
572
                else:
573
                    potential_edges[s1] += 1
574
                    potential_edges[s2] += 1
575

    
576
            if not _suitable(edges, potential_edges):
577
                return None  # failed to find suitable edge set
578

    
579
            stubs = [node for node, potential in potential_edges.items()
580
                     for _ in range(potential)]
581
        return edges
582

    
583
    # Even though a suitable edge set exists,
584
    # the generation of such a set is not guaranteed.
585
    # Try repeatedly to find one.
586
    edges = _try_creation()
587
    while edges is None:
588
        edges = _try_creation()
589

    
590
    G = nx.Graph()
591
    G.add_edges_from(edges)
592

    
593
    return G
594

    
595

    
596
def _random_subset(seq, m, rng):
597
    """ Return m unique elements from seq.
598

599
    This differs from random.sample which can return repeated
600
    elements if seq holds repeated elements.
601

602
    Note: rng is a random.Random or numpy.random.RandomState instance.
603
    """
604
    targets = set()
605
    while len(targets) < m:
606
        x = rng.choice(seq)
607
        targets.add(x)
608
    return targets
609

    
610

    
611
@py_random_state(2)
612
def barabasi_albert_graph(n, m, seed=None):
613
    """Returns a random graph according to the Barabási–Albert preferential
614
    attachment model.
615

616
    A graph of $n$ nodes is grown by attaching new nodes each with $m$
617
    edges that are preferentially attached to existing nodes with high degree.
618

619
    Parameters
620
    ----------
621
    n : int
622
        Number of nodes
623
    m : int
624
        Number of edges to attach from a new node to existing nodes
625
    seed : integer, random_state, or None (default)
626
        Indicator of random number generation state.
627
        See :ref:`Randomness<randomness>`.
628

629
    Returns
630
    -------
631
    G : Graph
632

633
    Raises
634
    ------
635
    NetworkXError
636
        If `m` does not satisfy ``1 <= m < n``.
637

638
    References
639
    ----------
640
    .. [1] A. L. Barabási and R. Albert "Emergence of scaling in
641
       random networks", Science 286, pp 509-512, 1999.
642
    """
643

    
644
    if m < 1 or m >= n:
645
        raise nx.NetworkXError("Barabási–Albert network must have m >= 1"
646
                               " and m < n, m = %d, n = %d" % (m, n))
647

    
648
    # Add m initial nodes (m0 in barabasi-speak)
649
    G = empty_graph(m)
650
    # Target nodes for new edges
651
    targets = list(range(m))
652
    # List of existing nodes, with nodes repeated once for each adjacent edge
653
    repeated_nodes = []
654
    # Start adding the other n-m nodes. The first node is m.
655
    source = m
656
    while source < n:
657
        # Add edges to m nodes from the source.
658
        G.add_edges_from(zip([source] * m, targets))
659
        # Add one node to the list for each new edge just created.
660
        repeated_nodes.extend(targets)
661
        # And the new node "source" has m edges to add to the list.
662
        repeated_nodes.extend([source] * m)
663
        # Now choose m unique nodes from the existing nodes
664
        # Pick uniformly from repeated_nodes (preferential attachment)
665
        targets = _random_subset(repeated_nodes, m, seed)
666
        source += 1
667
    return G
668

    
669

    
670
@py_random_state(4)
671
def dual_barabasi_albert_graph(n, m1, m2, p, seed=None):
672
    """Returns a random graph according to the dual Barabási–Albert preferential
673
    attachment model.
674

675
    A graph of $n$ nodes is grown by attaching new nodes each with either $m_1$
676
    edges (with probability $p$) or $m_2$ edges (with probability $1-p$) that
677
    are preferentially attached to existing nodes with high degree.
678

679
    Parameters
680
    ----------
681
    n : int
682
        Number of nodes
683
    m1 : int
684
        Number of edges to attach from a new node to existing nodes with probability $p$
685
    m2 : int
686
        Number of edges to attach from a new node to existing nodes with probability $1-p$
687
    p : float
688
        The probability of attaching $m_1$ edges (as opposed to $m_2$ edges)
689
    seed : integer, random_state, or None (default)
690
        Indicator of random number generation state.
691
        See :ref:`Randomness<randomness>`.
692

693
    Returns
694
    -------
695
    G : Graph
696

697
    Raises
698
    ------
699
    NetworkXError
700
        If `m1` and `m2` do not satisfy ``1 <= m1,m2 < n`` or `p` does not satisfy ``0 <= p <= 1``.
701

702
    References
703
    ----------
704
    .. [1] N. Moshiri "The dual-Barabasi-Albert model", arXiv:1810.10538.
705
    """
706

    
707
    if m1 < 1 or m1 >= n:
708
        raise nx.NetworkXError("Dual Barabási–Albert network must have m1 >= 1"
709
                               " and m1 < n, m1 = %d, n = %d" % (m1, n))
710
    if m2 < 1 or m2 >= n:
711
        raise nx.NetworkXError("Dual Barabási–Albert network must have m2 >= 1"
712
                               " and m2 < n, m2 = %d, n = %d" % (m2, n))
713
    if p < 0 or p > 1:
714
        raise nx.NetworkXError("Dual Barabási–Albert network must have 0 <= p <= 1,"
715
                               "p = %f" % p)
716
    
717
    # For simplicity, if p == 0 or 1, just return BA
718
    if p == 1:
719
        return barabasi_albert_graph(n, m1, seed)
720
    elif p == 0:
721
        return barabasi_albert_graph(n, m2, seed)
722

    
723
    # Add max(m1,m2) initial nodes (m0 in barabasi-speak)
724
    G = empty_graph(max(m1,m2))
725
    # Target nodes for new edges
726
    targets = list(range(max(m1,m2)))
727
    # List of existing nodes, with nodes repeated once for each adjacent edge
728
    repeated_nodes = []
729
    # Start adding the remaining nodes.
730
    source = max(m1,m2)
731
    # Pick which m to use first time (m1 or m2)
732
    if seed.random() < p:
733
        m = m1
734
    else:
735
        m = m2
736
    while source < n:
737
        # Add edges to m nodes from the source.
738
        G.add_edges_from(zip([source] * m, targets))
739
        # Add one node to the list for each new edge just created.
740
        repeated_nodes.extend(targets)
741
        # And the new node "source" has m edges to add to the list.
742
        repeated_nodes.extend([source] * m)
743
        # Pick which m to use next time (m1 or m2)
744
        if seed.random() < p:
745
            m = m1
746
        else:
747
            m = m2
748
        # Now choose m unique nodes from the existing nodes
749
        # Pick uniformly from repeated_nodes (preferential attachment)
750
        targets = _random_subset(repeated_nodes, m, seed)
751
        source += 1
752
    return G
753

    
754

    
755
@py_random_state(4)
756
def extended_barabasi_albert_graph(n, m, p, q, seed=None):
757
    """Returns an extended Barabási–Albert model graph.
758

759
    An extended Barabási–Albert model graph is a random graph constructed
760
    using preferential attachment. The extended model allows new edges,
761
    rewired edges or new nodes. Based on the probabilities $p$ and $q$
762
    with $p + q < 1$, the growing behavior of the graph is determined as:
763

764
    1) With $p$ probability, $m$ new edges are added to the graph,
765
    starting from randomly chosen existing nodes and attached preferentially at the other end.
766

767
    2) With $q$ probability, $m$ existing edges are rewired
768
    by randomly choosing an edge and rewiring one end to a preferentially chosen node.
769

770
    3) With $(1 - p - q)$ probability, $m$ new nodes are added to the graph
771
    with edges attached preferentially.
772

773
    When $p = q = 0$, the model behaves just like the Barabási–Alber mo
774

775
    Parameters
776
    ----------
777
    n : int
778
        Number of nodes
779
    m : int
780
        Number of edges with which a new node attaches to existing nodes
781
    p : float
782
        Probability value for adding an edge between existing nodes. p + q < 1
783
    q : float
784
        Probability value of rewiring of existing edges. p + q < 1
785
    seed : integer, random_state, or None (default)
786
        Indicator of random number generation state.
787
        See :ref:`Randomness<randomness>`.
788

789
    Returns
790
    -------
791
    G : Graph
792

793
    Raises
794
    ------
795
    NetworkXError
796
        If `m` does not satisfy ``1 <= m < n`` or ``1 >= p + q``
797

798
    References
799
    ----------
800
    .. [1] Albert, R., & Barabási, A. L. (2000)
801
       Topology of evolving networks: local events and universality
802
       Physical review letters, 85(24), 5234.
803
    """
804
    if m < 1 or m >= n:
805
        msg = "Extended Barabasi-Albert network needs m>=1 and m<n, m=%d, n=%d"
806
        raise nx.NetworkXError(msg % (m, n))
807
    if p + q >= 1:
808
        msg = "Extended Barabasi-Albert network needs p + q <= 1, p=%d, q=%d"
809
        raise nx.NetworkXError(msg % (p, q))
810

    
811
    # Add m initial nodes (m0 in barabasi-speak)
812
    G = empty_graph(m)
813

    
814
    # List of nodes to represent the preferential attachment random selection.
815
    # At the creation of the graph, all nodes are added to the list
816
    # so that even nodes that are not connected have a chance to get selected,
817
    # for rewiring and adding of edges.
818
    # With each new edge, nodes at the ends of the edge are added to the list.
819
    attachment_preference = []
820
    attachment_preference.extend(range(m))
821

    
822
    # Start adding the other n-m nodes. The first node is m.
823
    new_node = m
824
    while new_node < n:
825
        a_probability = seed.random()
826

    
827
        # Total number of edges of a Clique of all the nodes
828
        clique_degree = len(G) - 1
829
        clique_size = (len(G) * clique_degree) / 2
830

    
831
        # Adding m new edges, if there is room to add them
832
        if a_probability < p and G.size() <= clique_size - m:
833
            # Select the nodes where an edge can be added
834
            elligible_nodes = [nd for nd, deg in G.degree()
835
                               if deg < clique_degree]
836
            for i in range(m):
837
                # Choosing a random source node from elligible_nodes
838
                src_node = seed.choice(elligible_nodes)
839

    
840
                # Picking a possible node that is not 'src_node' or
841
                # neighbor with 'src_node', with preferential attachment
842
                prohibited_nodes = list(G[src_node])
843
                prohibited_nodes.append(src_node)
844
                # This will raise an exception if the sequence is empty
845
                dest_node = seed.choice([nd for nd in attachment_preference
846
                                           if nd not in prohibited_nodes])
847
                # Adding the new edge
848
                G.add_edge(src_node, dest_node)
849

    
850
                # Appending both nodes to add to their preferential attachment
851
                attachment_preference.append(src_node)
852
                attachment_preference.append(dest_node)
853

    
854
                # Adjusting the elligible nodes. Degree may be saturated.
855
                if G.degree(src_node) == clique_degree:
856
                    elligible_nodes.remove(src_node)
857
                if G.degree(dest_node) == clique_degree \
858
                        and dest_node in elligible_nodes:
859
                    elligible_nodes.remove(dest_node)
860

    
861
        # Rewiring m edges, if there are enough edges
862
        elif p <= a_probability < (p + q) and m <= G.size() < clique_size:
863
            # Selecting nodes that have at least 1 edge but that are not
864
            # fully connected to ALL other nodes (center of star).
865
            # These nodes are the pivot nodes of the edges to rewire
866
            elligible_nodes = [nd for nd, deg in G.degree()
867
                               if 0 < deg < clique_degree]
868
            for i in range(m):
869
                # Choosing a random source node
870
                node = seed.choice(elligible_nodes)
871

    
872
                # The available nodes do have a neighbor at least.
873
                neighbor_nodes = list(G[node])
874

    
875
                # Choosing the other end that will get dettached
876
                src_node = seed.choice(neighbor_nodes)
877

    
878
                # Picking a target node that is not 'node' or
879
                # neighbor with 'node', with preferential attachment
880
                neighbor_nodes.append(node)
881
                dest_node = seed.choice([nd for nd in attachment_preference
882
                                           if nd not in neighbor_nodes])
883
                # Rewire
884
                G.remove_edge(node, src_node)
885
                G.add_edge(node, dest_node)
886

    
887
                # Adjusting the preferential attachment list
888
                attachment_preference.remove(src_node)
889
                attachment_preference.append(dest_node)
890

    
891
                # Adjusting the elligible nodes.
892
                # nodes may be saturated or isolated.
893
                if G.degree(src_node) == 0 and src_node in elligible_nodes:
894
                    elligible_nodes.remove(src_node)
895
                if dest_node in elligible_nodes:
896
                    if G.degree(dest_node) == clique_degree:
897
                        elligible_nodes.remove(dest_node)
898
                else:
899
                    if G.degree(dest_node) == 1:
900
                        elligible_nodes.append(dest_node)
901

    
902
        # Adding new node with m edges
903
        else:
904
            # Select the edges' nodes by preferential attachment
905
            targets = _random_subset(attachment_preference, m, seed)
906
            G.add_edges_from(zip([new_node] * m, targets))
907

    
908
            # Add one node to the list for each new edge just created.
909
            attachment_preference.extend(targets)
910
            # The new node has m edges to it, plus itself: m + 1
911
            attachment_preference.extend([new_node] * (m + 1))
912
            new_node += 1
913
    return G
914

    
915

    
916
@py_random_state(3)
917
def powerlaw_cluster_graph(n, m, p, seed=None):
918
    """Holme and Kim algorithm for growing graphs with powerlaw
919
    degree distribution and approximate average clustering.
920

921
    Parameters
922
    ----------
923
    n : int
924
        the number of nodes
925
    m : int
926
        the number of random edges to add for each new node
927
    p : float,
928
        Probability of adding a triangle after adding a random edge
929
    seed : integer, random_state, or None (default)
930
        Indicator of random number generation state.
931
        See :ref:`Randomness<randomness>`.
932

933
    Notes
934
    -----
935
    The average clustering has a hard time getting above a certain
936
    cutoff that depends on `m`.  This cutoff is often quite low.  The
937
    transitivity (fraction of triangles to possible triangles) seems to
938
    decrease with network size.
939

940
    It is essentially the Barabási–Albert (BA) growth model with an
941
    extra step that each random edge is followed by a chance of
942
    making an edge to one of its neighbors too (and thus a triangle).
943

944
    This algorithm improves on BA in the sense that it enables a
945
    higher average clustering to be attained if desired.
946

947
    It seems possible to have a disconnected graph with this algorithm
948
    since the initial `m` nodes may not be all linked to a new node
949
    on the first iteration like the BA model.
950

951
    Raises
952
    ------
953
    NetworkXError
954
        If `m` does not satisfy ``1 <= m <= n`` or `p` does not
955
        satisfy ``0 <= p <= 1``.
956

957
    References
958
    ----------
959
    .. [1] P. Holme and B. J. Kim,
960
       "Growing scale-free networks with tunable clustering",
961
       Phys. Rev. E, 65, 026107, 2002.
962
    """
963

    
964
    if m < 1 or n < m:
965
        raise nx.NetworkXError(
966
            "NetworkXError must have m>1 and m<n, m=%d,n=%d" % (m, n))
967

    
968
    if p > 1 or p < 0:
969
        raise nx.NetworkXError(
970
            "NetworkXError p must be in [0,1], p=%f" % (p))
971

    
972
    G = empty_graph(m)  # add m initial nodes (m0 in barabasi-speak)
973
    repeated_nodes = list(G.nodes())  # list of existing nodes to sample from
974
    # with nodes repeated once for each adjacent edge
975
    source = m               # next node is m
976
    while source < n:        # Now add the other n-1 nodes
977
        possible_targets = _random_subset(repeated_nodes, m, seed)
978
        # do one preferential attachment for new node
979
        target = possible_targets.pop()
980
        G.add_edge(source, target)
981
        repeated_nodes.append(target)  # add one node to list for each new link
982
        count = 1
983
        while count < m:  # add m-1 more new links
984
            if seed.random() < p:  # clustering step: add triangle
985
                neighborhood = [nbr for nbr in G.neighbors(target)
986
                                if not G.has_edge(source, nbr)
987
                                and not nbr == source]
988
                if neighborhood:  # if there is a neighbor without a link
989
                    nbr = seed.choice(neighborhood)
990
                    G.add_edge(source, nbr)  # add triangle
991
                    repeated_nodes.append(nbr)
992
                    count = count + 1
993
                    continue  # go to top of while loop
994
            # else do preferential attachment step if above fails
995
            target = possible_targets.pop()
996
            G.add_edge(source, target)
997
            repeated_nodes.append(target)
998
            count = count + 1
999

    
1000
        repeated_nodes.extend([source] * m)  # add source node to list m times
1001
        source += 1
1002
    return G
1003

    
1004

    
1005
@py_random_state(3)
1006
def random_lobster(n, p1, p2, seed=None):
1007
    """Returns a random lobster graph.
1008

1009
    A lobster is a tree that reduces to a caterpillar when pruning all
1010
    leaf nodes. A caterpillar is a tree that reduces to a path graph
1011
    when pruning all leaf nodes; setting `p2` to zero produces a caterpillar.
1012

1013
    Parameters
1014
    ----------
1015
    n : int
1016
        The expected number of nodes in the backbone
1017
    p1 : float
1018
        Probability of adding an edge to the backbone
1019
    p2 : float
1020
        Probability of adding an edge one level beyond backbone
1021
    seed : integer, random_state, or None (default)
1022
        Indicator of random number generation state.
1023
        See :ref:`Randomness<randomness>`.
1024
    """
1025
    # a necessary ingredient in any self-respecting graph library
1026
    llen = int(2 * seed.random() * n + 0.5)
1027
    L = path_graph(llen)
1028
    # build caterpillar: add edges to path graph with probability p1
1029
    current_node = llen - 1
1030
    for n in range(llen):
1031
        if seed.random() < p1:  # add fuzzy caterpillar parts
1032
            current_node += 1
1033
            L.add_edge(n, current_node)
1034
            if seed.random() < p2:  # add crunchy lobster bits
1035
                current_node += 1
1036
                L.add_edge(current_node - 1, current_node)
1037
    return L  # voila, un lobster!
1038

    
1039

    
1040
@py_random_state(1)
1041
def random_shell_graph(constructor, seed=None):
1042
    """Returns a random shell graph for the constructor given.
1043

1044
    Parameters
1045
    ----------
1046
    constructor : list of three-tuples
1047
        Represents the parameters for a shell, starting at the center
1048
        shell.  Each element of the list must be of the form `(n, m,
1049
        d)`, where `n` is the number of nodes in the shell, `m` is
1050
        the number of edges in the shell, and `d` is the ratio of
1051
        inter-shell (next) edges to intra-shell edges. If `d` is zero,
1052
        there will be no intra-shell edges, and if `d` is one there
1053
        will be all possible intra-shell edges.
1054
    seed : integer, random_state, or None (default)
1055
        Indicator of random number generation state.
1056
        See :ref:`Randomness<randomness>`.
1057

1058
    Examples
1059
    --------
1060
    >>> constructor = [(10, 20, 0.8), (20, 40, 0.8)]
1061
    >>> G = nx.random_shell_graph(constructor)
1062

1063
    """
1064
    G = empty_graph(0)
1065

    
1066
    glist = []
1067
    intra_edges = []
1068
    nnodes = 0
1069
    # create gnm graphs for each shell
1070
    for (n, m, d) in constructor:
1071
        inter_edges = int(m * d)
1072
        intra_edges.append(m - inter_edges)
1073
        g = nx.convert_node_labels_to_integers(
1074
            gnm_random_graph(n, inter_edges, seed=seed),
1075
            first_label=nnodes)
1076
        glist.append(g)
1077
        nnodes += n
1078
        G = nx.operators.union(G, g)
1079

    
1080
    # connect the shells randomly
1081
    for gi in range(len(glist) - 1):
1082
        nlist1 = list(glist[gi])
1083
        nlist2 = list(glist[gi + 1])
1084
        total_edges = intra_edges[gi]
1085
        edge_count = 0
1086
        while edge_count < total_edges:
1087
            u = seed.choice(nlist1)
1088
            v = seed.choice(nlist2)
1089
            if u == v or G.has_edge(u, v):
1090
                continue
1091
            else:
1092
                G.add_edge(u, v)
1093
                edge_count = edge_count + 1
1094
    return G
1095

    
1096

    
1097
@py_random_state(2)
1098
def random_powerlaw_tree(n, gamma=3, seed=None, tries=100):
1099
    """Returns a tree with a power law degree distribution.
1100

1101
    Parameters
1102
    ----------
1103
    n : int
1104
        The number of nodes.
1105
    gamma : float
1106
        Exponent of the power law.
1107
    seed : integer, random_state, or None (default)
1108
        Indicator of random number generation state.
1109
        See :ref:`Randomness<randomness>`.
1110
    tries : int
1111
        Number of attempts to adjust the sequence to make it a tree.
1112

1113
    Raises
1114
    ------
1115
    NetworkXError
1116
        If no valid sequence is found within the maximum number of
1117
        attempts.
1118

1119
    Notes
1120
    -----
1121
    A trial power law degree sequence is chosen and then elements are
1122
    swapped with new elements from a powerlaw distribution until the
1123
    sequence makes a tree (by checking, for example, that the number of
1124
    edges is one smaller than the number of nodes).
1125

1126
    """
1127
    # This call may raise a NetworkXError if the number of tries is succeeded.
1128
    seq = random_powerlaw_tree_sequence(n, gamma=gamma, seed=seed, tries=tries)
1129
    G = degree_sequence_tree(seq)
1130
    return G
1131

    
1132

    
1133
@py_random_state(2)
1134
def random_powerlaw_tree_sequence(n, gamma=3, seed=None, tries=100):
1135
    """Returns a degree sequence for a tree with a power law distribution.
1136

1137
    Parameters
1138
    ----------
1139
    n : int,
1140
        The number of nodes.
1141
    gamma : float
1142
        Exponent of the power law.
1143
    seed : integer, random_state, or None (default)
1144
        Indicator of random number generation state.
1145
        See :ref:`Randomness<randomness>`.
1146
    tries : int
1147
        Number of attempts to adjust the sequence to make it a tree.
1148

1149
    Raises
1150
    ------
1151
    NetworkXError
1152
        If no valid sequence is found within the maximum number of
1153
        attempts.
1154

1155
    Notes
1156
    -----
1157
    A trial power law degree sequence is chosen and then elements are
1158
    swapped with new elements from a power law distribution until
1159
    the sequence makes a tree (by checking, for example, that the number of
1160
    edges is one smaller than the number of nodes).
1161

1162
    """
1163
    # get trial sequence
1164
    z = nx.utils.powerlaw_sequence(n, exponent=gamma, seed=seed)
1165
    # round to integer values in the range [0,n]
1166
    zseq = [min(n, max(int(round(s)), 0)) for s in z]
1167

    
1168
    # another sequence to swap values from
1169
    z = nx.utils.powerlaw_sequence(tries, exponent=gamma, seed=seed)
1170
    # round to integer values in the range [0,n]
1171
    swap = [min(n, max(int(round(s)), 0)) for s in z]
1172

    
1173
    for deg in swap:
1174
        # If this degree sequence can be the degree sequence of a tree, return
1175
        # it. It can be a tree if the number of edges is one fewer than the
1176
        # number of nodes, or in other words, `n - sum(zseq) / 2 == 1`. We
1177
        # use an equivalent condition below that avoids floating point
1178
        # operations.
1179
        if 2 * n - sum(zseq) == 2:
1180
            return zseq
1181
        index = seed.randint(0, n - 1)
1182
        zseq[index] = swap.pop()
1183

    
1184
    raise nx.NetworkXError('Exceeded max (%d) attempts for a valid tree'
1185
                           ' sequence.' % tries)
1186

    
1187

    
1188
@py_random_state(3)
1189
def random_kernel_graph(n, kernel_integral, kernel_root=None, seed=None):
1190
    r"""Returns an random graph based on the specified kernel.
1191

1192
    The algorithm chooses each of the $[n(n-1)]/2$ possible edges with
1193
    probability specified by a kernel $\kappa(x,y)$ [1]_.  The kernel
1194
    $\kappa(x,y)$ must be a symmetric (in $x,y$), non-negative,
1195
    bounded function.
1196

1197
    Parameters
1198
    ----------
1199
    n : int
1200
        The number of nodes
1201
    kernal_integral : function
1202
        Function that returns the definite integral of the kernel $\kappa(x,y)$,
1203
        $F(y,a,b) := \int_a^b \kappa(x,y)dx$
1204
    kernel_root: function (optional)
1205
        Function that returns the root $b$ of the equation $F(y,a,b) = r$.
1206
        If None, the root is found using :func:`scipy.optimize.brentq`
1207
        (this requires SciPy).
1208
    seed : integer, random_state, or None (default)
1209
        Indicator of random number generation state.
1210
        See :ref:`Randomness<randomness>`.
1211

1212
    Notes
1213
    -----
1214
    The kernel is specified through its definite integral which must be
1215
    provided as one of the arguments. If the integral and root of the
1216
    kernel integral can be found in $O(1)$ time then this algorithm runs in
1217
    time $O(n+m)$ where m is the expected number of edges [2]_.
1218

1219
    The nodes are set to integers from $0$ to $n-1$.
1220

1221
    Examples
1222
    --------
1223
    Generate an Erdős–Rényi random graph $G(n,c/n)$, with kernel
1224
    $\kappa(x,y)=c$ where $c$ is the mean expected degree.
1225

1226
    >>> def integral(u, w, z):
1227
    ...     return c * (z - w)
1228
    >>> def root(u, w, r):
1229
    ...     return r / c + w
1230
    >>> c = 1
1231
    >>> graph = nx.random_kernel_graph(1000, integral, root)
1232

1233
    See Also
1234
    --------
1235
    gnp_random_graph
1236
    expected_degree_graph
1237

1238
    References
1239
    ----------
1240
    .. [1] Bollobás, Béla,  Janson, S. and Riordan, O.
1241
       "The phase transition in inhomogeneous random graphs",
1242
       *Random Structures Algorithms*, 31, 3--122, 2007.
1243

1244
    .. [2] Hagberg A, Lemons N (2015),
1245
       "Fast Generation of Sparse Random Kernel Graphs".
1246
       PLoS ONE 10(9): e0135177, 2015. doi:10.1371/journal.pone.0135177
1247
    """
1248
    if kernel_root is None:
1249
        import scipy.optimize as optimize
1250

    
1251
        def kernel_root(y, a, r):
1252
            def my_function(b):
1253
                return kernel_integral(y, a, b) - r
1254
            return optimize.brentq(my_function, a, 1)
1255
    graph = nx.Graph()
1256
    graph.add_nodes_from(range(n))
1257
    (i, j) = (1, 1)
1258
    while i < n:
1259
        r = -math.log(1 - seed.random())  # (1-seed.random()) in (0, 1]
1260
        if kernel_integral(i / n, j / n, 1) <= r:
1261
            i, j = i + 1, i + 1
1262
        else:
1263
            j = int(math.ceil(n * kernel_root(i / n, j / n, r)))
1264
            graph.add_edge(i - 1, j - 1)
1265
    return graph