The problem of identifying the source of a propagation based on limited observations has been studied significantly in recent years, as it can help reducing the damage caused by unwanted infections. In this paper we present an efficient approach to find the node that originally introduced a piece of information into the network, and infer the time when it is initiated. Labeling infected nodes detected in limited observation as observed nodes and other ones as hidden nodes, we first estimate the shortest path between hidden nodes to observed ones for each propagation trace. Then we find the best node as the source among the hidden nodes by optimizing over square loss function. The method presented in this paper is based on more realistic situations and is easy and more practical than previous works. Our experiments on real-world propagation through networks show the superiority of our approach in detecting true source, boosting the top ten accuracy from less than 10 for the sate-of-the-art methods to approximately 30 . Additionally, we observe that our source identification method runs about 10 times faster than previous work.
Over recent years, much work has been done with different perspectives on diffusion networks. There are some works on uncovering the hidden network based on propagation traces @cite_0 @cite_11 @cite_12 @cite_16 @cite_4 , the spread of influence through a network @cite_14 @cite_3 , reconstructing the propagation of an activity in a network @cite_21 , and finding the source of a propagation trace @cite_18 @cite_15 @cite_7 .
@cite_18 @cite_14 @cite_4 @cite_7 @cite_21 @cite_3 @cite_0 @cite_15 @cite_16 @cite_12 @cite_11
1587790278 188609219 2092129584 2949499549
Learning about the structure of hidden or covert networks is a major challenge in epidemiology, sociology, and intelligence analysis. Vertices in hidden networks usually cannot be enumerated or sampled in a systematic way; they can only be revealed by tracing links emanating from already-observed vertices. Observers sometimes cannot follow links directly, and instead must rely on passive observation of a dynamic process to reveal vertices and edges. This paper outlines a framework for estimating network structures from partial observation of information diffusion through the network. Diffusion is modeled by a continuous-time Markov epidemic model. Edges are revealed by transmission events and new vertices are uncovered when information is transmitted to them. The approach is a generalization of tools developed to reconstruct drug-user networks from respondent-driven sampling studies in epidemiology. The likelihood of the diffusion process can be interpreted as an exponential random graph model. A Bayesian method for probabilistic reconstruction of the transmission-induced subgraph is described. Analyzing the spreading patterns of memes with respect to their topic distributions and the underlying diffusion network structures is an important task in social network analysis. This task in many cases becomes very challenging since the underlying diffusion networks are often hidden, and the topic specific transmission rates are unknown either. In this paper, we propose a continuous time model, TOPICCASCADE, for topicsensitive information diffusion networks, and infer the hidden diffusion networks and the topic dependent transmission rates from the observed time stamps and contents of cascades. One attractive property of the model is that its parameters can be estimated via a convex optimization which we solve with an efficient proximal gradient based block coordinate descent (BCD) algorithm. In both synthetic and real-world data, we show that our method significantly improves over the previous state-of-the-art models in terms of both recovering the hidden diffusion networks and predicting the transmission times of memes. The analysis of network connections, diffusion processes and cascades requires evaluating properties of the diffusion network. Properties of interest often involve variables that are not explicitly observed in real world diffusions. Connection strengths in the network and diffusion paths of infections over the network are examples of such hidden variables. These hidden variables therefore need to be estimated for these properties to be evaluated. In this paper, we propose and study this novel problem in a Bayesian framework by capturing the posterior distribution of these hidden variables given the observed cascades, and computing the expectation of these properties under this posterior distribution. We identify and characterize interesting network diffusion properties whose expectations can be computed exactly and efficiently, either wholly or in part. For properties that are not nice' in this sense, we propose a Gibbs Sampling framework for Monte Carlo integration. In detailed experiments using various network diffusion properties over multiple synthetic and real datasets, we demonstrate that the proposed approach is significantly more accurate than a frequentist plug-in baseline. We also propose a map-reduce implementation of our framework and demonstrate that this can analyze cascades with millions of infections in minutes. Diffusion and propagation of information, influence and diseases take place over increasingly larger networks. We observe when a node copies information, makes a decision or becomes infected but networks are often hidden or unobserved. Since networks are highly dynamic, changing and growing rapidly, we only observe a relatively small set of cascades before a network changes significantly. Scalable network inference based on a small cascade set is then necessary for understanding the rapidly evolving dynamics that govern diffusion. In this article, we develop a scalable approximation algorithm with provable near-optimal performance based on submodular maximization which achieves a high accuracy in such scenario, solving an open problem first introduced by Gomez- (2010). Experiments on synthetic and real diffusion data show that our algorithm in practice achieves an optimal trade-off between accuracy and running time.