Revert Propagation: Who are responsible for a contagion initialization in a Diffusion Network?

摘要

Millions of stories are transferred in a social network and some of them are malicious. Can we identify the source node(s) that are responsible to initiate the propagation originally? If so, when did they initiated the propagation? The problem of identifying the source of propagation based on limited observations has been studied significantly in recent years, as it can help to reduce the damage caused by unwanted infections with early detection. In this paper, we present an efficient algorithm for finding a node initiating a piece of information into the network and also inferring the time when it is initiated. We propose Source Location Estimation method, SoLE, that estimate the source probability for each node and then choose the source set which are maximize the probability using a well-known greedy method with a theoretical guarantees. The Observed nodes are detected nodes which are known clearly that spread specified malicious information in the network but small fraction of nodes are detected. The Hidden infected nodes are hidden, which spread the information in the network, however, they're not identified yet. In this problem, we first estimate the shortest path between other nodes to observed ones for each propagation trace, SoLE. Afterward, we find the best nodes as the source set among the hidden nodes by optimizing a loss function. Our experiments on real-world propagation through networks show the superiority of our approach in detecting true sources and promote the top ten accuracy from less than 10% for the state-of-the-art methods to approximately 30%.