ioftools / networkxMiCe / networkxmaster / networkx / generators / duplication.py @ 5cef0f13
History  View  Annotate  Download (5.21 KB)
1 
# duplication.py  functions for generating graphs by duplicating nodes


2 
#

3 
# Copyright 20162019 NetworkX developers.

4 
# Copyright (C) 20042019 by

5 
# Aric Hagberg <hagberg@lanl.gov>

6 
# Dan Schult <dschult@colgate.edu>

7 
# Pieter Swart <swart@lanl.gov>

8 
#

9 
# This file is part of NetworkX.

10 
#

11 
# NetworkX is distributed under a BSD license; see LICENSE.txt for more

12 
# information.

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

14 

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

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

17 
generally inspired by biological networks.

18 

19 
"""

20 
import networkx as nx 
21 
from networkx.utils import py_random_state 
22 
from networkx.exception import NetworkXError 
23  
24 
__all__ = ['partial_duplication_graph', 'duplication_divergence_graph'] 
25  
26  
27 
@py_random_state(4) 
28 
def partial_duplication_graph(N, n, p, q, seed=None): 
29 
"""Returns a random graph using the partial duplication model.

30 

31 
Parameters

32 


33 
N : int

34 
The total number of nodes in the final graph.

35 

36 
n : int

37 
The number of nodes in the initial clique.

38 

39 
p : float

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

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

42 
inclusive.

43 

44 
q : float

45 
The probability of joining the source node to the duplicate

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

47 

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

49 
Indicator of random number generation state.

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

51 

52 
Notes

53 


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

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

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

57 

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

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

60 
with probability `p`.

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

62 

63 
This algorithm appears in [1].

64 

65 
This implementation allows the possibility of generating

66 
disconnected graphs.

67 

68 
References

69 


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

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

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

73 

74 
"""

75 
if p < 0 or p > 1 or q < 0 or q > 1: 
76 
msg = "partial duplication graph must have 0 <= p, q <= 1."

77 
raise NetworkXError(msg)

78 
if n > N:

79 
raise NetworkXError("partial duplication graph must have n <= N.") 
80  
81 
G = nx.complete_graph(n) 
82 
for new_node in range(n, N): 
83 
# Add a new vertex, v, to the graph.

84 
G.add_node(new_node) 
85  
86 
# Pick a random vertex, u, already in the graph.

87 
src_node = seed.randint(0, new_node)

88  
89 
# Join v and u with probability q.

90 
if seed.random() < q:

91 
G.add_edge(new_node, src_node) 
92  
93 
# For each neighbor of u...

94 
for neighbor_node in list(nx.all_neighbors(G, src_node)): 
95 
# Add the neighbor to v with probability p.

96 
if seed.random() < p:

97 
G.add_edge(new_node, neighbor_node) 
98 
return G

99  
100  
101 
@py_random_state(2) 
102 
def duplication_divergence_graph(n, p, seed=None): 
103 
"""Returns an undirected graph using the duplicationdivergence model.

104 

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

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

107 
probability `p`.

108 

109 
Parameters

110 


111 
n : int

112 
The desired number of nodes in the graph.

113 
p : float

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

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

116 
Indicator of random number generation state.

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

118 

119 
Returns

120 


121 
G : Graph

122 

123 
Raises

124 


125 
NetworkXError

126 
If `p` is not a valid probability.

127 
If `n` is less than 2.

128 

129 
Notes

130 


131 
This algorithm appears in [1].

132 

133 
This implementation disallows the possibility of generating

134 
disconnected graphs.

135 

136 
References

137 


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

139 
"Duplicationdivergence model of protein interaction network",

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

141 

142 
"""

143 
if p > 1 or p < 0: 
144 
msg = "NetworkXError p={0} is not in [0,1].".format(p)

145 
raise nx.NetworkXError(msg)

146 
if n < 2: 
147 
msg = 'n must be greater than or equal to 2'

148 
raise nx.NetworkXError(msg)

149  
150 
G = nx.Graph() 
151  
152 
# Initialize the graph with two connected nodes.

153 
G.add_edge(0, 1) 
154 
i = 2

155 
while i < n:

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

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

158 
# Make the replica.

159 
G.add_node(i) 
160 
# flag indicates whether at least one edge is connected on the replica.

161 
flag = False

162 
for nbr in G.neighbors(random_node): 
163 
if seed.random() < p:

164 
# Link retention step.

165 
G.add_edge(i, nbr) 
166 
flag = True

167 
if not flag: 
168 
# Delete replica if no edges retained.

169 
G.remove_node(i) 
170 
else:

171 
# Successful duplication.

172 
i += 1

173 
return G
