A Compressive Sensing Framework for Distributed Detection of High Closeness Centrality Nodes in Networks

The large scale of toady’s real-world networks makes development of distributed algorithms for network science applications of great importance. These algorithms require a node to only have local interactions with its immediate neighbors. This is due to the fact that the whole network topology is usually unknown to each individual node. Detecting key actors within a network with respect to different notions of influence, has recently received a lot of attention among researchers. Closeness centrality is a prominent measure for evaluating a node’s importance and influence within a given network, based on its accessibility in the network. In this paper, we first introduce an ego-centric metric with very low computational complexity, that correlates well with the global closeness centrality. Then, we propose CS-HiClose, a compressive sensing (CS) framework that can accurately and efficiently recover top-k closeness centrality nodes in the network using the proposed local metric. Computations of our ego-centric metric and the aggregation procedure are both carried out effectively in a distributed manner, using only local interactions between neighboring nodes. The performance of the proposed method is evaluated by extensive simulations under several configurations on various types of synthetic and real-world networks. The experimental results demonstrate that the proposed local metric correlates with the global closeness centrality, better than the existing local metrics. Moreover, the results show that CS-HiClose outperforms the state-of-the-art CS-based methods with notable improvements.