Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/generators/random_clustered.py: 19%

1"""Generate graphs with given degree and triangle sequence. 

2""" 

3import networkx as nx 

4from networkx.utils import py_random_state 

5 

6__all__ = ["random_clustered_graph"] 

7 

8 

9@py_random_state(2) 

10@nx._dispatch(graphs=None) 

11def random_clustered_graph(joint_degree_sequence, create_using=None, seed=None): 

12 r"""Generate a random graph with the given joint independent edge degree and 

13 triangle degree sequence. 

14 

15 This uses a configuration model-like approach to generate a random graph 

16 (with parallel edges and self-loops) by randomly assigning edges to match 

17 the given joint degree sequence. 

18 

19 The joint degree sequence is a list of pairs of integers of the form 

20 $[(d_{1,i}, d_{1,t}), \dotsc, (d_{n,i}, d_{n,t})]$. According to this list, 

21 vertex $u$ is a member of $d_{u,t}$ triangles and has $d_{u, i}$ other 

22 edges. The number $d_{u,t}$ is the *triangle degree* of $u$ and the number 

23 $d_{u,i}$ is the *independent edge degree*. 

24 

25 Parameters 

26 ---------- 

27 joint_degree_sequence : list of integer pairs 

28 Each list entry corresponds to the independent edge degree and 

29 triangle degree of a node. 

30 create_using : NetworkX graph constructor, optional (default MultiGraph) 

31 Graph type to create. If graph instance, then cleared before populated. 

32 seed : integer, random_state, or None (default) 

33 Indicator of random number generation state. 

34 See :ref:`Randomness<randomness>`. 

35 

36 Returns 

37 ------- 

38 G : MultiGraph 

39 A graph with the specified degree sequence. Nodes are labeled 

40 starting at 0 with an index corresponding to the position in 

41 deg_sequence. 

42 

43 Raises 

44 ------ 

45 NetworkXError 

46 If the independent edge degree sequence sum is not even 

47 or the triangle degree sequence sum is not divisible by 3. 

48 

49 Notes 

50 ----- 

51 As described by Miller [1]_ (see also Newman [2]_ for an equivalent 

52 description). 

53 

54 A non-graphical degree sequence (not realizable by some simple 

55 graph) is allowed since this function returns graphs with self 

56 loops and parallel edges. An exception is raised if the 

57 independent degree sequence does not have an even sum or the 

58 triangle degree sequence sum is not divisible by 3. 

59 

60 This configuration model-like construction process can lead to 

61 duplicate edges and loops. You can remove the self-loops and 

62 parallel edges (see below) which will likely result in a graph 

63 that doesn't have the exact degree sequence specified. This 

64 "finite-size effect" decreases as the size of the graph increases. 

65 

66 References 

67 ---------- 

68 .. [1] Joel C. Miller. "Percolation and epidemics in random clustered 

69 networks". In: Physical review. E, Statistical, nonlinear, and soft 

70 matter physics 80 (2 Part 1 August 2009). 

71 .. [2] M. E. J. Newman. "Random Graphs with Clustering". 

72 In: Physical Review Letters 103 (5 July 2009) 

73 

74 Examples 

75 -------- 

76 >>> deg = [(1, 0), (1, 0), (1, 0), (2, 0), (1, 0), (2, 1), (0, 1), (0, 1)] 

77 >>> G = nx.random_clustered_graph(deg) 

78 

79 To remove parallel edges: 

80 

81 >>> G = nx.Graph(G) 

82 

83 To remove self loops: 

84 

85 >>> G.remove_edges_from(nx.selfloop_edges(G)) 

86 

87 """ 

88 # In Python 3, zip() returns an iterator. Make this into a list. 

89 joint_degree_sequence = list(joint_degree_sequence) 

90 

91 N = len(joint_degree_sequence) 

92 G = nx.empty_graph(N, create_using, default=nx.MultiGraph) 

93 if G.is_directed(): 

94 raise nx.NetworkXError("Directed Graph not supported") 

95 

96 ilist = [] 

97 tlist = [] 

98 for n in G: 

99 degrees = joint_degree_sequence[n] 

100 for icount in range(degrees[0]): 

101 ilist.append(n) 

102 for tcount in range(degrees[1]): 

103 tlist.append(n) 

104 

105 if len(ilist) % 2 != 0 or len(tlist) % 3 != 0: 

106 raise nx.NetworkXError("Invalid degree sequence") 

107 

108 seed.shuffle(ilist) 

109 seed.shuffle(tlist) 

110 while ilist: 

111 G.add_edge(ilist.pop(), ilist.pop()) 

112 while tlist: 

113 n1 = tlist.pop() 

114 n2 = tlist.pop() 

115 n3 = tlist.pop() 

116 G.add_edges_from([(n1, n2), (n1, n3), (n2, n3)]) 

117 return G