Mercurial > repos > guerler > springsuite
comparison planemo/lib/python3.7/site-packages/networkx/generators/duplication.py @ 1:56ad4e20f292 draft
"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 |