复杂网络中计算中心性测度的分布式算法.pdf

This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TAC.2016.2604373, IEEE Transactions on Automatic Control 1 Distributed Algorithms for Computation of Centrality Measures in Complex Networks Keyou You, Member, IEEE , Roberto Tempo, Fellow, IEEE, and Li Qiu, Fellow, IEEE Abstract—This paper is concerned with distributed computa- it is of great importance to design distributed algorithms with tion of several commonly used centrality measures in complex good scalability properties for their computation, where each networks. In particular, we propose deterministic algorithms, node evaluates centralities by only using local interactions. which converge in finite time, for the distributed computation of the degree, closeness and betweenness centrality measures in Although distributed algorithms may play a significant role directed graphs. Regarding eigenvector centrality, we consider in alleviating the computational burden, the access to limited the PageRank problem as its typical variant, and design dis- information renders it challenging to ensure that each node tributed randomized algorithms to compute PageRank for both provides its exact centrality. This requires a rigorous and fixed and time-varying graphs. A key feature of the proposed challenging anal