Publication Type

Journal Article

Version

acceptedVersion

Publication Date

6-2020

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.

Keywords

Greedy search, Information source detection, Likelihood approximation, Maximum a posteriori (MAP)

Discipline

Databases and Information Systems

Research Areas

Data Science and Engineering

Publication

IEEE Transactions on Systems, Man and Cybernetics: Systems

Volume

50

Issue

6

First Page

2242

Last Page

2256

ISSN

1083-4427

Publisher

Institute of Electrical and Electronics Engineers (IEEE)

Embargo Period

3-28-2021

Additional URL

https://doi.org/10.1109/TSMC.2018.2811410

Download

Share

COinS