Algebraic Connectivity Ratio of Ramanujan Graphs

In this paper, we explore spectral properties of a class of regular Cayley graphs known as Ramanujan graphs and prove that the ratio of their algebraic connectivity to that of regular lattices grows exponentially as O(n^gamma) with ^gamma = 1.84plusmn0.05 for networks with average degree of O(log(n)). Explicit construction algorithms exist for Ramanujan graphs that create regular graphs with especial degree and scale that depend on a pair of prime numbers. We introduce a randomized algorithm for construction of a class of fast regular graphs called quasi Ramanujan graphs. These graphs are obtained from finite number of degree balancing operations on Watts-Strogatz small-word networks that are irregular graphs. We show that quasi Ramanujan graphs share similar combinatorial optimality spectral properties as Ramanujan graphs and are not restricted to especial choices of degree and scale. A byproduct of this fact is that the algebraic connectivity ratio of quasi Ramanujan graphs grows exponentially in n as well. Numerical experiments are performed to verify our analytical predictions. Consensus algorithms converge extremely fast on networks with exponentially growing algebraic connectivity ratios.