Information source detection is to identify nodes initiating the diffusion process in a network, which has a wide range of applications including epidemic outbreak prevention, Internet virus source identification, and rumor source tracing in social networks. Although it has attracted ever-increasing attention from research community in recent years, existing solutions still suffer from high time complexity and inadequate effectiveness, due to high dynamics of information diffusion and observing just a snapshot of the whole process. To this end, we present a comprehensive study for single information source detection in weighted graphs. Specifically, we first propose a maximum a posteriori (MAP) estimator to detect the information source with other methods as the prior, which ensures our method can be integrated with others naturally. Different from many related works, we exploit both infected nodes and their uninfected neighbors to calculate the effective propagation probability, and then derive the exact formation of likelihood for general weighted graphs. To further improve the efficiency, we design two approximate MAP estimators, namely brute force search approximation (BFSA) and greedy search bound approximation (GSBA), from the perspective of likelihood approximation. BFSA tries to traverse the permitted permutations to directly compute the likelihood, but GSBA exploits a strategy of greedy search to find a surrogate upper bound of the likelihood, and thus avoids the enumeration of permitted permutations. Therefore, detecting with partial nodes and likelihood approximation reduces the computational complexity drastically for large graphs. Extensive experiments on several data sets also clearly demonstrate the effectiveness of our methods on detecting the single information source with different settings in weighted graphs.

INTRODUCTION

THE BOOM of research on social network analysis [1]–[۵] has brought ever-increasing attention to the topics of information source detection [6]–[۸], influence maximization [9]–[۱۲], and so on [13]–[۱۶] in recent years. Information source detection aims to identify the nodes initiating the diffusion process based on a single snapshot of the infected network (e.g., diffusion of opinion, rumor, and epidemic). Its wide range of applications include epidemic outbreak prevention, Internet virus source identification, and rumor source tracing in social networks [7], [17]–[۲۰]. The research challenges of this problem come from a number of aspects. First, information diffusion is characteristic of high dynamics and displays a great variety of patterns when initiating from different sources [21]. For example, in social networks, a photograph will be shared more times if it is posted by a celebrity. Second, the actual information diffusion laws are unknown. Although many models have been proposed such as the susceptible-infected-recovered (SIR) model [22] and independent cascade (IC) model [23], they cannot describe information diffusion comprehensively. Third, we only observe a snapshot of the infected network, which is just a part of the whole diffusion process. Nevertheless, various methods have been introduced along the years to overcome these challenges and detect the source of a diffusion for different situations, including methods based on centrality [8], [24], spectral [17], [19], belief propagation (BP) [25]–[۲۷], and so on. However, existing methods are still deemed inadequate due to their high computational complexity and yet-to-be-improved effectiveness. For example, rumor center (RC) [8] only considers the utility of infected nodes to detect the source in homogeneous graphs, and Jordan center (JC) [6] just aims to minimize the maximum distance from the source to others and neglects the dynamicity of information diffusion. Dynamic message passing (DMP) [27], one of the state-of-the-arts, exploits all nodes in the network to estimate the marginal probability of a given node to be in a given state and how long the information has already propagated, which is too time-consuming.