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"""Provides explicit constructions of expander graphs."""
3import itertools
5import networkx as nx
7__all__ = [
8 "margulis_gabber_galil_graph",
9 "chordal_cycle_graph",
10 "paley_graph",
11 "maybe_regular_expander",
12 "maybe_regular_expander_graph",
13 "is_regular_expander",
14 "random_regular_expander_graph",
15]
18# Other discrete torus expanders can be constructed by using the following edge
19# sets. For more information, see Chapter 4, "Expander Graphs", in
20# "Pseudorandomness", by Salil Vadhan.
21#
22# For a directed expander, add edges from (x, y) to:
23#
24# (x, y),
25# ((x + 1) % n, y),
26# (x, (y + 1) % n),
27# (x, (x + y) % n),
28# (-y % n, x)
29#
30# For an undirected expander, add the reverse edges.
31#
32# Also appearing in the paper of Gabber and Galil:
33#
34# (x, y),
35# (x, (x + y) % n),
36# (x, (x + y + 1) % n),
37# ((x + y) % n, y),
38# ((x + y + 1) % n, y)
39#
40# and:
41#
42# (x, y),
43# ((x + 2*y) % n, y),
44# ((x + (2*y + 1)) % n, y),
45# ((x + (2*y + 2)) % n, y),
46# (x, (y + 2*x) % n),
47# (x, (y + (2*x + 1)) % n),
48# (x, (y + (2*x + 2)) % n),
49#
50@nx._dispatchable(graphs=None, returns_graph=True)
51def margulis_gabber_galil_graph(n, create_using=None):
52 r"""Returns the Margulis-Gabber-Galil undirected MultiGraph on `n^2` nodes.
54 The undirected MultiGraph is regular with degree `8`. Nodes are integer
55 pairs. The second-largest eigenvalue of the adjacency matrix of the graph
56 is at most `5 \sqrt{2}`, regardless of `n`.
58 Parameters
59 ----------
60 n : int
61 Determines the number of nodes in the graph: `n^2`.
62 create_using : NetworkX graph constructor, optional (default MultiGraph)
63 Graph type to create. If graph instance, then cleared before populated.
65 Returns
66 -------
67 G : graph
68 The constructed undirected multigraph.
70 Raises
71 ------
72 NetworkXError
73 If the graph is directed or not a multigraph.
75 """
76 G = nx.empty_graph(0, create_using, default=nx.MultiGraph)
77 if G.is_directed() or not G.is_multigraph():
78 msg = "`create_using` must be an undirected multigraph."
79 raise nx.NetworkXError(msg)
81 for x, y in itertools.product(range(n), repeat=2):
82 for u, v in (
83 ((x + 2 * y) % n, y),
84 ((x + (2 * y + 1)) % n, y),
85 (x, (y + 2 * x) % n),
86 (x, (y + (2 * x + 1)) % n),
87 ):
88 G.add_edge((x, y), (u, v))
89 G.graph["name"] = f"margulis_gabber_galil_graph({n})"
90 return G
93@nx._dispatchable(graphs=None, returns_graph=True)
94def chordal_cycle_graph(p, create_using=None):
95 """Returns the chordal cycle graph on `p` nodes.
97 The returned graph is a cycle graph on `p` nodes with chords joining each
98 vertex `x` to its inverse modulo `p`. This graph is a (mildly explicit)
99 3-regular expander [1]_ when viewed as a simple graph. The default return
100 type is a MultiGraph, which has 6-regular nodes due to the symmetric nature
101 of the edge additions. Use ``nx.Graph(nx.chordal_cycle_graph(p))`` to obtain
102 the 3-regular simple graph.
104 `p` *must* be a prime number.
106 Parameters
107 ----------
108 p : a prime number
110 The number of vertices in the graph. This also indicates where the
111 chordal edges in the cycle will be created.
113 create_using : NetworkX graph constructor, optional (default=nx.Graph)
114 Graph type to create. If graph instance, then cleared before populated.
116 Returns
117 -------
118 G : graph
119 The constructed undirected multigraph.
121 Raises
122 ------
123 NetworkXError
125 If `create_using` indicates directed or not a multigraph.
127 References
128 ----------
130 .. [1] Theorem 4.4.2 in A. Lubotzky. "Discrete groups, expanding graphs and
131 invariant measures", volume 125 of Progress in Mathematics.
132 Birkhäuser Verlag, Basel, 1994.
134 """
135 G = nx.empty_graph(0, create_using, default=nx.MultiGraph)
136 if G.is_directed() or not G.is_multigraph():
137 msg = "`create_using` must be an undirected multigraph."
138 raise nx.NetworkXError(msg)
140 for x in range(p):
141 left = (x - 1) % p
142 right = (x + 1) % p
143 # Here we apply Fermat's Little Theorem to compute the multiplicative
144 # inverse of x in Z/pZ. By Fermat's Little Theorem,
145 #
146 # x^p = x (mod p)
147 #
148 # Therefore,
149 #
150 # x * x^(p - 2) = 1 (mod p)
151 #
152 # The number 0 is a special case: we just let its inverse be itself.
153 chord = pow(x, p - 2, p) if x > 0 else 0
154 for y in (left, right, chord):
155 G.add_edge(x, y)
156 G.graph["name"] = f"chordal_cycle_graph({p})"
157 return G
160@nx._dispatchable(graphs=None, returns_graph=True)
161def paley_graph(p, create_using=None):
162 r"""Returns the Paley $\frac{(p-1)}{2}$ -regular graph on $p$ nodes.
164 The returned graph is a graph on $\mathbb{Z}/p\mathbb{Z}$ with edges between $x$ and $y$
165 if and only if $x-y$ is a nonzero square in $\mathbb{Z}/p\mathbb{Z}$.
167 If $p \equiv 1 \pmod 4$, $-1$ is a square in
168 $\mathbb{Z}/p\mathbb{Z}$ and therefore $x-y$ is a square if and
169 only if $y-x$ is also a square, i.e the edges in the Paley graph are symmetric.
171 If $p \equiv 3 \pmod 4$, $-1$ is not a square in $\mathbb{Z}/p\mathbb{Z}$
172 and therefore either $x-y$ or $y-x$ is a square in $\mathbb{Z}/p\mathbb{Z}$ but not both.
174 Note that a more general definition of Paley graphs extends this construction
175 to graphs over $q=p^n$ vertices, by using the finite field $F_q$ instead of
176 $\mathbb{Z}/p\mathbb{Z}$.
177 This construction requires to compute squares in general finite fields and is
178 not what is implemented here (i.e `paley_graph(25)` does not return the true
179 Paley graph associated with $5^2$).
181 Parameters
182 ----------
183 p : int, an odd prime number.
185 create_using : NetworkX graph constructor, optional (default=nx.Graph)
186 Graph type to create. If graph instance, then cleared before populated.
188 Returns
189 -------
190 G : graph
191 The constructed directed graph.
193 Raises
194 ------
195 NetworkXError
196 If the graph is a multigraph.
198 References
199 ----------
200 Chapter 13 in B. Bollobas, Random Graphs. Second edition.
201 Cambridge Studies in Advanced Mathematics, 73.
202 Cambridge University Press, Cambridge (2001).
203 """
204 G = nx.empty_graph(0, create_using, default=nx.DiGraph)
205 if G.is_multigraph():
206 msg = "`create_using` cannot be a multigraph."
207 raise nx.NetworkXError(msg)
209 # Compute the squares in Z/pZ.
210 # Make it a set to uniquify (there are exactly (p-1)/2 squares in Z/pZ
211 # when is prime).
212 square_set = {(x**2) % p for x in range(1, p) if (x**2) % p != 0}
214 for x in range(p):
215 for x2 in square_set:
216 G.add_edge(x, (x + x2) % p)
217 G.graph["name"] = f"paley({p})"
218 return G
221@nx.utils.decorators.np_random_state("seed")
222@nx._dispatchable(graphs=None, returns_graph=True)
223def maybe_regular_expander_graph(n, d, *, create_using=None, max_tries=100, seed=None):
224 r"""Utility for creating a random regular expander.
226 Returns a random $d$-regular graph on $n$ nodes which is an expander
227 graph with very good probability.
229 Parameters
230 ----------
231 n : int
232 The number of nodes.
233 d : int
234 The degree of each node.
235 create_using : Graph Instance or Constructor
236 Indicator of type of graph to return.
237 If a Graph-type instance, then clear and use it.
238 If a constructor, call it to create an empty graph.
239 Use the Graph constructor by default.
240 max_tries : int. (default: 100)
241 The number of allowed loops when generating each independent cycle
242 seed : (default: None)
243 Seed used to set random number generation state. See :ref`Randomness<randomness>`.
245 Notes
246 -----
247 The nodes are numbered from $0$ to $n - 1$.
249 The graph is generated by taking $d / 2$ random independent cycles.
251 Joel Friedman proved that in this model the resulting
252 graph is an expander with probability
253 $1 - O(n^{-\tau})$ where $\tau = \lceil (\sqrt{d - 1}) / 2 \rceil - 1$. [1]_
255 Examples
256 --------
257 >>> G = nx.maybe_regular_expander_graph(n=200, d=6, seed=8020)
259 Returns
260 -------
261 G : graph
262 The constructed undirected graph.
264 Raises
265 ------
266 NetworkXError
267 If $d % 2 != 0$ as the degree must be even.
268 If $n - 1$ is less than $ 2d $ as the graph is complete at most.
269 If max_tries is reached
271 See Also
272 --------
273 is_regular_expander
274 random_regular_expander_graph
276 References
277 ----------
278 .. [1] Joel Friedman,
279 A Proof of Alon's Second Eigenvalue Conjecture and Related Problems, 2004
280 https://arxiv.org/abs/cs/0405020
282 """
284 import numpy as np
286 if n < 1:
287 raise nx.NetworkXError("n must be a positive integer")
289 if not (d >= 2):
290 raise nx.NetworkXError("d must be greater than or equal to 2")
292 if not (d % 2 == 0):
293 raise nx.NetworkXError("d must be even")
295 if not (n - 1 >= d):
296 raise nx.NetworkXError(
297 f"Need n-1>= d to have room for {d // 2} independent cycles with {n} nodes"
298 )
300 G = nx.empty_graph(n, create_using)
302 if n < 2:
303 return G
305 cycles = []
306 edges = set()
308 # Create d / 2 cycles
309 for i in range(d // 2):
310 iterations = max_tries
311 # Make sure the cycles are independent to have a regular graph
312 while len(edges) != (i + 1) * n:
313 iterations -= 1
314 # Faster than random.permutation(n) since there are only
315 # (n-1)! distinct cycles against n! permutations of size n
316 cycle = seed.permutation(n - 1).tolist()
317 cycle.append(n - 1)
319 new_edges = {
320 (u, v)
321 for u, v in nx.utils.pairwise(cycle, cyclic=True)
322 if (u, v) not in edges and (v, u) not in edges
323 }
324 # If the new cycle has no edges in common with previous cycles
325 # then add it to the list otherwise try again
326 if len(new_edges) == n:
327 cycles.append(cycle)
328 edges.update(new_edges)
330 if iterations == 0:
331 msg = "Too many iterations in maybe_regular_expander_graph"
332 raise nx.NetworkXError(msg)
334 G.add_edges_from(edges)
336 return G
339def maybe_regular_expander(n, d, *, create_using=None, max_tries=100, seed=None):
340 """
341 .. deprecated:: 3.6
342 `maybe_regular_expander` is a deprecated alias
343 for `maybe_regular_expander_graph`.
344 Use `maybe_regular_expander_graph` instead.
345 """
346 import warnings
348 warnings.warn(
349 "maybe_regular_expander is deprecated, "
350 "use `maybe_regular_expander_graph` instead.",
351 category=DeprecationWarning,
352 stacklevel=2,
353 )
354 return maybe_regular_expander_graph(
355 n, d, create_using=create_using, max_tries=max_tries, seed=seed
356 )
359@nx.utils.not_implemented_for("directed")
360@nx.utils.not_implemented_for("multigraph")
361@nx._dispatchable(preserve_edge_attrs={"G": {"weight": 1}})
362def is_regular_expander(G, *, epsilon=0):
363 r"""Determines whether the graph G is a regular expander. [1]_
365 An expander graph is a sparse graph with strong connectivity properties.
367 More precisely, this helper checks whether the graph is a
368 regular $(n, d, \lambda)$-expander with $\lambda$ close to
369 the Alon-Boppana bound and given by
370 $\lambda = 2 \sqrt{d - 1} + \epsilon$. [2]_
372 In the case where $\epsilon = 0$ then if the graph successfully passes the test
373 it is a Ramanujan graph. [3]_
375 A Ramanujan graph has spectral gap almost as large as possible, which makes them
376 excellent expanders.
378 Parameters
379 ----------
380 G : NetworkX graph
381 epsilon : int, float, default=0
383 Returns
384 -------
385 bool
386 Whether the given graph is a regular $(n, d, \lambda)$-expander
387 where $\lambda = 2 \sqrt{d - 1} + \epsilon$.
389 Examples
390 --------
391 >>> G = nx.random_regular_expander_graph(20, 4)
392 >>> nx.is_regular_expander(G)
393 True
395 See Also
396 --------
397 maybe_regular_expander_graph
398 random_regular_expander_graph
400 References
401 ----------
402 .. [1] Expander graph, https://en.wikipedia.org/wiki/Expander_graph
403 .. [2] Alon-Boppana bound, https://en.wikipedia.org/wiki/Alon%E2%80%93Boppana_bound
404 .. [3] Ramanujan graphs, https://en.wikipedia.org/wiki/Ramanujan_graph
406 """
408 import numpy as np
409 import scipy as sp
411 if epsilon < 0:
412 raise nx.NetworkXError("epsilon must be non negative")
414 if not nx.is_regular(G):
415 return False
417 _, d = nx.utils.arbitrary_element(G.degree)
419 A = nx.adjacency_matrix(G, dtype=float)
420 lams = sp.sparse.linalg.eigsh(A, which="LM", k=2, return_eigenvectors=False)
422 # lambda2 is the second biggest eigenvalue
423 lambda2 = min(lams)
425 # Use bool() to convert numpy scalar to Python Boolean
426 return bool(abs(lambda2) < 2 * np.sqrt(d - 1) + epsilon)
429@nx.utils.decorators.np_random_state("seed")
430@nx._dispatchable(graphs=None, returns_graph=True)
431def random_regular_expander_graph(
432 n, d, *, epsilon=0, create_using=None, max_tries=100, seed=None
433):
434 r"""Returns a random regular expander graph on $n$ nodes with degree $d$.
436 An expander graph is a sparse graph with strong connectivity properties. [1]_
438 More precisely the returned graph is a $(n, d, \lambda)$-expander with
439 $\lambda = 2 \sqrt{d - 1} + \epsilon$, close to the Alon-Boppana bound. [2]_
441 In the case where $\epsilon = 0$ it returns a Ramanujan graph.
442 A Ramanujan graph has spectral gap almost as large as possible,
443 which makes them excellent expanders. [3]_
445 Parameters
446 ----------
447 n : int
448 The number of nodes.
449 d : int
450 The degree of each node.
451 epsilon : int, float, default=0
452 max_tries : int, (default: 100)
453 The number of allowed loops,
454 also used in the `maybe_regular_expander_graph` utility
455 seed : (default: None)
456 Seed used to set random number generation state. See :ref`Randomness<randomness>`.
458 Raises
459 ------
460 NetworkXError
461 If max_tries is reached
463 Examples
464 --------
465 >>> G = nx.random_regular_expander_graph(20, 4)
466 >>> nx.is_regular_expander(G)
467 True
469 Notes
470 -----
471 This loops over `maybe_regular_expander_graph` and can be slow when
472 $n$ is too big or $\epsilon$ too small.
474 See Also
475 --------
476 maybe_regular_expander_graph
477 is_regular_expander
479 References
480 ----------
481 .. [1] Expander graph, https://en.wikipedia.org/wiki/Expander_graph
482 .. [2] Alon-Boppana bound, https://en.wikipedia.org/wiki/Alon%E2%80%93Boppana_bound
483 .. [3] Ramanujan graphs, https://en.wikipedia.org/wiki/Ramanujan_graph
485 """
486 G = maybe_regular_expander_graph(
487 n, d, create_using=create_using, max_tries=max_tries, seed=seed
488 )
489 iterations = max_tries
491 while not is_regular_expander(G, epsilon=epsilon):
492 iterations -= 1
493 G = maybe_regular_expander_graph(
494 n=n, d=d, create_using=create_using, max_tries=max_tries, seed=seed
495 )
497 if iterations == 0:
498 raise nx.NetworkXError(
499 "Too many iterations in random_regular_expander_graph"
500 )
502 return G