2012 · 166 citations · 18 references
BusinessMarketingDigital MarketingSocial InfluenceSocial Media MarketingInformation DiffusionSocial Network AnalysisWord-of-mouth MarketingGreedy HeuristicsInfluence FunctionInfluence PropagationInformation Diffusion ModelsScalabilitySpreadingViral Information SpreadViral Spreading
Influence maximization, a key problem in social networks, has been widely studied for applications such as viral marketing, yet prior work has not addressed time constraints. This study introduces a time‑constrained influence maximization problem and proposes two scalable Influence Spreading Path methods to address it. We formulate the problem, design a greedy algorithm with theoretical guarantees, and introduce two Influence Spreading Path techniques to enhance scalability. The problem is NP‑hard, with a monotone submodular spread function, and experiments on four datasets confirm that the proposed path‑based methods are efficient and effective.
Influence maximization is a fundamental research problem in social networks. Viral marketing, one of its applications, is to get a small number of users to adopt a product, which subsequently triggers a large cascade of further adoptions by utilizing "Word-of-Mouth" effect in social networks. Influence maximization problem has been extensively studied recently. However, none of the previous work considers the time constraint in the influence maximization problem. In this paper, we propose the time constrained influence maximization problem. We show that the problem is NP-hard, and prove the monotonicity and submodularity of the time constrained influence spread function. Based on this, we develop a greedy algorithm with performance guarantees. To improve the algorithm scalability, we propose two Influence Spreading Path based methods. Extensive experiments conducted over four public available datasets demonstrate the efficiency and effectiveness of the Influence Spreading Path based methods.
18
Maximizing the spread of influence through a social network
David Kempe, Jon Kleinberg, Éva Tardos · 2003 · 7.3K citations
A New Product Growth for Model Consumer Durables
Frank M. Bass · Management Science · 1969 · 5.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