Scalable Influence Maximization in Large Social Networks

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2269 papers319 conceptsfrozen 2026-10-04

The core challenge of viral marketing and epidemic control is a selection problem: if you can only influence a small number of individuals, which ones should you choose to trigger the largest possible cascade? This is known as Influence Maximization (IM). While the problem is easy to state, it is notoriously difficult to solve. Selecting the optimal "seed set" of nodes is NP-hard, and even estimating the resulting spread for a given set is #P-hard, requiring thousands of expensive Monte-Carlo simulations.

As social networks have grown to include billions of edges, researchers have moved away from exact solutions toward scalable approximations that replace brute-force simulation with structural proxies, continuous dynamics, and distributed computing.

The Computational Bottleneck

The traditional approach to IM uses a greedy algorithm: start with an empty set and repeatedly add the node that provides the largest marginal increase in expected influence. While this provides a provable approximation guarantee, it is computationally grueling. To estimate the "marginal increase," one typically runs thousands of random simulations (Monte-Carlo) to see how far the information travels.

To break this bottleneck, researchers have developed methods that avoid simulation entirely. Biao Xiang, Qi Liu, and colleagues proposed the Linear Circuit Model For Social Influence, which treats a network like an electrical circuit. By mapping influence to "potential" and trust to "conductance," they transform the stochastic simulation problem into a linear algebra problem, achieving massive speedups with minimal loss in accuracy. Similarly, Kyomin Jung and Wooram Heo introduced IRIE, which uses a message-passing approach to identify influential nodes in a fraction of the time required by traditional greedy methods.

From Discrete Steps to Continuous Dynamics

A recent shift in the field treats information spread not as a series of discrete "flips" (where a node becomes active), but as a continuous-time dynamical system. This allows researchers to use the tools of calculus and differential equations.

Ruize Gao and Xiaokui Xiao developed the Framework of dIffusion approxiMation (FIM), which models diffusion using ordinary differential equations (ODEs). By making the process differentiable, they can use gradient-based optimization to find influential nodes. This "differentiable influence" approach is also seen in the work of Ambuj Singh and Saurabh Sharma, whose Dynamic Gradient Influencing (DGI) framework uses Graph Neural Networks to find the minimum budget needed to hit a specific adoption target.

Leveraging Network Structure

Intuition suggests that influencers shouldn't just be popular; they should be strategically placed. If two influencers have overlapping audiences, their collective impact is redundant.

To address this, researchers are looking at higher-order structures:

  • Hypergraphs: Real-world interactions often happen in groups (chats, meetings) rather than pairs. Chuang Liu and Xiu-Xiu Zhan developed the Heuristic Degree Discount (HDD) for hypergraphs, which explicitly accounts for influence overlap to ensure the seed set is diverse.
  • Communities: Social networks are naturally modular. A Community-Aware Framework uses a divide-and-conquer strategy, partitioning the network into communities and solving for influencers locally before aggregating them globally. This significantly reduces the search space.

Scaling to Billions of Edges

For modern web-scale graphs, even efficient heuristics can struggle on a single machine. The frontier of the field involves distributed and streaming algorithms.

Jing Tang and Kai Han introduced DIIMM, a distributed framework that partitions data across clusters to handle networks with billions of edges. Meanwhile, Reet Barik and Mahantesh Halappanavar developed GreediRIS, which uses asynchronous streaming to break communication bottlenecks on supercomputers. These methods ensure that as networks grow, our ability to identify their most critical nodes keeps pace.

Papers in this version

Showing 60 of 269 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 263 papers
  2. Version 1 · 2026-10-04 · 269 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_influence_maximization_complexity_5786ebca,
  title = {influence maximization complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/influence-maximization-complexity/rdr_5786ebca5beb4dd4ba5f423dae94229f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_scalable_influence_maximization_in_large_5786ebca_v1,
  title = {Scalable Influence Maximization in Large Social Networks},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scalable-influence-maximization-in-large-social-networks/rdr_5786ebca5beb4dd4ba5f423dae94229f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}