Source-linked AI summary
A Data-Based Approach to Social Influence Maximization
Amit Goyal, Francesco Bonchi, Laks V. S. Lakshmanan
TL;DR
Influence maximization has largely focused on social-graph structure while overlooking historical propagation traces. This paper introduces credit distribution to estimate spread directly from traces, and derives an approximation algorithm that is accurate and scalable while avoiding probability learning and Monte Carlo simulation.
Problem
Influence maximization traditionally relies on social graphs and edge probabilities, while historical traces of past action propagations have been largely overlooked.
Method
Credit distribution learns influence flow, user influenceability, and temporal effects from propagation traces to predict seed-set spread directly without learning edge probabilities or running Monte Carlo simulations.
Results
The credit-distribution problem is NP-hard, its expected-spread function is monotone and submodular, and the resulting greedy algorithm guarantees a (1−1/e)-approximation.
Takeaways & Limitations
On real datasets, credit distribution is closest to ground truth and the resulting algorithm is highly scalable.
Takeaways & Limitations
Expected-spread computation is #P-hard under classical IC and LT models, and the paper’s algorithm requires maintaining a potentially large data structure UC.
Abstract
from arXiv · showhide
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 influenceability 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.
1. INTRODUCTION
Influence maximization traditionally relies on social graphs and assumed or learned edge probabilities, while this paper proposes directly using historical propagation traces to estimate spread. The approach introduces credit distribution and supports a scalable approximation algorithm.
- Influence maximization seeks k seed users whose activation maximizes expected influence spread under a propagation model.The expected spread is the number of nodes eventually activated.
- Standard methods require a directed graph and edge influence probabilities, but real propagation probabilities are often unavailable and historically assigned using ad hoc assumptions.Examples include constant values, trivalency assignments, and weighted-cascade probabilities.
- The paper asks how graph structure and edge probabilities compare in describing propagation accurately, including against probabilities learned from real traces.
- Directly mining propagation logs could avoid the costly combination of learning edge probabilities and simulating spread.The paper frames this as an alternative to the standard learning-and-simulation process.
- The credit distribution model predicts spread directly from real propagation traces without learning edge probabilities or running Monte Carlo simulations.
- The paper develops a greedy approximation algorithm after showing credit-distribution influence maximization is NP-hard and its spread function is monotone and submodular.The algorithm guarantees a (1−1/e)-approximation and is described as scalable.
- The model is evaluated against the standard approach on large real-world datasets, with higher accuracy and results on networks where the standard approach is impractical.
2. BACKGROUND
The background defines influence maximization over edge-weighted propagation models and reviews the computational and data limitations of standard methods. It then positions the paper’s trace-based spread model as a distinct alternative to prior graph-based heuristics and probability-learning approaches.
- The standard greedy algorithm repeatedly selects the remaining node with the largest marginal expected-spread gain.Its selection rule is u ← arg max over w of σm(S + w) − σm(S).
- IC and LT propagation models describe activation through probabilistic attempts or weighted neighbor influence over discrete time until no new nodes activate.
- Influence maximization selects a size-k set S maximizing expected spread σm(S) on a directed, edge-weighted graph under propagation model m.
- Influence maximization is NP-hard under both IC and LT, while their spread functions are monotone and submodular, enabling a (1−1/e)-approximation through greedy selection.
- Expected-spread computation is #P-hard under IC and LT, so prior work uses many Monte Carlo trials, including 10,000 reported simulations, causing long computation times.
- The standard process estimates edge probabilities from propagation logs, constructs an edge-weighted graph, and then applies greedy optimization with Monte Carlo simulations.
- Other Related Work: Prior work includes CELF, PMIA, and LDAG scalability heuristics, as well as methods learning IC probabilities or modeling time-varying influenceability.
- Other Related Work: This paper instead directly predicts spread for node sets, bypasses edge-probability learning and Monte Carlo simulation, and uses the model for scalable data-based influence maximization.
3. WHY DATA MATTERS
The experiments test how probability assignment affects seed selection and spread prediction, comparing trace-learned methods with ad hoc and perturbed alternatives on Flixster and Flickr.
- Experimental setup: The study compares edge-probability assignments under the IC model using real propagation traces, ad hoc assumptions, and perturbed learned probabilities.Methods include WC, TV, UN, EM, and PT across Flixster and Flickr datasets.
- Experimental setup: The datasets pair unweighted directed social graphs with action logs, while training and test traces support probability learning and spread evaluation.The split keeps each propagation trace entirely in either training or test data.
- Seed set intersection: For seed selection, EM produces seed sets with very small intersections with ad hoc methods, whereas EM and its perturbed version PT overlap substantially more.The experiment uses seed sets of size k = 50; the reported pattern indicates that modest noise in learned probabilities does not drastically change selection.
- Spread prediction: In spread prediction, EM is the most accurate method overall, although it tends to underestimate larger spreads; methods without real traces are unreliable.On Flickr Small, EM outperforms all other methods across actual-spread sizes, while EM and PT are nearly indistinguishable.
- Why data matters: UN, TV, and WC select seeds unlike EM and may choose poor-quality seeds because their predicted spreads can be inaccurate.This conclusion combines the seed-set intersection and spread-prediction experiments.
4. CREDIT DISTRIBUTION MODEL
The credit distribution model estimates influence spread directly from historical propagation traces rather than sampling probabilistic possible worlds. It assigns and aggregates influence credit through time-ordered propagation graphs, producing an objective to maximize.
- Expected spread: Under probabilistic models, expected spread equals the sum across nodes of each node’s activation probability from seed set S.The standard formulation can also be viewed through possible worlds and path indicators.
- Trace-based estimation: Real propagation traces are treated as available worlds for directly estimating Pr[path(S, u) = 1] from the action log.The action log records users, actions, and times, while each action induces a directed acyclic propagation graph.
- Credit assignment: The model assigns direct credit from each user u to earlier neighbors who performed the same action, with total outgoing direct credit constrained to at most 1.Equal credit, when used for exposition, assigns 1/din(u, a) to each potential influencer.
- Credit assignment: Total credit is propagated transitively backward through the action graph, so users receive credit through multiple paths leading to the influenced user.The recursive construction uses Γv,v(a) = 1 as its base case.
- Aggregation: For a node pair, credit is averaged over the actions performed by the influenced user; for a seed set S, these credits are aggregated over all actions and nodes.The resulting κS,u represents the model’s estimate of Pr[path(S, u) = 1], and σcd(S) is the total influence credit from the network.
- Time-aware credit: The model’s direct-credit rule incorporates exponential temporal decay and user influenceability, using average propagation time τv,u and infl(u).User influenceability measures how prone u is to influence by social context, based on actions performed under a neighbor’s influence.
5. INFLUENCE MAXIMIZATION
The CD influence-maximization problem is NP-hard, but its spread function is monotone and submodular, enabling a greedy (1−1/e)-approximation. The section develops an efficient algorithm that computes marginal gains from credit distributions and incrementally updates them during seed selection.
- Complexity and approximation: Influence maximization under the credit distribution model is NP-hard via a reduction from Vertex Cover.The reduction constructs a directed instance with the same nodes and two directed edges for each undirected edge.
- Complexity and approximation: The CD influence-spread function σcd(S) is monotone and submodular.The proof establishes submodularity by induction on propagation-path length, using the acyclic propagation graph.
- Complexity and approximation: Because σcd(S) is monotone and submodular, the greedy algorithm provides a (1−1/e)-approximation to the optimum.The algorithm repeatedly selects a node with the largest marginal gain σcd(S + w) − σcd(S).
- Efficient optimization: The algorithm computes marginal gains from total-credit quantities rather than expensive Monte Carlo simulations.Theorem 3 expresses a node’s marginal gain using normalized marginal gains over actions, with values maintained for the current seed set and its complement.
- Efficient optimization: The method scans the action log, stores user credits and set credits, and uses CELF during greedy seed selection.User Credits stores credit for influencing nodes across actions, while Set Credits stores credit attributed to the current seed set.
- Efficient optimization: Credit values are updated incrementally as nodes enter the seed set, using equations derived from auxiliary lemmas.The updates operate on induced subgraphs and preserve the quantities needed for subsequent marginal-gain computations.
6. EXPERIMENTAL EVALUATION
Experiments compare credit distribution (CD) with IC and LT models on spread prediction, seed selection, runtime, scalability, and truncation. CD predicts spread more accurately, produces materially different and better-performing seeds, and runs far faster, while requiring data-dependent memory.
- Accuracy of Spread Prediction: CD captures a much higher fraction of propagation traces within any given absolute-error tolerance than IC and LT on both datasets.For absolute error ≤30 on Flixster Small, CD captures 67% of propagations, versus 46% for IC and 26% for LT.
- Seed Set Intersection: IC and LT select seed sets that differ substantially from CD, with IC having an empty intersection with both LT and CD on the reported comparison.CD and LT have approximately 50% seed overlap; Flickr Small uses PMIA and LDAG heuristics because greedy Monte Carlo computation is too slow.
- Seed Set Quality: Under CD-based evaluation, seeds selected using IC and LT fall far short of the spread achieved by seeds selected under CD on both datasets.IC also performs worse than High Degree and PageRank in this comparison.
- Seed Set Quality: 30.3 average actions characterize seeds chosen by IC, compared with 1,108.7 for CD-selected seeds.The IC-selected seeds’ average is also below the global average of 167 actions, indicating that many are relatively inactive nodes.
- Running Time: 3 minutes selects 50 Flixster Small seeds with the proposed algorithm, versus 40 and 25 hours for greedy CELF under IC and LT.On Flickr Small, the IC experiment ran 27 days without selecting one seed, LT selected 17 seeds in that time, and the proposed algorithm selected 50 in 6 minutes.
- Scalability: 1M training tuples match the quality of all 6.5M tuples on Flixster Large, while Flickr Large spread converges after 8M tuples.Memory usage scales with training tuples, reaching approximately 16GB for 6.5M Flixster tuples and 46GB for 13M Flickr tuples.
- Effect of truncation threshold: At λ = 0.001, influence spread and true seeds discovered essentially saturate; lowering λ improves accuracy but increases memory and runtime.The experiments use λ = 0.001 as a practical choice, with similar results on Flickr Large and the small datasets.
7. CONCLUSIONS AND DISCUSSION
The paper concludes that influence maximization should directly exploit historical propagation traces rather than rely primarily on social graph structure. Its Credit Distribution model estimates spread efficiently and accurately, while comparisons show data-learned probabilities outperform arbitrary assignments.
- 7. CONCLUSIONS AND DISCUSSION: The Credit Distribution model directly leverages historical propagation traces instead of focusing mainly on social graph structure.It estimates influence spread from past propagations and avoids learning influence probabilities.
- 7. CONCLUSIONS AND DISCUSSION: The model avoids costly Monte Carlo simulations while directly estimating influence spread from historical data.The paper presents this as the basis for an efficient influence-maximization algorithm.
- 7. CONCLUSIONS AND DISCUSSION: The CD model was by far closest to ground truth on real data sets, and the algorithm was highly scalable.These results support both the model’s accuracy and the algorithm’s practical scalability.
- 7. CONCLUSIONS AND DISCUSSION: Methods that arbitrarily assign influence probabilities have larger spread-prediction errors than methods that learn probabilities from data.They also select seed sets very different from data-driven methods, suggesting potentially poor spread.
- 7. CONCLUSIONS AND DISCUSSION: IC and LT models with learned probabilities select seed sets different from each other and from CD, which is closest to ground truth.This comparison highlights that the choice of propagation model affects the selected seeds.