دانلود رایگان مقاله انگلیسی برآوردگر بیشینه‌گر احتمال پسین برای شناسایی منبع اطلاعات - IEEE 2018

Abstract

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.

CONCLUSION

In this paper, we revisited the problem of single information source detection in weighted graphs from the perspective of likelihood approximation. After deriving the MAP estimator, we design two approximation approaches to improve the efficiency, namely BFSA and GSBA. Experiments on several networks clearly show the superiority of our methods especially when measured by normalized ranking, and the feasibility of likelihood approximation. Additionally, GSBA is nearly as effective as BFSA, but far more efficient. Three directions are worth exploring as further study. First, so far we have derived our methods to detect the single information source under the SI model. It is interesting to extend them for multiple information sources detection under other models, such as SIR. The second direction is to explore other more effective approaches to find the upper bound of likelihood, instead of greedy search. We can exploit the Cramer–Rao bound to evaluate their estimation qualities. Third, there may be other methods to approximate the likelihood such as Markov chain Monte Carlo sampling, instead of the upper bound to derive GSBA in Section V-B.