Distributed Algorithms for Computation of Centrality Measures in Complex Networks

DOI10.1109/TAC.2016.2604373zbMATH Open1366.90023arXiv1507.01694MaRDI QIDQ5280396FDOQ5280396

Authors: Keyou You, Li Qiu, Roberto Tempo 

Publication date: 27 July 2017

Published in: IEEE Transactions on Automatic Control (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1507.01694

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Deterministic network models in operations research (90B10) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Distributed algorithms (68W15)

Cited In (6)

• Tunable Eigenvector-Based Centralities for Multiplex and Temporal Networks
• Parallelization of game theoretic centrality algorithms
• Eigenvector-Based Centrality Measures for Temporal Networks
• A general higher-order supracentrality framework based on motifs of temporal networks and multiplex networks
• Supracentrality analysis of temporal networks with directed interlayer coupling
• On predefined-time consensus protocols for dynamic networks

This page was built for publication: Distributed Algorithms for Computation of Centrality Measures in Complex Networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5280396)