Research On Selection And Detection Of Information Sources For Networked Diffusion

Spreading of epidemics, messages and innovations via networks, especially mobile social networks (MSNets), is ubiquitous in the modern world. Generally, any of these situations can be modeled as an epidemic-like information spreading in a network. In recent tens of years, the issues on epidemic-like information spreading through networks have been attracting researchers’extensive attentions; and in the future, they will still be a long-term focus of interdisciplinary network sciences. From the angle of information spreading source, we study some key problems on the selection and detection of information sources, with the aim to boost the spreading of useful information or restrain the spreading of malicious information.For the issue of information source selection, our main contributions are as follows:1) First, we study the non-adaptive information source selection problem under the gossip spreading model. For the push-based (PUSH) and pull-based (PULL) models, we construct an equivalent view and a temporal mapping of the information spreading process over a network, respectively, and further prove that this source selection problem has the property of submodularity. Leveraging the submodularity, we propose a natural sub-optimal greedy algorithm for the gossip spreading maximization problem, that promises a performance guarantee factor of (1-1/e) for both the PUSH and PULL models. From the experiments, it is demonstrated that a small number of information sources with a moderate delay-tolerant deadline can cause a wide diffusion of information over the network, and the greedy algorithm significantly outperforms the commonly-used heuristic and random algorithms.2) Second, we study the adaptive information source selection problem under the influence spreading model. For a class of sequentially greedy optimization problems, we develop a key concept of sequence greediness for analysis and propose a sub-optimal online greedy algorithm with a performance guarantee factor of (1-1/e) as a solution. For the linear threshold (LT) and independent cascade (IC) models, we construct an equivalent view of the information diffusion process over a network in the adaptive case, and further prove that this source selection problem has the property of sequence greediness for the LT model and discuss the sequence greediness for the IC model as well. Leveraging the sequence greediness, we propose the online greedy algorithm for the adaptive influence diffusion maximization problem, that promises a performance guarantee factor of (1-1/e) for the LT model. Besides, we develop a unified model by combing the gossip spreading and influence spreading models, and further discuss the adaptive influence diffusion maximization problem under this unified model. From the experiments, it is demonstrated that the algorithms leveraging the benefit of adaptivity significantly outperforms the non-adaptive algorithm, and the choice of moderate seeding-time intervals to pick successive information sources is sufficient to achieve the adaptivity benefit.3) Third, we study the application of the information source selection problem, focusing on the wireless traffic offloading problem. We develop a theoretical framework for the proximity-based wireless traffic offloading problem, proposing a gossip-style social cascade (GSC) model to model the information spreading process over MSNets and using a local mobility model to model the underlying temporal network. For the static-network and mobile-network cases, we construct an equivalent view and a temporal mapping of the information spreading process over a network, respectively, and further prove that this traffic offloading problem has the property of submodularity. Leveraging the submodularity, we propose a natural sub-optimal greedy algorithm based on the simulation of user contacts for the traffic offloading maximization problem, that promises a performance guarantee factor of (1-1/e). From the experiments, it is demonstrated that a small number of information sources can offload a large volume of traffic load, more traffic load can be offloaded with stronger social participations and longer delay tolerances, and user mobility can further help reduce the traffic load.For the issue of information source detection, our main contributions are as follows:1) First, we study the information source detection problem without prior knowledge under the virus spreading model. For the susceptible-infected (SI) model under regular tree-type networks, we use an optimal rumor centrality-based maximum likelihood (ML) estimator to identify the information source, develop a key concept of local rumor center to solve this source estimator, and obtain the probability distribution of infection samples by leveraging ideas from the Polya’s urn model. Furthermore, from the perspective of the number of infected nodes, we derive the exact correct detection probability in both the finite and asymptotic regimes. The correct detection probability monotonically decreases with the number of infected nodes and monotonically increases with the node degree in the finite regime; and it is0,0.25and0.307in the asymptotic regime when the node degree is2,3and sufficiently large, respectively.2) Second, we study the information source detection problem with prior knowledge under the virus spreading model. For the SI model under regular tree-type networks, we construct an optimal rumor centrality-based maximum a posteriori (MAP) estimator to identify the information source from a prior specified set of suspect nodes, leverage the concept of local rumor center to solve this source estimator, and use the probability distribution of infection samples obtained from the Polya’s urn model to analyze it. Furthermore, we characterize the correct detection probability in both the finite and asymptotic regimes with different connection patterns of suspect nodes. When the suspect nodes form a connected subgraph of the network, the correct detection probability monotonically decreases with the number of infected nodes and monotonically increases with the node degree in the finite regime, and in the asymptotic regime it exceeds the prior probability significantly with the node degree larger than2and reliable detection can be achieved with sufficiently large node degree. When there are only two suspect nodes in the network, the correct detection probability monotonically increases with their distance in the finite regime, and in the asymptotic regime it is no smaller than0.75with the node degree larger than2and reliable detection can be also achieved with sufficiently large node degree. When there are multiple suspect nodes in the network, among all possible connection patterns, the pattern that all the suspect nodes form a single connected subgraph of the network achieves the smallest detection probability for the source estimator.3) Third, we study the application of the information source detection problem, focusing on the computer-virus source identification problem. We use the SI model to model the computer-virus spreading process, leverage the breadth-first search (BFS) strategy to construct an approximate diffusion tree of the virus spreading paths, and construct two rumor centrality-based MAP estimators to identify the virus source from a prior specified set of suspect nodes. Besides, we present some works on the virus source identification problem under the case with the knowledge of multiple observations and under the susceptible-infected-recovered (SIR) model along with susceptible-infected-susceptible (SIS) model. From the experiments, it is demonstrated that the MAP estimator that combines the infection probability of the BFS diffusion tree and the rumor centrality outperforms significantly the MAP estimator that relies only on the rumor centrality, the correction detection probability monotonically decreases with the number of suspect nodes, and it is larger when the suspect nodes are more dispersive.