Generalized algebraic connectivity for asymmetric networks
Mohammad Mehdi Asadi, Mohammad Ali Khosravi, Amir G. Aghdam, Stéphane Blouin · 2016
The problem of connectivity assessment of an asymmetric network represented by a weighted directed graph is investigated in this paper. The notion of generalized algebraic connectivity is introduced for this type of network as an extension of conventional algebraic connectivity measure for symmetric networks. This new notion represents the expected asymptotic convergence rate of a cooperative algorithm used to control the network. The proposed connectivity measure is then described in terms of the eigenvalues of the Laplacian matrix of the graph representing the network. The effectiveness of this measure in describing the connectivity of asymmetric networks is demonstrated by some intuitive and counter-intuitive examples. A variation of the power iteration algorithm is then developed to compute the proposed connectivity measure. To this end, the Laplacian matrix of the network is properly transformed to a new matrix such that existing techniques can be used to find the eigenvalue representing network connectivity. The effectiveness of the proposed notion in describing network connectivity and also the efficiency of the developed algorithm are subsequently verified by simulations.