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

1"""Functions for generating graphs based on the "duplication" method. 

2 

3These graph generators start with a small initial graph then duplicate 

4nodes and (partially) duplicate their edges. These functions are 

5generally inspired by biological networks. 

6 

7""" 

8import networkx as nx 

9from networkx.exception import NetworkXError 

10from networkx.utils import py_random_state 

11 

12__all__ = ["partial_duplication_graph", "duplication_divergence_graph"] 

13 

14 

15@py_random_state(4) 

16@nx._dispatch(graphs=None) 

17def partial_duplication_graph(N, n, p, q, seed=None): 

18 """Returns a random graph using the partial duplication model. 

19 

20 Parameters 

21 ---------- 

22 N : int 

23 The total number of nodes in the final graph. 

24 

25 n : int 

26 The number of nodes in the initial clique. 

27 

28 p : float 

29 The probability of joining each neighbor of a node to the 

30 duplicate node. Must be a number in the between zero and one, 

31 inclusive. 

32 

33 q : float 

34 The probability of joining the source node to the duplicate 

35 node. Must be a number in the between zero and one, inclusive. 

36 

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

38 Indicator of random number generation state. 

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

40 

41 Notes 

42 ----- 

43 A graph of nodes is grown by creating a fully connected graph 

44 of size `n`. The following procedure is then repeated until 

45 a total of `N` nodes have been reached. 

46 

47 1. A random node, *u*, is picked and a new node, *v*, is created. 

48 2. For each neighbor of *u* an edge from the neighbor to *v* is created 

49 with probability `p`. 

50 3. An edge from *u* to *v* is created with probability `q`. 

51 

52 This algorithm appears in [1]. 

53 

54 This implementation allows the possibility of generating 

55 disconnected graphs. 

56 

57 References 

58 ---------- 

59 .. [1] Knudsen Michael, and Carsten Wiuf. "A Markov chain approach to 

60 randomly grown graphs." Journal of Applied Mathematics 2008. 

61 <https://doi.org/10.1155/2008/190836> 

62 

63 """ 

64 if p < 0 or p > 1 or q < 0 or q > 1: 

65 msg = "partial duplication graph must have 0 <= p, q <= 1." 

66 raise NetworkXError(msg) 

67 if n > N: 

68 raise NetworkXError("partial duplication graph must have n <= N.") 

69 

70 G = nx.complete_graph(n) 

71 for new_node in range(n, N): 

72 # Pick a random vertex, u, already in the graph. 

73 src_node = seed.randint(0, new_node - 1) 

74 

75 # Add a new vertex, v, to the graph. 

76 G.add_node(new_node) 

77 

78 # For each neighbor of u... 

79 for neighbor_node in list(nx.all_neighbors(G, src_node)): 

80 # Add the neighbor to v with probability p. 

81 if seed.random() < p: 

82 G.add_edge(new_node, neighbor_node) 

83 

84 # Join v and u with probability q. 

85 if seed.random() < q: 

86 G.add_edge(new_node, src_node) 

87 return G 

88 

89 

90@py_random_state(2) 

91@nx._dispatch(graphs=None) 

92def duplication_divergence_graph(n, p, seed=None): 

93 """Returns an undirected graph using the duplication-divergence model. 

94 

95 A graph of `n` nodes is created by duplicating the initial nodes 

96 and retaining edges incident to the original nodes with a retention 

97 probability `p`. 

98 

99 Parameters 

100 ---------- 

101 n : int 

102 The desired number of nodes in the graph. 

103 p : float 

104 The probability for retaining the edge of the replicated node. 

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

106 Indicator of random number generation state. 

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

108 

109 Returns 

110 ------- 

111 G : Graph 

112 

113 Raises 

114 ------ 

115 NetworkXError 

116 If `p` is not a valid probability. 

117 If `n` is less than 2. 

118 

119 Notes 

120 ----- 

121 This algorithm appears in [1]. 

122 

123 This implementation disallows the possibility of generating 

124 disconnected graphs. 

125 

126 References 

127 ---------- 

128 .. [1] I. Ispolatov, P. L. Krapivsky, A. Yuryev, 

129 "Duplication-divergence model of protein interaction network", 

130 Phys. Rev. E, 71, 061911, 2005. 

131 

132 """ 

133 if p > 1 or p < 0: 

134 msg = f"NetworkXError p={p} is not in [0,1]." 

135 raise nx.NetworkXError(msg) 

136 if n < 2: 

137 msg = "n must be greater than or equal to 2" 

138 raise nx.NetworkXError(msg) 

139 

140 G = nx.Graph() 

141 

142 # Initialize the graph with two connected nodes. 

143 G.add_edge(0, 1) 

144 i = 2 

145 while i < n: 

146 # Choose a random node from current graph to duplicate. 

147 random_node = seed.choice(list(G)) 

148 # Make the replica. 

149 G.add_node(i) 

150 # flag indicates whether at least one edge is connected on the replica. 

151 flag = False 

152 for nbr in G.neighbors(random_node): 

153 if seed.random() < p: 

154 # Link retention step. 

155 G.add_edge(i, nbr) 

156 flag = True 

157 if not flag: 

158 # Delete replica if no edges retained. 

159 G.remove_node(i) 

160 else: 

161 # Successful duplication. 

162 i += 1 

163 return G