Fast distributed algebraic connectivity estimation in large scale networks |
| |
| Authors: | Eduardo Montijano Juan I Montijano Carlos Sagues |
| |
| Institution: | 1. Instituto de Investigación en Ingeniería de Aragón (I3A), Universidad de Zaragoza, Spain;2. Instituto Universitario de Matemáticas y Aplicaciones (IUMA), Universidad de Zaragoza, Spain |
| |
| Abstract: | This paper presents a distributed method to estimate the algebraic connectivity of fixed undirected communication graphs. The proposed algorithm uses bisection to estimate the second smallest eigenvalue of the Laplacian matrix associated to the graph. In order to decide the sub-interval in which the eigenvalue is contained, a distributed averaging algorithm based on Chebyshev polynomials is considered together with a max consensus algorithm. The information exchanged by neighbors in the graph each communication round is constant and independent of the size of the network, making it scalable to large networks. Besides, exploiting the convergence properties of Chebyshev polynomials we provide a direct estimation of the algebraic connectivity so that, instead of the midpoint of the bisection interval, the new approximation can be used. Finally, our algorithm also provides upper and lower bounds on the algebraic connectivity and an estimation of the Fiedler eigenvector associated to it. Simulations in large networks demonstrate the scalability and accuracy of the algorithm. |
| |
| Keywords: | Corresponding author |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
