Simple Expander graph constructions

An expander graph is a sparse graph with high connectivity properties. I will show code for simple constructions of some families of Expander Graphs using Python networkx library:


1) LPS graph

From Michael Nielsen's blog
In this example the family of graphs is indexed by a prime number, . The set of vertices for the graph  is just the set of points in , the field of integers modulo . We construct a -regular graph by connecting each vertex  to  and . The vertex  is connected to  and . According to the lecture notes by Linial and Wigderson, this was proved to be a family of expanders by Lubotsky, Phillips and Sarnak in 1988.

Python code

import networkx as nx
import matplotlib
import matplotlib.pyplot as plt
import pylab as PL
import random, sys

def miller_rabin_pass(a, s, d, n):
    a_to_power = pow(a, d, n)
    if a_to_power == 1:
        return True
    for i in xrange(s-1):
        if a_to_power == n - 1:
            return True
        a_to_power = (a_to_power * a_to_power) % n
    return a_to_power == n - 1


def miller_rabin(n):
    d = n - 1
    s = 0
    while d % 2 == 0:
        d >>= 1
        s += 1
    for repeat in xrange(20):
        a = 0
        while a == 0:
            a = random.randrange(n)
        if not miller_rabin_pass(a, s, d, n):
            return False
    return True

def ramanujan_graph(p):
    if not miller_rabin(p):
        print "p is not prime"
        return None
    g = nx.Graph()
 
    for i in range(p):
        g.add_node(i)
    for i in range(p):
        if i == 0:
           g.add_edge(0,p-1)
           g.add_edge(0,1)
        else:
           g.add_edge(i,i-1)
           g.add_edge(i,(i+1)%p)
           g.add_edge(i,(i**(p-2))%p)          

              g=nx.Graph(g) #remove parallel edges
              g.remove_edges_from(g.selfloop_edges()) #remove self loops
              return g      

g = ramanujan_graph(41)
PL.figure()
nx.draw_circular(g)
plt.show()

2) Paley graph

Paley graph of order q (where q is a prime or integer power of a prime) has q nodes, each with degree (q-1)/2. Paley graph is undirected when q % 4 = 1. The set of vertices for the graph  is just the set of points in . Two vertices a,b in graph  are connected if a-b = x² % p where x lies in [1,p). See also: http://mathworld.wolfram.com/PaleyGraph.html

Python code

import networkx as nx
import matplotlib
import matplotlib.pyplot as plt
import pylab as PL
import random, sys

def paley_graph(p):
    if not p%4 == 1:
        return None
    square_list = []
    for i in range((p-1)/2):
        square_list.append((i**2)%p)
     
    g = nx.Graph()
 
    for i in range(p):
        g.add_node(i)
    for i in range(p):
        for j in square_list:
           g.add_edge(i,(i+j)%p)
    g=nx.Graph(g) #remove parallel edges
    g.remove_edges_from(g.selfloop_edges()) #remove self loops
    return g      

g = paley_graph(17)
print nx.diameter(g)
PL.figure()
nx.draw_circular(g)
plt.show()

3) Margulis construction

import networkx as nx
import matplotlib
import matplotlib.pyplot as plt
import pylab as PL
import random, sys

def margulis_graph(n):
    #Graph has n^2 vertices
    g = nx.Graph()
 
    for i in range(n):
        for j in range(n):
            g.add_node((i,j))

    for (i,j) in g.nodes():
        g.add_edge((i,j),((i+2*j)%n,j))
        g.add_edge((i,j),(i,(2*i+j)%n))
        g.add_edge((i,j),(i,(2*i+j+1)%n))
        g.add_edge((i,j),((i+2*j+1)%n,j))
    g=nx.Graph(g) #remove parallel edges
    g.remove_edges_from(g.selfloop_edges()) #remove self loops
    return g      

g = margulis_graph(5)
print nx.diameter(g)
PL.figure()
nx.draw_circular(g)
plt.show()

4) Hypercube graph

Wikipedia. Use nx.hypercube_graph(n)

5) Superconcentrators

Smaller Explicit Superconcentrators

Acknowledgments
I would like to thank Abhishek Bhowmick and Ankit Garg for helpful discussions.