Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/smallworld.py: 16%
142 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""Functions for estimating the small-world-ness of graphs.
3A small world network is characterized by a small average shortest path length,
4and a large clustering coefficient.
6Small-worldness is commonly measured with the coefficient sigma or omega.
8Both coefficients compare the average clustering coefficient and shortest path
9length of a given graph against the same quantities for an equivalent random
10or lattice graph.
12For more information, see the Wikipedia article on small-world network [1]_.
14.. [1] Small-world network:: https://en.wikipedia.org/wiki/Small-world_network
16"""
17import networkx as nx
18from networkx.utils import not_implemented_for, py_random_state
20__all__ = ["random_reference", "lattice_reference", "sigma", "omega"]
23@not_implemented_for("directed")
24@not_implemented_for("multigraph")
25@py_random_state(3)
26@nx._dispatch
27def random_reference(G, niter=1, connectivity=True, seed=None):
28 """Compute a random graph by swapping edges of a given graph.
30 Parameters
31 ----------
32 G : graph
33 An undirected graph with 4 or more nodes.
35 niter : integer (optional, default=1)
36 An edge is rewired approximately `niter` times.
38 connectivity : boolean (optional, default=True)
39 When True, ensure connectivity for the randomized graph.
41 seed : integer, random_state, or None (default)
42 Indicator of random number generation state.
43 See :ref:`Randomness<randomness>`.
45 Returns
46 -------
47 G : graph
48 The randomized graph.
50 Raises
51 ------
52 NetworkXError
53 If there are fewer than 4 nodes or 2 edges in `G`
55 Notes
56 -----
57 The implementation is adapted from the algorithm by Maslov and Sneppen
58 (2002) [1]_.
60 References
61 ----------
62 .. [1] Maslov, Sergei, and Kim Sneppen.
63 "Specificity and stability in topology of protein networks."
64 Science 296.5569 (2002): 910-913.
65 """
66 if len(G) < 4:
67 raise nx.NetworkXError("Graph has fewer than four nodes.")
68 if len(G.edges) < 2:
69 raise nx.NetworkXError("Graph has fewer that 2 edges")
71 from networkx.utils import cumulative_distribution, discrete_sequence
73 local_conn = nx.connectivity.local_edge_connectivity
75 G = G.copy()
76 keys, degrees = zip(*G.degree()) # keys, degree
77 cdf = cumulative_distribution(degrees) # cdf of degree
78 nnodes = len(G)
79 nedges = nx.number_of_edges(G)
80 niter = niter * nedges
81 ntries = int(nnodes * nedges / (nnodes * (nnodes - 1) / 2))
82 swapcount = 0
84 for i in range(niter):
85 n = 0
86 while n < ntries:
87 # pick two random edges without creating edge list
88 # choose source node indices from discrete distribution
89 (ai, ci) = discrete_sequence(2, cdistribution=cdf, seed=seed)
90 if ai == ci:
91 continue # same source, skip
92 a = keys[ai] # convert index to label
93 c = keys[ci]
94 # choose target uniformly from neighbors
95 b = seed.choice(list(G.neighbors(a)))
96 d = seed.choice(list(G.neighbors(c)))
97 if b in [a, c, d] or d in [a, b, c]:
98 continue # all vertices should be different
100 # don't create parallel edges
101 if (d not in G[a]) and (b not in G[c]):
102 G.add_edge(a, d)
103 G.add_edge(c, b)
104 G.remove_edge(a, b)
105 G.remove_edge(c, d)
107 # Check if the graph is still connected
108 if connectivity and local_conn(G, a, b) == 0:
109 # Not connected, revert the swap
110 G.remove_edge(a, d)
111 G.remove_edge(c, b)
112 G.add_edge(a, b)
113 G.add_edge(c, d)
114 else:
115 swapcount += 1
116 break
117 n += 1
118 return G
121@not_implemented_for("directed")
122@not_implemented_for("multigraph")
123@py_random_state(4)
124@nx._dispatch
125def lattice_reference(G, niter=5, D=None, connectivity=True, seed=None):
126 """Latticize the given graph by swapping edges.
128 Parameters
129 ----------
130 G : graph
131 An undirected graph.
133 niter : integer (optional, default=1)
134 An edge is rewired approximately niter times.
136 D : numpy.array (optional, default=None)
137 Distance to the diagonal matrix.
139 connectivity : boolean (optional, default=True)
140 Ensure connectivity for the latticized graph when set to True.
142 seed : integer, random_state, or None (default)
143 Indicator of random number generation state.
144 See :ref:`Randomness<randomness>`.
146 Returns
147 -------
148 G : graph
149 The latticized graph.
151 Raises
152 ------
153 NetworkXError
154 If there are fewer than 4 nodes or 2 edges in `G`
156 Notes
157 -----
158 The implementation is adapted from the algorithm by Sporns et al. [1]_.
159 which is inspired from the original work by Maslov and Sneppen(2002) [2]_.
161 References
162 ----------
163 .. [1] Sporns, Olaf, and Jonathan D. Zwi.
164 "The small world of the cerebral cortex."
165 Neuroinformatics 2.2 (2004): 145-162.
166 .. [2] Maslov, Sergei, and Kim Sneppen.
167 "Specificity and stability in topology of protein networks."
168 Science 296.5569 (2002): 910-913.
169 """
170 import numpy as np
172 from networkx.utils import cumulative_distribution, discrete_sequence
174 local_conn = nx.connectivity.local_edge_connectivity
176 if len(G) < 4:
177 raise nx.NetworkXError("Graph has fewer than four nodes.")
178 if len(G.edges) < 2:
179 raise nx.NetworkXError("Graph has fewer that 2 edges")
180 # Instead of choosing uniformly at random from a generated edge list,
181 # this algorithm chooses nonuniformly from the set of nodes with
182 # probability weighted by degree.
183 G = G.copy()
184 keys, degrees = zip(*G.degree()) # keys, degree
185 cdf = cumulative_distribution(degrees) # cdf of degree
187 nnodes = len(G)
188 nedges = nx.number_of_edges(G)
189 if D is None:
190 D = np.zeros((nnodes, nnodes))
191 un = np.arange(1, nnodes)
192 um = np.arange(nnodes - 1, 0, -1)
193 u = np.append((0,), np.where(un < um, un, um))
195 for v in range(int(np.ceil(nnodes / 2))):
196 D[nnodes - v - 1, :] = np.append(u[v + 1 :], u[: v + 1])
197 D[v, :] = D[nnodes - v - 1, :][::-1]
199 niter = niter * nedges
200 # maximal number of rewiring attempts per 'niter'
201 max_attempts = int(nnodes * nedges / (nnodes * (nnodes - 1) / 2))
203 for _ in range(niter):
204 n = 0
205 while n < max_attempts:
206 # pick two random edges without creating edge list
207 # choose source node indices from discrete distribution
208 (ai, ci) = discrete_sequence(2, cdistribution=cdf, seed=seed)
209 if ai == ci:
210 continue # same source, skip
211 a = keys[ai] # convert index to label
212 c = keys[ci]
213 # choose target uniformly from neighbors
214 b = seed.choice(list(G.neighbors(a)))
215 d = seed.choice(list(G.neighbors(c)))
216 bi = keys.index(b)
217 di = keys.index(d)
219 if b in [a, c, d] or d in [a, b, c]:
220 continue # all vertices should be different
222 # don't create parallel edges
223 if (d not in G[a]) and (b not in G[c]):
224 if D[ai, bi] + D[ci, di] >= D[ai, ci] + D[bi, di]:
225 # only swap if we get closer to the diagonal
226 G.add_edge(a, d)
227 G.add_edge(c, b)
228 G.remove_edge(a, b)
229 G.remove_edge(c, d)
231 # Check if the graph is still connected
232 if connectivity and local_conn(G, a, b) == 0:
233 # Not connected, revert the swap
234 G.remove_edge(a, d)
235 G.remove_edge(c, b)
236 G.add_edge(a, b)
237 G.add_edge(c, d)
238 else:
239 break
240 n += 1
242 return G
245@not_implemented_for("directed")
246@not_implemented_for("multigraph")
247@py_random_state(3)
248@nx._dispatch
249def sigma(G, niter=100, nrand=10, seed=None):
250 """Returns the small-world coefficient (sigma) of the given graph.
252 The small-world coefficient is defined as:
253 sigma = C/Cr / L/Lr
254 where C and L are respectively the average clustering coefficient and
255 average shortest path length of G. Cr and Lr are respectively the average
256 clustering coefficient and average shortest path length of an equivalent
257 random graph.
259 A graph is commonly classified as small-world if sigma>1.
261 Parameters
262 ----------
263 G : NetworkX graph
264 An undirected graph.
265 niter : integer (optional, default=100)
266 Approximate number of rewiring per edge to compute the equivalent
267 random graph.
268 nrand : integer (optional, default=10)
269 Number of random graphs generated to compute the average clustering
270 coefficient (Cr) and average shortest path length (Lr).
271 seed : integer, random_state, or None (default)
272 Indicator of random number generation state.
273 See :ref:`Randomness<randomness>`.
275 Returns
276 -------
277 sigma : float
278 The small-world coefficient of G.
280 Notes
281 -----
282 The implementation is adapted from Humphries et al. [1]_ [2]_.
284 References
285 ----------
286 .. [1] The brainstem reticular formation is a small-world, not scale-free,
287 network M. D. Humphries, K. Gurney and T. J. Prescott,
288 Proc. Roy. Soc. B 2006 273, 503-511, doi:10.1098/rspb.2005.3354.
289 .. [2] Humphries and Gurney (2008).
290 "Network 'Small-World-Ness': A Quantitative Method for Determining
291 Canonical Network Equivalence".
292 PLoS One. 3 (4). PMID 18446219. doi:10.1371/journal.pone.0002051.
293 """
294 import numpy as np
296 # Compute the mean clustering coefficient and average shortest path length
297 # for an equivalent random graph
298 randMetrics = {"C": [], "L": []}
299 for i in range(nrand):
300 Gr = random_reference(G, niter=niter, seed=seed)
301 randMetrics["C"].append(nx.transitivity(Gr))
302 randMetrics["L"].append(nx.average_shortest_path_length(Gr))
304 C = nx.transitivity(G)
305 L = nx.average_shortest_path_length(G)
306 Cr = np.mean(randMetrics["C"])
307 Lr = np.mean(randMetrics["L"])
309 sigma = (C / Cr) / (L / Lr)
311 return sigma
314@not_implemented_for("directed")
315@not_implemented_for("multigraph")
316@py_random_state(3)
317@nx._dispatch
318def omega(G, niter=5, nrand=10, seed=None):
319 """Returns the small-world coefficient (omega) of a graph
321 The small-world coefficient of a graph G is:
323 omega = Lr/L - C/Cl
325 where C and L are respectively the average clustering coefficient and
326 average shortest path length of G. Lr is the average shortest path length
327 of an equivalent random graph and Cl is the average clustering coefficient
328 of an equivalent lattice graph.
330 The small-world coefficient (omega) measures how much G is like a lattice
331 or a random graph. Negative values mean G is similar to a lattice whereas
332 positive values mean G is a random graph.
333 Values close to 0 mean that G has small-world characteristics.
335 Parameters
336 ----------
337 G : NetworkX graph
338 An undirected graph.
340 niter: integer (optional, default=5)
341 Approximate number of rewiring per edge to compute the equivalent
342 random graph.
344 nrand: integer (optional, default=10)
345 Number of random graphs generated to compute the maximal clustering
346 coefficient (Cr) and average shortest path length (Lr).
348 seed : integer, random_state, or None (default)
349 Indicator of random number generation state.
350 See :ref:`Randomness<randomness>`.
353 Returns
354 -------
355 omega : float
356 The small-world coefficient (omega)
358 Notes
359 -----
360 The implementation is adapted from the algorithm by Telesford et al. [1]_.
362 References
363 ----------
364 .. [1] Telesford, Joyce, Hayasaka, Burdette, and Laurienti (2011).
365 "The Ubiquity of Small-World Networks".
366 Brain Connectivity. 1 (0038): 367-75. PMC 3604768. PMID 22432451.
367 doi:10.1089/brain.2011.0038.
368 """
369 import numpy as np
371 # Compute the mean clustering coefficient and average shortest path length
372 # for an equivalent random graph
373 randMetrics = {"C": [], "L": []}
375 # Calculate initial average clustering coefficient which potentially will
376 # get replaced by higher clustering coefficients from generated lattice
377 # reference graphs
378 Cl = nx.average_clustering(G)
380 niter_lattice_reference = niter
381 niter_random_reference = niter * 2
383 for _ in range(nrand):
384 # Generate random graph
385 Gr = random_reference(G, niter=niter_random_reference, seed=seed)
386 randMetrics["L"].append(nx.average_shortest_path_length(Gr))
388 # Generate lattice graph
389 Gl = lattice_reference(G, niter=niter_lattice_reference, seed=seed)
391 # Replace old clustering coefficient, if clustering is higher in
392 # generated lattice reference
393 Cl_temp = nx.average_clustering(Gl)
394 if Cl_temp > Cl:
395 Cl = Cl_temp
397 C = nx.average_clustering(G)
398 L = nx.average_shortest_path_length(G)
399 Lr = np.mean(randMetrics["L"])
401 omega = (Lr / L) - (C / Cl)
403 return omega