2015 · 30 citations · 27 references
Social SciencesEvolutionary BiologyComplex SystemsEvolutionary TheorySocial InfluenceDynamic Network AnalysisInformation DiffusionInformation SpreadNetwork DynamicsSocial Network AnalysisDiffusion On NetworksInformation Diffusion ModelsNetwork DiffusionNetwork Diffusion ModelsNetwork EvolutionSpreading ProcessesTemporal Evolution Of Networks
Diffusion in social networks has been studied extensively in the past few years. Most previous work assumes that the underlying network is a static object that remains unchanged as the diffusion process progresses. However, there are several real-life networks that change dynamically over time. In this paper, we study diffusion on such evolving networks and extend the popular Independent Cascade and Linear Threshold models to account for network evolution. In particular, we introduce two natural variations, a persistent and a transient one, to capture diffusions of different types. We consider the problem of influence maximization where the goal is to select a few influential nodes to initiate a diffusion with maximum spread. We show that, surprisingly, when considering evolving networks the diffusion function is no longer submodular for the transient models, and not even monotone for the transient Independent Cascade model. We also show that, depending on the model, delaying the activation of the initiators may improve diffusion. Our experiments, using three real datasets, demonstrate the effect of network evolution on the diffusion process, and highlight the importance of timing in the selection process.
27
Maximizing the spread of influence through a social network
David Kempe, Jon Kleinberg, Éva Tardos · 2003 · 7.3K citations
Eunjoon Cho, Seth A. Myers, Jure Leskovec · 2011 · 2.9K citations
Mining the network value of customers
Pedro Domingos, Matt Richardson · 2001 · 2.9K citations
Cost-effective outbreak detection in networks
Jure Leskovec, Andreas Krause, Carlos Guestrin et al. · 2007 · 2.5K citations · Full text
Public Health, Environmental Sciences, Outbreak Detection +7