Expected Convergence Rate to Consensus in Asymmetric Networks: Analysis and Distributed Estimation
研究了加权有向图表示的非对称网络中达成共识的预期收敛速度，基于拉普拉斯矩阵特征值提出度量，并开发了集中式和分布式算法来计算该速度。
This paper investigates the expected rate of convergence to consensus in an asymmetric network represented by a weighted directed graph. The initial state of the network is represented by a random vector and the expectation is taken with respect to the random initial condition of the network. The proposed convergence rate is described in terms of the eigenvalues of the Laplacian matrix of the network graph. The generalized power iteration algorithm is then introduced based on the Krylov subspace method to compute the proposed expected convergence rate in a centralized fashion. To this end, the Laplacian matrix of the network is transformed to a new matrix such that existing techniques can be used to find the eigenvalue representing the expected convergence rate of the network. The convergence analysis of the centralized algorithm is performed with a prescribed upper bound on the approximation error of the algorithm. A distributed version of the centralized algorithm is then developed using the notion of consensus observer. The efficiency of the algorithms is subsequently demonstrated by simulations.