Distributed Algorithms for Computation of Centrality Measures in Complex Networks

Abstract

This paper is concerned with distributed computation of several commonly used centrality measures in complex networks. In particular, we propose deterministic algorithms, which converge in finite time, for the distributed computation of the degree, closeness and betweenness centrality measures in directed graphs. Regarding eigenvector centrality, we consider the PageRank problem as its typical variant, and design distributed randomized algorithms to compute PageRank for both fixed and time-varying graphs. A key feature of the proposed algorithms is that they do not require to know the network size, which can be simultaneously estimated at every node, and that they are clock-free. To address the PageRank problem of time-varying graphs, we introduce the novel concept of persistent graph, which eliminates the effect of spamming nodes. Moreover, we prove that these algorithms converge almost surely and in the sense of $L^p$. Finally, the effectiveness of the proposed algorithms is illustrated via extensive simulations using a classical benchmark.

15 pages, 8 figures,(conditionally accepted), IEEE Transactions on Automatic Control, 2016

References in corpus (1)

• Randomized Extended Kaczmarz for Solving Least-Squares

Cited by in corpus (7)

• A Tutorial on Modeling and Analysis of Dynamic Social Networks. Part I
• A Tutorial on Modeling and Analysis of Dynamic Social Networks. Part II
• On predefined-time consensus protocols for dynamic networks
• Distributed estimation and control of node centrality in undirected asymmetric networks
• Distributed Algorithms for Directed Betweenness Centrality and All Pairs Shortest Paths
• Efficient PageRank Computation via Distributed Algorithms with Web Clustering
• Simple and Fast Distributed Computation of Betweenness Centrality