Mercurial > repos > guerler > springsuite

comparison planemo/lib/python3.7/site-packages/networkx/generators/duplication.py @ 1:56ad4e20f292 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
author guerler
date Fri, 31 Jul 2020 00:32:28 -0400
parents
children
comparison
equal deleted inserted replaced
0:d30785e31577 1:56ad4e20f292
1 # duplication.py - functions for generating graphs by duplicating nodes
2 #
3 # Copyright 2016-2019 NetworkX developers.
4 # Copyright (C) 2004-2019 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 # Pick a random vertex, u, already in the graph.
84 src_node = seed.randint(0, new_node - 1)
85
86 # Add a new vertex, v, to the graph.
87 G.add_node(new_node)
88
89 # For each neighbor of u...
90 for neighbor_node in list(nx.all_neighbors(G, src_node)):
91 # Add the neighbor to v with probability p.
92 if seed.random() < p:
93 G.add_edge(new_node, neighbor_node)
94
95 # Join v and u with probability q.
96 if seed.random() < q:
97 G.add_edge(new_node, src_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 duplication-divergence 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 "Duplication-divergence 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