Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/smallworld.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """Functions for estimating the small-world-ness of graphs. | |
2 | |
3 A small world network is characterized by a small average shortest path length, | |
4 and a large clustering coefficient. | |
5 | |
6 Small-worldness is commonly measured with the coefficient sigma or omega. | |
7 | |
8 Both coefficients compare the average clustering coefficient and shortest path | |
9 length of a given graph against the same quantities for an equivalent random | |
10 or lattice graph. | |
11 | |
12 For more information, see the Wikipedia article on small-world network [1]_. | |
13 | |
14 .. [1] Small-world network:: https://en.wikipedia.org/wiki/Small-world_network | |
15 | |
16 """ | |
17 import networkx as nx | |
18 from networkx.utils import not_implemented_for | |
19 from networkx.utils import py_random_state | |
20 | |
21 __all__ = ["random_reference", "lattice_reference", "sigma", "omega"] | |
22 | |
23 | |
24 @py_random_state(3) | |
25 @not_implemented_for("directed") | |
26 @not_implemented_for("multigraph") | |
27 def random_reference(G, niter=1, connectivity=True, seed=None): | |
28 """Compute a random graph by swapping edges of a given graph. | |
29 | |
30 Parameters | |
31 ---------- | |
32 G : graph | |
33 An undirected graph with 4 or more nodes. | |
34 | |
35 niter : integer (optional, default=1) | |
36 An edge is rewired approximately `niter` times. | |
37 | |
38 connectivity : boolean (optional, default=True) | |
39 When True, ensure connectivity for the randomized graph. | |
40 | |
41 seed : integer, random_state, or None (default) | |
42 Indicator of random number generation state. | |
43 See :ref:`Randomness<randomness>`. | |
44 | |
45 Returns | |
46 ------- | |
47 G : graph | |
48 The randomized graph. | |
49 | |
50 Notes | |
51 ----- | |
52 The implementation is adapted from the algorithm by Maslov and Sneppen | |
53 (2002) [1]_. | |
54 | |
55 References | |
56 ---------- | |
57 .. [1] Maslov, Sergei, and Kim Sneppen. | |
58 "Specificity and stability in topology of protein networks." | |
59 Science 296.5569 (2002): 910-913. | |
60 """ | |
61 if G.is_directed(): | |
62 msg = "random_reference() not defined for directed graphs." | |
63 raise nx.NetworkXError(msg) | |
64 if len(G) < 4: | |
65 raise nx.NetworkXError("Graph has less than four nodes.") | |
66 | |
67 from networkx.utils import cumulative_distribution, discrete_sequence | |
68 | |
69 local_conn = nx.connectivity.local_edge_connectivity | |
70 | |
71 G = G.copy() | |
72 keys, degrees = zip(*G.degree()) # keys, degree | |
73 cdf = cumulative_distribution(degrees) # cdf of degree | |
74 nnodes = len(G) | |
75 nedges = nx.number_of_edges(G) | |
76 niter = niter * nedges | |
77 ntries = int(nnodes * nedges / (nnodes * (nnodes - 1) / 2)) | |
78 swapcount = 0 | |
79 | |
80 for i in range(niter): | |
81 n = 0 | |
82 while n < ntries: | |
83 # pick two random edges without creating edge list | |
84 # choose source node indices from discrete distribution | |
85 (ai, ci) = discrete_sequence(2, cdistribution=cdf, seed=seed) | |
86 if ai == ci: | |
87 continue # same source, skip | |
88 a = keys[ai] # convert index to label | |
89 c = keys[ci] | |
90 # choose target uniformly from neighbors | |
91 b = seed.choice(list(G.neighbors(a))) | |
92 d = seed.choice(list(G.neighbors(c))) | |
93 bi = keys.index(b) | |
94 di = keys.index(d) | |
95 if b in [a, c, d] or d in [a, b, c]: | |
96 continue # all vertices should be different | |
97 | |
98 # don't create parallel edges | |
99 if (d not in G[a]) and (b not in G[c]): | |
100 G.add_edge(a, d) | |
101 G.add_edge(c, b) | |
102 G.remove_edge(a, b) | |
103 G.remove_edge(c, d) | |
104 | |
105 # Check if the graph is still connected | |
106 if connectivity and local_conn(G, a, b) == 0: | |
107 # Not connected, revert the swap | |
108 G.remove_edge(a, d) | |
109 G.remove_edge(c, b) | |
110 G.add_edge(a, b) | |
111 G.add_edge(c, d) | |
112 else: | |
113 swapcount += 1 | |
114 break | |
115 n += 1 | |
116 return G | |
117 | |
118 | |
119 @py_random_state(4) | |
120 @not_implemented_for("directed") | |
121 @not_implemented_for("multigraph") | |
122 def lattice_reference(G, niter=1, D=None, connectivity=True, seed=None): | |
123 """Latticize the given graph by swapping edges. | |
124 | |
125 Parameters | |
126 ---------- | |
127 G : graph | |
128 An undirected graph with 4 or more nodes. | |
129 | |
130 niter : integer (optional, default=1) | |
131 An edge is rewired approximatively niter times. | |
132 | |
133 D : numpy.array (optional, default=None) | |
134 Distance to the diagonal matrix. | |
135 | |
136 connectivity : boolean (optional, default=True) | |
137 Ensure connectivity for the latticized graph when set to True. | |
138 | |
139 seed : integer, random_state, or None (default) | |
140 Indicator of random number generation state. | |
141 See :ref:`Randomness<randomness>`. | |
142 | |
143 Returns | |
144 ------- | |
145 G : graph | |
146 The latticized graph. | |
147 | |
148 Notes | |
149 ----- | |
150 The implementation is adapted from the algorithm by Sporns et al. [1]_. | |
151 which is inspired from the original work by Maslov and Sneppen(2002) [2]_. | |
152 | |
153 References | |
154 ---------- | |
155 .. [1] Sporns, Olaf, and Jonathan D. Zwi. | |
156 "The small world of the cerebral cortex." | |
157 Neuroinformatics 2.2 (2004): 145-162. | |
158 .. [2] Maslov, Sergei, and Kim Sneppen. | |
159 "Specificity and stability in topology of protein networks." | |
160 Science 296.5569 (2002): 910-913. | |
161 """ | |
162 import numpy as np | |
163 from networkx.utils import cumulative_distribution, discrete_sequence | |
164 | |
165 local_conn = nx.connectivity.local_edge_connectivity | |
166 | |
167 if G.is_directed(): | |
168 msg = "lattice_reference() not defined for directed graphs." | |
169 raise nx.NetworkXError(msg) | |
170 if len(G) < 4: | |
171 raise nx.NetworkXError("Graph has less than four nodes.") | |
172 # Instead of choosing uniformly at random from a generated edge list, | |
173 # this algorithm chooses nonuniformly from the set of nodes with | |
174 # probability weighted by degree. | |
175 G = G.copy() | |
176 keys, degrees = zip(*G.degree()) # keys, degree | |
177 cdf = cumulative_distribution(degrees) # cdf of degree | |
178 | |
179 nnodes = len(G) | |
180 nedges = nx.number_of_edges(G) | |
181 if D is None: | |
182 D = np.zeros((nnodes, nnodes)) | |
183 un = np.arange(1, nnodes) | |
184 um = np.arange(nnodes - 1, 0, -1) | |
185 u = np.append((0,), np.where(un < um, un, um)) | |
186 | |
187 for v in range(int(np.ceil(nnodes / 2))): | |
188 D[nnodes - v - 1, :] = np.append(u[v + 1 :], u[: v + 1]) | |
189 D[v, :] = D[nnodes - v - 1, :][::-1] | |
190 | |
191 niter = niter * nedges | |
192 ntries = int(nnodes * nedges / (nnodes * (nnodes - 1) / 2)) | |
193 swapcount = 0 | |
194 | |
195 for i in range(niter): | |
196 n = 0 | |
197 while n < ntries: | |
198 # pick two random edges without creating edge list | |
199 # choose source node indices from discrete distribution | |
200 (ai, ci) = discrete_sequence(2, cdistribution=cdf, seed=seed) | |
201 if ai == ci: | |
202 continue # same source, skip | |
203 a = keys[ai] # convert index to label | |
204 c = keys[ci] | |
205 # choose target uniformly from neighbors | |
206 b = seed.choice(list(G.neighbors(a))) | |
207 d = seed.choice(list(G.neighbors(c))) | |
208 bi = keys.index(b) | |
209 di = keys.index(d) | |
210 | |
211 if b in [a, c, d] or d in [a, b, c]: | |
212 continue # all vertices should be different | |
213 | |
214 # don't create parallel edges | |
215 if (d not in G[a]) and (b not in G[c]): | |
216 if D[ai, bi] + D[ci, di] >= D[ai, ci] + D[bi, di]: | |
217 # only swap if we get closer to the diagonal | |
218 G.add_edge(a, d) | |
219 G.add_edge(c, b) | |
220 G.remove_edge(a, b) | |
221 G.remove_edge(c, d) | |
222 | |
223 # Check if the graph is still connected | |
224 if connectivity and local_conn(G, a, b) == 0: | |
225 # Not connected, revert the swap | |
226 G.remove_edge(a, d) | |
227 G.remove_edge(c, b) | |
228 G.add_edge(a, b) | |
229 G.add_edge(c, d) | |
230 else: | |
231 swapcount += 1 | |
232 break | |
233 n += 1 | |
234 | |
235 return G | |
236 | |
237 | |
238 @py_random_state(3) | |
239 @not_implemented_for("directed") | |
240 @not_implemented_for("multigraph") | |
241 def sigma(G, niter=100, nrand=10, seed=None): | |
242 """Returns the small-world coefficient (sigma) of the given graph. | |
243 | |
244 The small-world coefficient is defined as: | |
245 sigma = C/Cr / L/Lr | |
246 where C and L are respectively the average clustering coefficient and | |
247 average shortest path length of G. Cr and Lr are respectively the average | |
248 clustering coefficient and average shortest path length of an equivalent | |
249 random graph. | |
250 | |
251 A graph is commonly classified as small-world if sigma>1. | |
252 | |
253 Parameters | |
254 ---------- | |
255 G : NetworkX graph | |
256 An undirected graph. | |
257 niter : integer (optional, default=100) | |
258 Approximate number of rewiring per edge to compute the equivalent | |
259 random graph. | |
260 nrand : integer (optional, default=10) | |
261 Number of random graphs generated to compute the average clustering | |
262 coefficient (Cr) and average shortest path length (Lr). | |
263 seed : integer, random_state, or None (default) | |
264 Indicator of random number generation state. | |
265 See :ref:`Randomness<randomness>`. | |
266 | |
267 Returns | |
268 ------- | |
269 sigma : float | |
270 The small-world coefficient of G. | |
271 | |
272 Notes | |
273 ----- | |
274 The implementation is adapted from Humphries et al. [1]_ [2]_. | |
275 | |
276 References | |
277 ---------- | |
278 .. [1] The brainstem reticular formation is a small-world, not scale-free, | |
279 network M. D. Humphries, K. Gurney and T. J. Prescott, | |
280 Proc. Roy. Soc. B 2006 273, 503-511, doi:10.1098/rspb.2005.3354. | |
281 .. [2] Humphries and Gurney (2008). | |
282 "Network 'Small-World-Ness': A Quantitative Method for Determining | |
283 Canonical Network Equivalence". | |
284 PLoS One. 3 (4). PMID 18446219. doi:10.1371/journal.pone.0002051. | |
285 """ | |
286 import numpy as np | |
287 | |
288 # Compute the mean clustering coefficient and average shortest path length | |
289 # for an equivalent random graph | |
290 randMetrics = {"C": [], "L": []} | |
291 for i in range(nrand): | |
292 Gr = random_reference(G, niter=niter, seed=seed) | |
293 randMetrics["C"].append(nx.transitivity(Gr)) | |
294 randMetrics["L"].append(nx.average_shortest_path_length(Gr)) | |
295 | |
296 C = nx.transitivity(G) | |
297 L = nx.average_shortest_path_length(G) | |
298 Cr = np.mean(randMetrics["C"]) | |
299 Lr = np.mean(randMetrics["L"]) | |
300 | |
301 sigma = (C / Cr) / (L / Lr) | |
302 | |
303 return sigma | |
304 | |
305 | |
306 @py_random_state(3) | |
307 @not_implemented_for("directed") | |
308 @not_implemented_for("multigraph") | |
309 def omega(G, niter=100, nrand=10, seed=None): | |
310 """Returns the small-world coefficient (omega) of a graph | |
311 | |
312 The small-world coefficient of a graph G is: | |
313 | |
314 omega = Lr/L - C/Cl | |
315 | |
316 where C and L are respectively the average clustering coefficient and | |
317 average shortest path length of G. Lr is the average shortest path length | |
318 of an equivalent random graph and Cl is the average clustering coefficient | |
319 of an equivalent lattice graph. | |
320 | |
321 The small-world coefficient (omega) ranges between -1 and 1. Values close | |
322 to 0 means the G features small-world characteristics. Values close to -1 | |
323 means G has a lattice shape whereas values close to 1 means G is a random | |
324 graph. | |
325 | |
326 Parameters | |
327 ---------- | |
328 G : NetworkX graph | |
329 An undirected graph. | |
330 | |
331 niter: integer (optional, default=100) | |
332 Approximate number of rewiring per edge to compute the equivalent | |
333 random graph. | |
334 | |
335 nrand: integer (optional, default=10) | |
336 Number of random graphs generated to compute the average clustering | |
337 coefficient (Cr) and average shortest path length (Lr). | |
338 | |
339 seed : integer, random_state, or None (default) | |
340 Indicator of random number generation state. | |
341 See :ref:`Randomness<randomness>`. | |
342 | |
343 | |
344 Returns | |
345 ------- | |
346 omega : float | |
347 The small-work coefficient (omega) | |
348 | |
349 Notes | |
350 ----- | |
351 The implementation is adapted from the algorithm by Telesford et al. [1]_. | |
352 | |
353 References | |
354 ---------- | |
355 .. [1] Telesford, Joyce, Hayasaka, Burdette, and Laurienti (2011). | |
356 "The Ubiquity of Small-World Networks". | |
357 Brain Connectivity. 1 (0038): 367-75. PMC 3604768. PMID 22432451. | |
358 doi:10.1089/brain.2011.0038. | |
359 """ | |
360 import numpy as np | |
361 | |
362 # Compute the mean clustering coefficient and average shortest path length | |
363 # for an equivalent random graph | |
364 randMetrics = {"C": [], "L": []} | |
365 for i in range(nrand): | |
366 Gr = random_reference(G, niter=niter, seed=seed) | |
367 Gl = lattice_reference(G, niter=niter, seed=seed) | |
368 randMetrics["C"].append(nx.transitivity(Gl)) | |
369 randMetrics["L"].append(nx.average_shortest_path_length(Gr)) | |
370 | |
371 C = nx.transitivity(G) | |
372 L = nx.average_shortest_path_length(G) | |
373 Cl = np.mean(randMetrics["C"]) | |
374 Lr = np.mean(randMetrics["L"]) | |
375 | |
376 omega = (Lr / L) - (C / Cl) | |
377 | |
378 return omega |