ioftools / networkxMiCe / networkxmaster / networkx / generators / random_clustered.py @ 5cef0f13
History  View  Annotate  Download (4.34 KB)
1 
# * coding: utf8 *


2 
# Copyright (C) 20042019 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 modellike approach to generate a random graph

24 
(with parallel edges and selfloops) 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 nongraphical 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 modellike construction process can lead to

69 
duplicate edges and loops. You can remove the selfloops 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 
"finitesize 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
