Decentralized estimation of the algebraic connectivity for strongly connected networks

The second smallest eigenvalue λ₂(L) of the Laplacian L of a network G is a parameter that captures important properties of the network. Applications such as synchronization of networked systems, consensus-based algorithms and network connectivity control may require one to regulate the magnitude of λ₂(L) in order to achieve suitable network performance. The problem of decentralized estimation of λ₂(L) for directed graphs is thus a relevant problem, yet it has received little attention thus far. We present an algorithm for its estimation and demonstrate its performance.