Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
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"""
18import networkx as nx
19from networkx.utils import not_implemented_for, py_random_state
21__all__ = ["random_reference", "lattice_reference", "sigma", "omega"]
24@not_implemented_for("directed")
25@not_implemented_for("multigraph")
26@py_random_state(3)
27@nx._dispatchable(returns_graph=True)
28def random_reference(G, niter=1, connectivity=True, seed=None):
29 """Compute a random graph by swapping edges of a given graph.
31 Parameters
32 ----------
33 G : graph
34 An undirected graph with 4 or more nodes.
36 niter : integer (optional, default=1)
37 An edge is rewired approximately `niter` times.
39 connectivity : boolean (optional, default=True)
40 When True, ensure connectivity for the randomized graph.
42 seed : integer, random_state, or None (default)
43 Indicator of random number generation state.
44 See :ref:`Randomness<randomness>`.
46 Returns
47 -------
48 G : graph
49 The randomized graph.
51 Raises
52 ------
53 NetworkXError
54 If there are fewer than 4 nodes or 2 edges in `G`
56 Notes
57 -----
58 The implementation is adapted from the algorithm by Maslov and Sneppen
59 (2002) [1]_.
61 References
62 ----------
63 .. [1] Maslov, Sergei, and Kim Sneppen.
64 "Specificity and stability in topology of protein networks."
65 Science 296.5569 (2002): 910-913.
66 """
67 if len(G) < 4:
68 raise nx.NetworkXError("Graph has fewer than four nodes.")
69 if len(G.edges) < 2:
70 raise nx.NetworkXError("Graph has fewer that 2 edges")
72 from networkx.utils import cumulative_distribution, discrete_sequence
74 local_conn = nx.connectivity.local_edge_connectivity
76 G = G.copy()
77 keys, degrees = zip(*G.degree()) # keys, degree
78 cdf = cumulative_distribution(degrees) # cdf of degree
79 nnodes = len(G)
80 nedges = nx.number_of_edges(G)
81 niter = niter * nedges
82 ntries = int(nnodes * nedges / (nnodes * (nnodes - 1) / 2))
83 swapcount = 0
85 for i in range(niter):
86 n = 0
87 while n < ntries:
88 # pick two random edges without creating edge list
89 # choose source node indices from discrete distribution
90 (ai, ci) = discrete_sequence(2, cdistribution=cdf, seed=seed)
91 if ai == ci:
92 continue # same source, skip
93 a = keys[ai] # convert index to label
94 c = keys[ci]
95 # choose target uniformly from neighbors
96 b = seed.choice(list(G.neighbors(a)))
97 d = seed.choice(list(G.neighbors(c)))
98 if b in [a, c, d] or d in [a, b, c]:
99 continue # all vertices should be different
101 # don't create parallel edges
102 if (d not in G[a]) and (b not in G[c]):
103 G.add_edge(a, d)
104 G.add_edge(c, b)
105 G.remove_edge(a, b)
106 G.remove_edge(c, d)
108 # Check if the graph is still connected
109 if connectivity and local_conn(G, a, b) == 0:
110 # Not connected, revert the swap
111 G.remove_edge(a, d)
112 G.remove_edge(c, b)
113 G.add_edge(a, b)
114 G.add_edge(c, d)
115 else:
116 swapcount += 1
117 break
118 n += 1
119 return G
122@not_implemented_for("directed")
123@not_implemented_for("multigraph")
124@py_random_state(4)
125@nx._dispatchable(returns_graph=True)
126def lattice_reference(G, niter=5, D=None, connectivity=True, seed=None):
127 """Latticize the given graph by swapping edges.
129 Parameters
130 ----------
131 G : graph
132 An undirected graph.
134 niter : integer (optional, default=1)
135 An edge is rewired approximately niter times.
137 D : numpy.array (optional, default=None)
138 Distance to the diagonal matrix.
140 connectivity : boolean (optional, default=True)
141 Ensure connectivity for the latticized graph when set to True.
143 seed : integer, random_state, or None (default)
144 Indicator of random number generation state.
145 See :ref:`Randomness<randomness>`.
147 Returns
148 -------
149 G : graph
150 The latticized graph.
152 Raises
153 ------
154 NetworkXError
155 If there are fewer than 4 nodes or 2 edges in `G`
157 Notes
158 -----
159 The implementation is adapted from the algorithm by Sporns et al. [1]_.
160 which is inspired from the original work by Maslov and Sneppen(2002) [2]_.
162 References
163 ----------
164 .. [1] Sporns, Olaf, and Jonathan D. Zwi.
165 "The small world of the cerebral cortex."
166 Neuroinformatics 2.2 (2004): 145-162.
167 .. [2] Maslov, Sergei, and Kim Sneppen.
168 "Specificity and stability in topology of protein networks."
169 Science 296.5569 (2002): 910-913.
170 """
171 import numpy as np
173 from networkx.utils import cumulative_distribution, discrete_sequence
175 local_conn = nx.connectivity.local_edge_connectivity
177 if len(G) < 4:
178 raise nx.NetworkXError("Graph has fewer than four nodes.")
179 if len(G.edges) < 2:
180 raise nx.NetworkXError("Graph has fewer that 2 edges")
181 # Instead of choosing uniformly at random from a generated edge list,
182 # this algorithm chooses nonuniformly from the set of nodes with
183 # probability weighted by degree.
184 G = G.copy()
185 keys, degrees = zip(*G.degree()) # keys, degree
186 cdf = cumulative_distribution(degrees) # cdf of degree
188 nnodes = len(G)
189 nedges = nx.number_of_edges(G)
190 if D is None:
191 D = np.zeros((nnodes, nnodes))
192 un = np.arange(1, nnodes)
193 um = np.arange(nnodes - 1, 0, -1)
194 u = np.append((0,), np.where(un < um, un, um))
196 for v in range(int(np.ceil(nnodes / 2))):
197 D[nnodes - v - 1, :] = np.append(u[v + 1 :], u[: v + 1])
198 D[v, :] = D[nnodes - v - 1, :][::-1]
200 niter = niter * nedges
201 # maximal number of rewiring attempts per 'niter'
202 max_attempts = int(nnodes * nedges / (nnodes * (nnodes - 1) / 2))
204 for _ in range(niter):
205 n = 0
206 while n < max_attempts:
207 # pick two random edges without creating edge list
208 # choose source node indices from discrete distribution
209 (ai, ci) = discrete_sequence(2, cdistribution=cdf, seed=seed)
210 if ai == ci:
211 continue # same source, skip
212 a = keys[ai] # convert index to label
213 c = keys[ci]
214 # choose target uniformly from neighbors
215 b = seed.choice(list(G.neighbors(a)))
216 d = seed.choice(list(G.neighbors(c)))
217 bi = keys.index(b)
218 di = keys.index(d)
220 if b in [a, c, d] or d in [a, b, c]:
221 continue # all vertices should be different
223 # don't create parallel edges
224 if (d not in G[a]) and (b not in G[c]):
225 if D[ai, bi] + D[ci, di] >= D[ai, ci] + D[bi, di]:
226 # only swap if we get closer to the diagonal
227 G.add_edge(a, d)
228 G.add_edge(c, b)
229 G.remove_edge(a, b)
230 G.remove_edge(c, d)
232 # Check if the graph is still connected
233 if connectivity and local_conn(G, a, b) == 0:
234 # Not connected, revert the swap
235 G.remove_edge(a, d)
236 G.remove_edge(c, b)
237 G.add_edge(a, b)
238 G.add_edge(c, d)
239 else:
240 break
241 n += 1
243 return G
246@not_implemented_for("directed")
247@not_implemented_for("multigraph")
248@py_random_state(3)
249@nx._dispatchable
250def sigma(G, niter=100, nrand=10, seed=None):
251 """Returns the small-world coefficient (sigma) of the given graph.
253 The small-world coefficient is defined as:
254 sigma = C/Cr / L/Lr
255 where C and L are respectively the average clustering coefficient and
256 average shortest path length of G. Cr and Lr are respectively the average
257 clustering coefficient and average shortest path length of an equivalent
258 random graph.
260 A graph is commonly classified as small-world if sigma>1.
262 Parameters
263 ----------
264 G : NetworkX graph
265 An undirected graph.
266 niter : integer (optional, default=100)
267 Approximate number of rewiring per edge to compute the equivalent
268 random graph.
269 nrand : integer (optional, default=10)
270 Number of random graphs generated to compute the average clustering
271 coefficient (Cr) and average shortest path length (Lr).
272 seed : integer, random_state, or None (default)
273 Indicator of random number generation state.
274 See :ref:`Randomness<randomness>`.
276 Returns
277 -------
278 sigma : float
279 The small-world coefficient of G.
281 Notes
282 -----
283 The implementation is adapted from Humphries et al. [1]_ [2]_.
285 References
286 ----------
287 .. [1] The brainstem reticular formation is a small-world, not scale-free,
288 network M. D. Humphries, K. Gurney and T. J. Prescott,
289 Proc. Roy. Soc. B 2006 273, 503-511, doi:10.1098/rspb.2005.3354.
290 .. [2] Humphries and Gurney (2008).
291 "Network 'Small-World-Ness': A Quantitative Method for Determining
292 Canonical Network Equivalence".
293 PLoS One. 3 (4). PMID 18446219. doi:10.1371/journal.pone.0002051.
294 """
295 import numpy as np
297 # Compute the mean clustering coefficient and average shortest path length
298 # for an equivalent random graph
299 randMetrics = {"C": [], "L": []}
300 for i in range(nrand):
301 Gr = random_reference(G, niter=niter, seed=seed)
302 randMetrics["C"].append(nx.transitivity(Gr))
303 randMetrics["L"].append(nx.average_shortest_path_length(Gr))
305 C = nx.transitivity(G)
306 L = nx.average_shortest_path_length(G)
307 Cr = np.mean(randMetrics["C"])
308 Lr = np.mean(randMetrics["L"])
310 sigma = (C / Cr) / (L / Lr)
312 return float(sigma)
315@not_implemented_for("directed")
316@not_implemented_for("multigraph")
317@py_random_state(3)
318@nx._dispatchable
319def omega(G, niter=5, nrand=10, seed=None):
320 """Returns the small-world coefficient (omega) of a graph
322 The small-world coefficient of a graph G is:
324 omega = Lr/L - C/Cl
326 where C and L are respectively the average clustering coefficient and
327 average shortest path length of G. Lr is the average shortest path length
328 of an equivalent random graph and Cl is the average clustering coefficient
329 of an equivalent lattice graph.
331 The small-world coefficient (omega) measures how much G is like a lattice
332 or a random graph. Negative values mean G is similar to a lattice whereas
333 positive values mean G is a random graph.
334 Values close to 0 mean that G has small-world characteristics.
336 Parameters
337 ----------
338 G : NetworkX graph
339 An undirected graph.
341 niter: integer (optional, default=5)
342 Approximate number of rewiring per edge to compute the equivalent
343 random graph.
345 nrand: integer (optional, default=10)
346 Number of random graphs generated to compute the maximal clustering
347 coefficient (Cr) and average shortest path length (Lr).
349 seed : integer, random_state, or None (default)
350 Indicator of random number generation state.
351 See :ref:`Randomness<randomness>`.
354 Returns
355 -------
356 omega : float
357 The small-world coefficient (omega)
359 Notes
360 -----
361 The implementation is adapted from the algorithm by Telesford et al. [1]_.
363 References
364 ----------
365 .. [1] Telesford, Joyce, Hayasaka, Burdette, and Laurienti (2011).
366 "The Ubiquity of Small-World Networks".
367 Brain Connectivity. 1 (0038): 367-75. PMC 3604768. PMID 22432451.
368 doi:10.1089/brain.2011.0038.
369 """
370 import numpy as np
372 # Compute the mean clustering coefficient and average shortest path length
373 # for an equivalent random graph
374 randMetrics = {"C": [], "L": []}
376 # Calculate initial average clustering coefficient which potentially will
377 # get replaced by higher clustering coefficients from generated lattice
378 # reference graphs
379 Cl = nx.average_clustering(G)
381 niter_lattice_reference = niter
382 niter_random_reference = niter * 2
384 for _ in range(nrand):
385 # Generate random graph
386 Gr = random_reference(G, niter=niter_random_reference, seed=seed)
387 randMetrics["L"].append(nx.average_shortest_path_length(Gr))
389 # Generate lattice graph
390 Gl = lattice_reference(G, niter=niter_lattice_reference, seed=seed)
392 # Replace old clustering coefficient, if clustering is higher in
393 # generated lattice reference
394 Cl_temp = nx.average_clustering(Gl)
395 if Cl_temp > Cl:
396 Cl = Cl_temp
398 C = nx.average_clustering(G)
399 L = nx.average_shortest_path_length(G)
400 Lr = np.mean(randMetrics["L"])
402 omega = (Lr / L) - (C / Cl)
404 return float(omega)