A Data-Based Approach to Social Influence Maximization

By Amit Goyal, Francesco Bonchi, Laks V. S. Lakshmanan. 2011

483 citations recorded by the source corpus.

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.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Scalable Influence Estimation in Continuous-Time Diffusion Networks (2013, background): “Most previous work in the literature tackled the influence estimation and maximization problems for infinite time window [1, 2, 3, 4, 5, 6].”
IRIE: Scalable and Robust Influence Maximization in Social Networks (2011, background): “propose a data-based approach to social influence maximization [15].”
Time-Critical Influence Maximization in Social Networks with Time-Delayed Diffusion Process (2012, background): “Two classical propagation models studied in the the literature are the Independent Cascade (IC) and the Linear Threshold (LT) model.”
Influence Maximization in Near-Linear Time: A Martingale Approach (2015, methodology): “This setting is adopted in previous work [7, 19, 24, 36].”
Microscopic Social Influence (2012, background): “Existing research mostly focuses on studying network dynamics within the setting of a single, homogenous network, with examples including diffusion and propagation [1], influence maximization [2, 7], community formation [16], and network evolution [17, 18].”
Influence maximization: near-optimal time complexity meets practical efficiency (2014, methodology): “, when the influence propagation process follows a different model [10, 22], when there are multiple parties that comp ete with each other for social influence [2, 23], or when the influe nce propagation process terminates at a predefined timestamp [4 ].”
Recommender Systems (2016, unknown): “Recent work has also shown how influence analysis can be performed directly from the social stream [80, 233, 573].”