A Model-Free Approach to Infer the Diffusion Network from Event Cascade
Authors:
Open Access
- 24 October 2016
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1653-1662
Abstract
Information diffusion through various types of networks, such as social networks and media networks, is a very common phenomenon on the Internet nowadays. In many scenarios, we can track only the time when the information reaches a node. However, the source infecting this node is usually unobserved. Inferring the underlying diffusion network based on cascade data (observed sequence of infected nodes with timestamp) without additional information is an essential and challenging task in information diffusion. Many studies have focused on constructing complex models to infer the underlying diffusion network in a parametric way. However, the diffusion process in the real world is very complex and hard to be captured by a parametric model. Even worse, inferring the parameters of a complex model is impractical under a large data volume. Different from previous works focusing on building models, we propose to interpret the diffusion process from the cascade data directly in a non-parametric way, and design a novel and efficient algorithm named Non-Parametric Distributional Clustering (NPDC). Our algorithm infers the diffusion network according to the statistical difference of the infection time intervals between nodes connected with diffusion edges versus those with no diffusion edges. NPDC is a model-free approach since we do not define any transmission models between nodes in advance. We conduct experiments on synthetic data sets and two large real-world data sets with millions of cascades. Our algorithm achieves substantially higher accuracy of network inference and is orders of magnitude faster compared with the state-of-the-art solutions.Keywords
Funding Information
- The Chinese University of Hong Kong (Direct Grant No. 4055048)
This publication has 23 references indexed in Scilit:
- Trace complexity of network inference2013
- Discovering latent influence in online social activities via shared cascade poisson processes2013
- Structure and dynamics of information pathways in online media2013
- Inferring networks of diffusion and influence2010
- Meme-tracking and the dynamics of the news cycle2009
- A measurement-driven analysis of information propagation in the flickr social network2009
- Scalable modeling of real graphs using Kronecker multiplication2007
- Tracking Information Epidemics in Blogspace2005
- Talk of the Network: A Complex Systems Look at the Underlying Process of Word-of-MouthMarketing Letters, 2001
- On the Distribution of the Two-Sample Cramer-von Mises CriterionThe Annals of Mathematical Statistics, 1962