Source-linked AI summary
IRIE: Scalable and Robust Influence Maximization in Social Networks
Kyomin Jung, Wooram Heo, Wei Chen
TL;DR
Influence maximization asks how to choose a small set of seed nodes for maximum spread under diffusion models. The paper proposes IRIE, combining influence ranking and estimation for IC and IC-N, and reports comparable coverage with much better scalability and robustness than existing algorithms.
Problem
Influence maximization requires selecting seed nodes to maximize spread, but existing greedy and heuristic approaches face scalability limitations, especially when influence estimation is expensive.
Method
IRIE integrates message-passing influence ranking with influence estimation and extends the framework from IC to IC-N diffusion.
Results
IRIE achieves comparable or better influence coverage than competing methods while using less time and memory, including on IC-N.
Takeaways & Limitations
IRIE provides a scalable and robust influence-maximization framework that avoids storing and computing local data structures.
Takeaways & Limitations
IRIE’s activation-probability estimate is not exact, although experiments report high accuracy; its estimation component can be replaced by another estimator.
Abstract
from arXiv · showhide
Influence maximization is the problem of selecting top $k$ seed nodes in a social network to maximize their influence coverage under certain influence diffusion models. In this paper, we propose a novel algorithm IRIE that integrates a new message passing based influence ranking (IR), and influence estimation (IE) methods for influence maximization in both the independent cascade (IC) model and its extension IC-N that incorporates negative opinion propagations. Through extensive experiments, we demonstrate that IRIE matches the influence coverage of other algorithms while scales much better than all other algorithms. Moreover IRIE is more robust and stable than other algorithms both in running time and memory usage for various density of networks and cascade size. It runs up to two orders of magnitude faster than other state-of-the-art algorithms such as PMIA for large networks with tens of millions of nodes and edges, while using only a fraction of memory comparing with PMIA.
1 Introduction
The paper addresses scalable influence maximization under IC and IC-N diffusion models by introducing IRIE, which combines influence ranking and estimation. Experiments report comparable influence coverage with substantially better scalability, memory usage, and robustness than existing methods.
- Motivation: Influence maximization selects k seed nodes to maximize expected influence spread in social networks.The paper focuses on this second component of large-scale viral marketing technology.
- Models: The study covers the independent cascade model and IC-N, its extension incorporating negative opinions.IC is widely used across economics, epidemiology, and sociology, while IC-N models negative opinion propagation.
- Approach: IRIE combines global influence ranking with influence estimation instead of estimating every candidate’s spread at every greedy round.This design targets the costly first round and integrates ranking with estimation to account for overlapping influence coverage.
- Results: IRIE matches or exceeds PMIA’s influence spread while achieving up to two orders of magnitude speedup and significant memory savings.The paper compares IRIE with greedy, PMIA, simulated annealing, and PageRank across synthetic and real-world networks.
- Results: Under IC-N, IRIE achieves comparable influence coverage while scaling much better than the MIA-N heuristic.This demonstrates applicability beyond the classic IC model.
- Prior limitations: Existing methods face scalability limits, with PMIA’s running time sensitive to network structure and cascade size.The paper identifies clustering coefficient, edge density, and cascade size as sources of PMIA’s sensitivity.
2 Model and Problem Setup
The paper formalizes influence maximization under IC and IC-N diffusion processes, then motivates scalable estimation because exact influence computation and Monte Carlo greedy selection are computationally expensive.
- IC model: Influence maximization chooses a size-k seed set in a directed network to maximize expected activated nodes under the IC model.Edges carry propagation probabilities, and nodes transition from inactive to active only.
- IC model: In the IC process, seeds activate first, then newly active nodes independently attempt to activate inactive out-neighbors with edge-specific probabilities.The cascade ends when no nodes are activated in a step.
- Optimization: The influence function is nonnegative, monotone, and submodular, enabling the greedy algorithm’s (1 −1/e)-approximation guarantee.The guarantee applies relative to an optimum solution.
- Optimization: Greedy repeatedly adds the node with maximum marginal influence until the seed set reaches size K.The algorithm evaluates every node outside the current seed set at each round.
- Computational challenge: Exact influence computation is #P-hard, while Monte Carlo estimates can make greedy selection impractical for networks with millions of nodes and edges.Alternative heuristics include shortest-path, Shapley-value, and related influence measures.
- IC-N model: IC-N gives nodes neutral, positive, or negative states, with quality factor q governing positive activation outcomes.Negative activation can dominate when caused by a negative node, reflecting negativity bias.
- IC-N model: Under IC-N, the influence function counts expected positive activations and retains monotonicity, non-negativity, and submodularity.Therefore, greedy also has a (1 −1/e)-approximation guarantee for IC-N.
3 Our Algorithm
IRIE combines message-passing influence ranking with influence estimation and greedy seed selection to scale influence maximization under IC and IC-N models. Its approximations address overlapping influence coverage while retaining fast iterative computation.
- Influence Ranking: IRIE derives linear equations for marginal influence estimates and solves them with an iterative message-passing method.The approach replaces Monte Carlo estimation and PMIA's local-tree generation with faster iterative computation.
- Scalability: One IP iteration can require O(Σv∈V d_in(v)·d_out(v)) time, motivating the simplified IR whose iterations use O(Σv∈V d_out(v)) time.Experiments report that simple IR preserves nearly the accuracy of IP and is faster than Greedy and PMIA, especially on large or dense networks.
- Influence Ranking: Simple influence ranking uses a damping factor α to reduce loop and multi-count effects in relaxed influence paths.The resulting series weights longer paths by α, while the paper notes convergence conditions involving the influence matrix.
- IRIE: IRIE integrates ranking, influence estimation, and greedy selection to account for overlapping influence coverage among seed nodes.Simple ranking cannot generally sum individual influences because seed nodes have influence dependencies.
- Influence Estimation: IRIE extends simple ranking by estimating σ(u|S) for a fixed seed set through influence estimation and MIOA structures.MIOA approximates each seed's local influence region using a highest-probability propagation path; the estimation component can use alternative estimators.
- IRIE-N: IRIE-N estimates net influence under IC-N by subtracting λ-weighted negative influence from positive influence and selecting nodes by marginal net influence.The extension separately estimates positive and negative marginal influence components across K selection rounds.
4 Experiments
The experiments evaluate influence-maximization algorithms across scalability, propagation-model sensitivity, influence spread, running time, and memory efficiency.
- The experiments compare IRIE and other state-of-the-art influence-maximization algorithms on scalability, propagation-model sensitivity, influence spread, running time, and memory efficiency.
4.1 Experimental Setup
The evaluation uses five real-world networks, standard WC and TR propagation models, multiple baselines, and Monte-Carlo influence-spread estimates for IC and IC-N models.
- Five real-world social networks contain between 29K and 69M edges, spanning co-authorship and directed friendship graphs.
- The Weighted cascade model assigns each edge probability P_uv = 1/d_v, while Trivalency randomly assigns probabilities from {0.1, 0.01, 0.001}.
- The study compares IRIE with optimized greedy, PMIA, simulated annealing, PageRank, Degree, IR, and IC-N variants including CELF-N, MIA-N, and IRIE-N.
- IR and IRIE use α = 0.7; PMIA and IRIE-related MIOA generation use θ values of 1/320, while IC-N variants use θ = 1/160.
- Influence spread is estimated by averaging 10,000 Monte-Carlo simulations for each seed set under both IC and IC-N models.
4.2 Experimental Results
Experiments show that IRIE preserves influence-spread quality while substantially improving scalability, runtime stability, and memory efficiency across synthetic and real-world networks.
- Scalability Test: IR and IRIE scale efficiently with network size, while PMIA is about 2-10 times slower as nodes increase.With fixed node count, IR and IRIE also show much better runtime and scalability as edge density increases.
- Sensitivity to Propagation Probability Models: More than 1000 times faster than PMIA for the (0.16, 0.016)-bivalency model, IRIE also has more stable runtime as propagation probabilities increase.PMIA runtime increases dramatically around i = 8, where spread size becomes large.
- Influence Spread: IRIE achieves influence spread almost similar to CELF and generally matches or exceeds PMIA across seed sizes and propagation models.IRIE outperforms SAEDV by a large margin in most K=50 comparisons.
- Running Time: More than 1000 times faster than CELF, IRIE runs quickly across real-world datasets under both WC and TR models.IRIE is also faster than PMIA in most cases.
- Running Time: PMIA runtime is unstable across networks, running longer on smaller Epinions and Slashdot graphs than on larger DBLP graphs.The paper relates this sensitivity to clustering coefficient, edge density, and spread size.
- Memory Usage: 2-7 times larger than IRIE, PMIA uses substantially more memory than IRIE across datasets; on LiveJournal, PMIA requires about 10GB versus IRIE's 3GB under WC.Under TR, PMIA requires about 16GB on LiveJournal, while IRIE's usage remains close to its WC usage.
4.3 Experiments on IC-N Model
IRIE is adapted to the IC-N model with negative-opinion propagation, where it achieves comparable or best influence spread and substantially faster runtime than competing methods.
- Influence Spread: Under IC-N with λ = 0, Greedy-N and IRIE-N show the best influence-spread performance, while MIA-N is slightly worse than IRIE-N.For Arxiv-TR, IRIE-N has more stable influence spread than MIA-N.
5 Conclusion
IRIE is a scalable and robust influence-maximization algorithm for the IC and IC-N models. Its iterative ranking and influence-estimation design avoids local data structures, delivering strong coverage with major runtime and memory savings; its simple computation also supports parallelization.
- Algorithm and scope: IRIE combines iterative ranking with influence estimation for influence maximization under the IC and IC-N models.The design targets scalability and robustness while maintaining good influence coverage.
- Algorithm and scope: Avoiding local data-structure storage and computation yields significant savings in memory usage and running time.
- Empirical conclusion: Up to two orders of magnitude speed-up with only a small fraction of memory usage is demonstrated, especially on networks with average degree greater than 10.
- Future scalability: IRIE's simple iterative computation can be readily ported to parallel graph platforms such as Google's Pregel.The paper identifies parallel validation and extension to other diffusion models as future directions.
A Proof of Theorem 2
The proof establishes that Algorithm 2 computes the intended message-passing values by induction on distance. On tree graphs, these values converge to the exact influence quantities because the longest shortest path is at most |V| − 1.
- Inductive equality: Algorithm 2's computed values are shown equal to the expected activated-node counts by mathematical induction on t.The base case is ˜m0(u, v) = m0(u, v) = 0, and the induction hypothesis handles all earlier distances.
- Tree decomposition: For a rooted tree, mt−1(w, u) represents the expected influence from w within distance t − 1 in subtree Tuw.
- Tree decomposition: Linearity of expectation over the rooted tree connects each node's influence quantity to the recursive message-passing computation.
- Convergence: The message sequences converge by t ≤ |V| because the graph's longest shortest path is at most |V| − 1.The converged computed values therefore equal the intended m(u, v) values.