[Back]

H. Mahyar, R. Hasheminezhad, E. Ghalebi, A. Nazemian, R. Grosu, A. Movaghar, H. Rabiee:
"Identifying central nodes for information flow in social networks using compressive sensing";
Social Network Analysis and Mining, 8 (2018), 33.

This paper addresses the problem of identifying central nodes from the information flow standpoint in a social network. Betweenness centrality is the most prominent measure that shows the node importance from the information flow standpoint in the network. High betweenness centrality nodes play crucial roles in the spread of propaganda, ideologies, or gossips in social networks, the bottlenecks in communication networks, and the connector hubs in biological systems. In this paper, we introduce DICeNod, a new approach to efficiently identify central nodes in social networks without direct measurement of each individual node using compressive sensing, which is a well-known paradigm in sparse signal recovery. DICeNod can perform in a distributed manner by utilizing only local information at each node; thus, it is appropriate for large real-world and unknown networks. We theoretically show that by using only 𝑂(𝑘log(𝑛𝑘)) indirect end-to-end measurements in DICeNod, one can recover top-k central nodes in a network with n nodes, even though the measurements have to follow network topological constraints. Furthermore, we show that the computationally efficient ℓ1-minimization can provide recovery guarantees to infer such central nodes from the constructed measurement matrix with this number of measurements. Finally, we evaluate accuracy, speedup, and effectiveness of the proposed method by extensive simulations on several synthetic and real-world networks. The experimental results demonstrate that the number of correctly identified central nodes and their estimated rank based on the DICeNod framework and the global betweenness centrality correlate very well. Moreover, the results show that DICeNod is a scalable framework and it can be efficiently used for identifying central nodes in real-world networks.

http://dx.doi.org/10.1007/s13278-018-0506-1