Locating multiple sources in social networks under the SIR model: A divide-and-conquer approach

Social networks greatly amplify the spread of information across different communities. However, we recently have observed that various malicious information, such as computer virus and rumors, were broadly spread via social networks. For better controlling the spread of malicious information, it is critical to develop effective methods to locate the diffusion source nodes in social networks. Many pioneer works have explored the source locating problem, but they mostly rely on the assumption that there is only a single source node. In this paper, we present an approximate multi-source locating algorithm by first introducing a new reverse propagation model to detect the recovered and unobserved infected nodes, and then developing a community detection method to cluster the extended infected nodes (including recovered nodes and infected nodes) into multiple infected communities. In doing so, we can identify the source nodes by using the maximum likelihood estimation on each infected community. Numerical simulations on both synthetic and real networks show the performance of the proposed method.