A data-based approach to social influence maximization
Authors:
Top Cited Papers
Open Access
- 1 September 2011
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 5 (1) , 73-84
Abstract
Influence maximization is the problem of finding a set of users in a social network, such that by targeting this set, one maximizes the expected spread of influence in the network. Most of the literature on this topic has focused exclusively on the social graph, overlooking historical data, i.e., traces of past action propagations. In this paper, we study influence maximization from a novel data-based perspective. In particular, we introduce a new model, which we call credit distribution , that directly leverages available propagation traces to learn how influence flows in the network and uses this to estimate expected influence spread. Our approach also learns the different levels of influence-ability of users, and it is time-aware in the sense that it takes the temporal nature of influence into account. We show that influence maximization under the credit distribution model is NP -hard and that the function that defines expected spread under our model is submodular. Based on these, we develop an approximation algorithm for solving the influence maximization problem that at once enjoys high accuracy compared to the standard approach, while being several orders of magnitude faster and more scalable.Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Oxidation of Olefins and Alcohols with Pt@Fe2O3NanowiresSynfacts, 2011
- Synthesis of a Phosphodiesterase-4 InhibitorSynfacts, 2010
- Scalable influence maximization for prevalent viral marketing in large-scale social networks2010
- Prediction of Information Diffusion Probabilities for Independent Cascade Model2008
- Cost-effective outbreak detection in networks2007
- Information flow modeling based on diffusion rate for prediction and ranking2007
- Tractable Models for Information Diffusion in Social Networks2006
- Maximizing the spread of influence through a social network2003
- Mining the network value of customers2001
- An analysis of approximations for maximizing submodular set functions—IMathematical Programming, 1978