Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (4.34 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
# Authors: Aric Hagberg (hagberg@lanl.gov)
9
#          Joel Miller (joel.c.miller.research@gmail.com)
10
"""Generate graphs with given degree and triangle sequence.
11
"""
12
import networkx as nx
13
from networkx.utils import py_random_state
14

    
15
__all__ = ['random_clustered_graph']
16

    
17

    
18
@py_random_state(2)
19
def random_clustered_graph(joint_degree_sequence, create_using=None, seed=None):
20
    r"""Generate a random graph with the given joint independent edge degree and
21
    triangle degree sequence.
22

23
    This uses a configuration model-like approach to generate a random graph
24
    (with parallel edges and self-loops) by randomly assigning edges to match
25
    the given joint degree sequence.
26

27
    The joint degree sequence is a list of pairs of integers of the form
28
    $[(d_{1,i}, d_{1,t}), \dotsc, (d_{n,i}, d_{n,t})]$. According to this list,
29
    vertex $u$ is a member of $d_{u,t}$ triangles and has $d_{u, i}$ other
30
    edges. The number $d_{u,t}$ is the *triangle degree* of $u$ and the number
31
    $d_{u,i}$ is the *independent edge degree*.
32

33
    Parameters
34
    ----------
35
    joint_degree_sequence : list of integer pairs
36
        Each list entry corresponds to the independent edge degree and
37
        triangle degree of a node.
38
    create_using : NetworkX graph constructor, optional (default MultiGraph)
39
       Graph type to create. If graph instance, then cleared before populated.
40
    seed : integer, random_state, or None (default)
41
        Indicator of random number generation state.
42
        See :ref:`Randomness<randomness>`.
43

44
    Returns
45
    -------
46
    G : MultiGraph
47
        A graph with the specified degree sequence. Nodes are labeled
48
        starting at 0 with an index corresponding to the position in
49
        deg_sequence.
50

51
    Raises
52
    ------
53
    NetworkXError
54
        If the independent edge degree sequence sum is not even
55
        or the triangle degree sequence sum is not divisible by 3.
56

57
    Notes
58
    -----
59
    As described by Miller [1]_ (see also Newman [2]_ for an equivalent
60
    description).
61

62
    A non-graphical degree sequence (not realizable by some simple
63
    graph) is allowed since this function returns graphs with self
64
    loops and parallel edges.  An exception is raised if the
65
    independent degree sequence does not have an even sum or the
66
    triangle degree sequence sum is not divisible by 3.
67

68
    This configuration model-like construction process can lead to
69
    duplicate edges and loops.  You can remove the self-loops and
70
    parallel edges (see below) which will likely result in a graph
71
    that doesn't have the exact degree sequence specified.  This
72
    "finite-size effect" decreases as the size of the graph increases.
73

74
    References
75
    ----------
76
    .. [1] Joel C. Miller. "Percolation and epidemics in random clustered
77
           networks". In: Physical review. E, Statistical, nonlinear, and soft
78
           matter physics 80 (2 Part 1 August 2009).
79
    .. [2] M. E. J. Newman. "Random Graphs with Clustering".
80
           In: Physical Review Letters 103 (5 July 2009)
81

82
    Examples
83
    --------
84
    >>> deg = [(1, 0), (1, 0), (1, 0), (2, 0), (1, 0), (2, 1), (0, 1), (0, 1)]
85
    >>> G = nx.random_clustered_graph(deg)
86

87
    To remove parallel edges:
88

89
    >>> G = nx.Graph(G)
90

91
    To remove self loops:
92

93
    >>> G.remove_edges_from(nx.selfloop_edges(G))
94

95
    """
96
    # In Python 3, zip() returns an iterator. Make this into a list.
97
    joint_degree_sequence = list(joint_degree_sequence)
98

    
99
    N = len(joint_degree_sequence)
100
    G = nx.empty_graph(N, create_using, default=nx.MultiGraph)
101
    if G.is_directed():
102
        raise nx.NetworkXError("Directed Graph not supported")
103

    
104
    ilist = []
105
    tlist = []
106
    for n in G:
107
        degrees = joint_degree_sequence[n]
108
        for icount in range(degrees[0]):
109
            ilist.append(n)
110
        for tcount in range(degrees[1]):
111
            tlist.append(n)
112

    
113
    if len(ilist) % 2 != 0 or len(tlist) % 3 != 0:
114
        raise nx.NetworkXError('Invalid degree sequence')
115

    
116
    seed.shuffle(ilist)
117
    seed.shuffle(tlist)
118
    while ilist:
119
        G.add_edge(ilist.pop(), ilist.pop())
120
    while tlist:
121
        n1 = tlist.pop()
122
        n2 = tlist.pop()
123
        n3 = tlist.pop()
124
        G.add_edges_from([(n1, n2), (n1, n3), (n2, n3)])
125
    return G