A novel approach for detecting multiple rumor sources in networks with partial observations

作者：Zhang, Zhao; Xu, Wen; Wu, Weili; Du, Ding-Zhu^*

来源：Journal of Combinatorial Optimization, 2017, 33(1): 132-146.

DOI：10.1007/s10878-015-9939-x

• Social network
• Rumor source detection
• Set resolving set
• Approximation algorithm

Locating source of information diffusion in networks has very important applications such as locating the sources of epidemics, news/rumors in social networks or online computer virus. In this paper, we consider detecting multiple rumor sources from a deterministic point of view by modeling it as the set resolving set (SRS) problem. Let G be a network on n nodes. A node subset K is an SRS of G if all detectable node sets are distinguishable by K. The problem of multiple rumor source detection (MRSD) in the network can be modeled as finding an SRS K with the smallest cardinality. In this paper, we propose a polynomial-time greedy algorithm for finding a minimum SRS in a general network, achieving performance ratio . This is the first work establishing a relation between the MRSD problem and a deterministic concept of SRS, and a first work to give the minimum SRS problem a polynomial-time performance-guaranteed approximation algorithm. Our framework suggests a robust and efficient approach for estimating multiple rumor sources independent of diffusion models in networks.

• 出版日期2017-1
• 单位浙江师范大学