Paper Info
Title
Algebraic Connectivity Ratio of Ramanujan Graphs
Abstract
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(ngamma) 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.
Year
DOI
Venue
2007
10.1109/ACC.2007.4282254
New York, NY
Keywords
DocType
ISSN
algebra,convergence of numerical methods,graph theory,algebraic connectivity ratio,combinatorial mathematics,consensus algorithms,explicit construction algorithms,fast regular graphs,prime numbers,quasiRamanujan graphs,randomized algorithm,regular Cayley graphs,small-word networks,Cayley graphs,Ramanujan graphs,algebraic connectivity,random graphs,small-world networks,ultrafast consensus
Conference
0743-1619 E-ISBN : 1-4244-0989-6
ISBN
Citations 
PageRank 
1-4244-0989-6
13
1.79
References 
Authors
17
2
Name
Order
Citations
PageRank
Reza Olfati-Saber18066549.43
Olfati-Saber, R.2131.79