Source-linked AI summary
A Survey on Influence Maximization in a Social Network
Suman Banerjee, Mamata Jenamani, Dilip Kumar Pratihar
TL;DR
The paper addresses how to select initial nodes to maximize influence in social networks, a problem with applications including viral marketing, target advertisement, and personalized recommendation. It surveys the SIM/TSS literature, including problem variants, solution methodologies, hardness results, research challenges, and future directions, concluding that variants remain less studied and scalable algorithms are still needed.
Problem
The paper examines how to choose k initial nodes that maximize information influence in a social network, a practically important problem studied in multiple variants.
Method
The paper provides an organized survey of the SIM/TSS problem, its variants, solution methodologies, hardness results, research challenges, and future research directions.
Results
The survey concludes that the SIM problem is well studied, while its variants remain less studied and require more scalable algorithms.
Takeaways & Limitations
Future work should develop more scalable algorithms for the variants of the SIM problem.
Takeaways & Limitations
The survey identifies cost, benefit, and time as issues that require consideration in TSS research.
Abstract
from arXiv · showhide
Given a social network with diffusion probabilities as edge weights and an integer k, which k nodes should be chosen for initial injection of information to maximize influence in the network? This problem is known as Target Set Selection in a social network (TSS Problem) and more popularly, Social Influence Maximization Problem (SIM Problem). This is an active area of research in computational social network analysis domain since one and half decades or so. Due to its practical importance in various domains, such as viral marketing, target advertisement, personalized recommendation, the problem has been studied in different variants, and different solution methodologies have been proposed over the years. Hence, there is a need for an organized and comprehensive review on this topic. This paper presents a survey on the progress in and around TSS Problem. At last, it discusses current research trends and future research directions as well.
1. Introduction
The survey introduces Social Influence Maximization as selecting influential seed nodes to maximize information diffusion, motivated by applications and a broad research literature. It organizes problem variants, solution methodologies, and research directions.
- The problem has practical applications in viral marketing, personalized recommendation, feed ranking, target advertisement, and selecting influential online users.
- Limited free samples motivate selecting highly influential users whose subsequent sharing can trigger a large cascade of product adoption.
- Social Influence Maximization selects seed nodes so information, opinions, ideas, innovations, or rumors reach as many users as possible.
- The survey represents social networks as graphs with users as vertices, social ties as edges, vertex thresholds, and edge influence probabilities.
- Its stated goals are to explain SIM and its variants, classify solution methodologies through a taxonomy, and review current trends and future directions.
- The survey excludes adversarial, time-varying, and competitive social-network settings from its considered aspects.
2. Background
The background formalizes graph representations, diffusion models, approximation algorithms, parameterized complexity, and related graph problems used to study influence propagation.
- Information diffusion is represented by a directed, simple, vertex- and edge-weighted graph G(V, E, θ, P).
- Vertex weights represent node thresholds, while edge weights represent diffusion probabilities governing influence difficulty and transmission likelihood.
- Related Graph Problems: TSS generalizes several graph problems, including threshold domination, vertex cover, irreversible conversion, bootstrap percolation, and dynamic monopolies.
- Approximation Algorithms: Approximation algorithms trade exact polynomial-time optimization for affordable computation with worst-case solution-quality guarantees.
- Parameterized Complexity: Parameterized complexity classifies difficulty by parameters, with fixed-parameter tractable running time O(f(k)|x|^O(1)) when the parameter is k.
- Information Diffusion Models: The Independent Cascade model gives active nodes probabilistic opportunities to activate inactive outgoing neighbors, with activation cascading across discrete time steps.
- Information Diffusion Models: The Linear Threshold model activates a node when the combined probability contribution of its newly active neighbors reaches its threshold.
3. SIM Problem and its Variants
The survey traces SIM research from its viral-marketing origins and introduces variants of the basic TSS formulation. The basic version asks whether at most k seeds can activate at least λ nodes.
- SIM was introduced by Domingos and Richardson in the context of viral marketing and later developed into multiple variants.
- The basic SIM formulation uses a directed social network G(V, E, θ, P) with integers k and λ.
- Its decision objective is to find at most k nodes whose completed diffusion activates at least λ nodes.
Top k-node Problem / Social Influence Maximization Problem (SIM Problem)
The Top k-node Problem selects k seed nodes to maximize the number of influenced nodes in a social network. Related TSS variants change the objective or constraints by varying seed-set size, diffusion rounds, target nodes, selection costs, or required coverage.
- Top k-node Problem: The Top k-node Problem seeks a seed set S of exactly k nodes that maximizes the number of influenced network nodes.
- Influence Spectrum Problem: The Influence Spectrum Problem finds an optimal seed set for every k between k_lower and k_upper, producing multiple cardinality-specific solutions.The survey notes that one instance is equivalent to solving k_upper − k_lower + 1 SIM instances, and connects this variant to phased viral marketing.
- λ Coverage Problem: The λ Coverage Problem minimizes seed-set cardinality while requiring at least λ nodes to be influenced after diffusion.
- Weighted Target Set Selection Problem: The Weighted Target Set Selection Problem assigns each vertex a cost and seeks a minimum-cost seed set that influences all network nodes.The vertex weight function represents the selection cost or incentive paid when a vertex is selected as a seed.
- Other TSS Variants: Round-, budget-, and target-constrained variants respectively limit diffusion rounds, impose a seed-selection budget, or require influence over specified nodes.The r-round min-TSS Problem minimizes seed-set size subject to activating all nodes within r rounds; Budgeted Influence Maximization uses nonuniform costs and a fixed budget; (λ, β, A) and (λ, A) TSS target a node set A within λ rounds.
- Coverage of Variants: The survey describes many TSS variants but reports that only the Top-k node Problem has been studied in depth.
4. Hardness Results of TSS Problem
The survey reviews hardness results for TSS/SIM across probabilistic and deterministic diffusion models, classical complexity, and parameterized settings. Results include NP-hardness, inapproximability, W-hardness, and fixed-parameter tractability under specific graph and threshold restrictions.
- SIM is NP-hard under both the IC and LT diffusion models and is also hard to approximate within a stated factor.
- For λ-coverage, TSS cannot be approximated within a constant factor, while majority-threshold variants retain similar hardness.
- When every vertex has threshold 1, selecting one node per connected component activates the entire network; allowing thresholds up to 2 makes TSS NP-hard even on bounded bipartite graphs.
- With unanimous thresholds, TSS is identical to vertex cover, whereas TSS on trees is solvable in polynomial time through the ALG-Tree algorithm.
- Parameterized results vary by structural parameter: majority-threshold TSS is W[1]-hard for several cohesiveness and sparsity measures, while other parameterizations are fixed-parameter tractable.
- TSS remains NP-hard and W[2]-hard when parameterized by target-set size k, even on graphs with clique cover number two.
- Fixed-parameter tractability is obtained for distance to clique when the threshold function satisfies the stated dependence condition.
5. Major Research Challenges
The SIM Problem poses intertwined challenges of computational feasibility, influence quality, scalability, and modeling assumptions. The survey organizes existing methodologies while highlighting limits from heuristic trade-offs, non-submodular objectives, unrealistic assumptions, and computational hardness.
- Theoretical Challenges: The SIM Problem is generally hard in traditional and parameterized complexity frameworks, complicating feasible selection of the most influential k nodes.The survey presents hardness results for TSS and its variants in both frameworks and develops a taxonomy of existing solution methodologies.
- Trade of Between Accuracy and Computational Time: Heuristic seed selection can reduce seed-set generation time, but may produce arbitrarily fewer influenced nodes.The challenge is to balance affordable execution time against the gap between algorithmic and optimal spread.
- Breaking the Barrier of Submodularity: The SIM Problem may lose submodularity when nodes switch between positive and negative opinions, making optimization more challenging.Opinion and topic-specific influence settings are identified as practical situations where submodularity may not hold.
- Practicality of the Problem: SIM assumptions that seeds perform up to expectation and that every network node matters equally may be unrealistic in some situations.Relaxing these assumptions makes the SIM Problem and its variants more challenging.
- Scalability: Real-life social networks contain millions of nodes and billions of edges, making scalability important for SIM and related solutions.Methods must address the size of real-world network instances.
- Theoretical Challenges: Theoretical research must address computational complexity, while practical methods must also account for execution time on real-life instances.The survey distinguishes execution time from asymptotic computational complexity as two aspects of solution methodology.
6. Solutions Methodologies
The survey organizes SIM solution methodologies into approximation, heuristic, meta-heuristic, community-based, and miscellaneous categories, emphasizing trade-offs between guarantees, influence quality, and scalability.
- The proposed taxonomy classifies SIM algorithms by approach, including provable approximation, heuristic, meta-heuristic, community-based, and miscellaneous solutions.The taxonomy is diagrammed in Figure 2 and described across the section.
- Approximation algorithms with provable guarantee: Approximation algorithms provide worst-case influence-spread bounds, but most suffer from scalability issues as network size increases.Running time grows heavily with increasing network size.
- Heuristic and meta-heuristic solutions: Heuristic and meta-heuristic algorithms generally improve scalability or running time but do not provide worst-case influence-spread guarantees.Meta-heuristics include evolutionary computation techniques.
- Community-based solutions: Community-based methods detect communities to reduce SIM to community-level problems and improve scalability, although most are heuristic and lack worst-case guarantees.The absence of guarantees is stated for both community-based and meta-heuristic approaches.
- Influence estimation: Influence-spread estimation is computationally difficult, motivating Monte Carlo simulation and reverse-reachable-set methods to reduce evaluation costs.Exact influence-spread computation is #P-Complete, while basic greedy selection may require O(kmnR) evaluations.
7. Summary of the Survey and Future Research Directions
The survey identifies unresolved practical and methodological challenges in SIM, including scalability, unrealistic diffusion assumptions, limited benchmarking, and insufficient support for dynamic, distributed, and adaptive settings.
- Practical problem formulations: The survey calls for models incorporating cost, benefit, and time, including influence benefits and diffusion-time constraints for time-sensitive events.It also points to incentivization and multiphase diffusion as settings for further study.
- Practicality of the problem: Reverse reachable sets have become a common alternative to Monte Carlo spread estimation for improving scalability in popular SIM algorithms.TIM, IMM, and TIM+ use reverse reachable sets as an influence-spread estimation technique.
- Diffusion probability computation: The assumption that influence probabilities are known is unrealistic, motivating machine-learning approaches for predicting them.The survey identifies diffusion-probability computation as a future research direction.
- Problem variants: Future work should address time-varying networks, newer diffusion models with negative opinions, and topic-aware influence settings.The survey notes that most studies use IC or LT models and static networks, while temporal and topic-aware research remains limited.
- Algorithmic directions: Distributed and parallel methods, multiphase diffusion, and additional meta-heuristics are identified as open directions for improving SIM solutions.The survey notes that most algorithms are serial and that distributed work is especially limited.
- Evaluation and methodology: Benchmarking remains insufficient because experiments with 11 popular algorithms found contradictions between new results and previously reported results.The survey therefore recommends more comparative studies using benchmark datasets.
8. Concluding Remarks
The survey integrates SIM variants, hardness results, challenges, and solution methodologies into a three-dimensional review, then identifies continuing gaps in variants and scalability.
- The survey covers SIM variants, hardness results, research challenges, classified solution methodologies, current trends, and future directions.These topics are presented across the paper’s major sections.
- SIM is well studied, but its variants remain less studied and there is continuing demand for more scalable algorithms.This is the survey’s stated conclusion.
- Considering variants, hardness results, and solution methodologies together is intended to improve researchers’ and practitioners’ understanding of SIM.The survey describes this as a three-dimensional view of the problem.