Distributed computation of the Fiedler vector with application to topology inference in ad hoc networks

The Fiedler vector of a graph is the eigenvector corresponding to the smallest non-trivial eigenvalue of the graph's Laplacian matrix. The entries of the Fiedler vector are known to provide a powerful heuristic for topology inference, e.g., to identify densely connected node clusters, to search for bottleneck links in the information dissemination, or to increase the overall connectivity of the network. In this paper, we consider ad hoc networks where the nodes can process and exchange data in a synchronous fashion, and we propose a distributed algorithm for in-network estimation of the Fiedler vector and the algebraic connectivity of the corresponding network graph. The algorithm is fully scalable with respect to the network size in terms of per-node computational complexity and data transmission. Simulation results demonstrate the performance of the algorithm. (C) 2012 Elsevier B.V. All rights reserved.