Efficient influence maximization in social networks

Wei ChenYajun WangSiyu Yang

article2009KDD2,339 citations

Develops degree discount heuristics and improved greedy algorithms for influence maximization in social networks, matching the influence spread of standard greedy approaches while reducing computation time from hours to milliseconds on graphs with tens of thousands of nodes.

Listen

Modern online social networks are primary channels for viral marketing and information dissemination, yet identifying the most influential initial users (seeds) to maximize message spread remains a severe computational bottleneck. While traditional greedy approximation algorithms offer guaranteed influence spread, their reliance on repeated simulations requires hours or days to evaluate even moderately sized networks. The article sets out to design and evaluate faster greedy algorithms and practical degree discount heuristics to achieve both scalable runtime and high influence spread across large-scale social networks.

The authors tackled the challenge through two complementary approaches evaluated on real-world academic collaboration networks (NetHEPT with 15,233 nodes and NetPHY with 37,154 nodes). First, they refined greedy simulation techniques by batch-evaluating reachable components across sampled graphs and combining them with the state-of-the-art Cost-Effective Lazy Forward scheme. Second, they developed fast heuristic algorithms—most notably a tailored degree discount method—that dynamically adjust a candidate node's connection score based on how many of its neighbors have already been selected as seeds.

The findings reveal that fine-tuned heuristics can resolve the scalability dilemma in viral marketing. The proposed degree discount heuristic ran in just a few milliseconds—over six orders of magnitude faster than greedy algorithms—while achieving an influence spread virtually identical to the greedy benchmark (matching it on one network and trailing by only 3.4% on the other). A simpler universal discount heuristic also consistently surpassed standard degree and distance baselines. For applications requiring theoretical guarantees, the article's mixed greedy algorithms reduced computational runtime by 15% to 34% compared to the fastest existing greedy methods without any loss in spread quality. Furthermore, the seed sets selected by these techniques proved robust when tested under alternative influence propagation models.

These results demonstrate that organizations do not need to invest heavy computing resources into slow simulation-based algorithms to run effective influence campaigns. By adopting degree discount heuristics, decision-makers can identify high-impact seed audiences instantly on dynamic, large-scale platforms. Where absolute theoretical performance bounds are mandatory, hybrid greedy approaches offer modest runtime savings, though heuristics provide the only truly scalable path forward. Future work should explore extending tailored degree discounts to other network diffusion models and incorporating community structure to further refine targeting accuracy.

Microsoft Tsinghua University approximation algorithms database systems heuristic approaches Uence Algorithm Model

Chen et al (2009).pdf

Paper: Maximizing the spread of influence through a social network, David Kempe et al. (2003). This foundational paper formalizes the influence maximization problem and establishes the submodularity framework that the source paper builds upon and accelerates.
Paper: Cost-effective outbreak detection in networks, J. Leskovec et al. (2007). Understanding this foundational work on scalable submodular optimization algorithms provides the necessary context for the efficient network analysis methods studied in the source.

No sufficiently relevant recommendations were found.

Cover for Efficient influence maximization in social networks

Abstract

Influence maximization is the problem of finding a small subset of nodes (seed nodes) in a social network that could maximize the spread of influence. In this paper, we study the efficient influence maximization from two complementary directions. One is to improve the original greedy algorithm of [5] and its improvement [7] to further reduce its running time, and the second is to propose new degree discount heuristics that improves influence spread. We evaluate our algorithms by experiments on two large academic collaboration graphs obtained from the online archival database arXiv.org. Our experimental results show that (a) our improved greedy algorithm achieves better running time comparing with the improvement of [7] with matching influence spread, (b) our degree discount heuristics achieve much better influence spread than classic degree and centrality-based heuristics, and when tuned for a specific influence cascade model, it achieves almost matching influence thread with the greedy algorithm, and more importantly (c) the degree discount heuristics run only in milliseconds while even the improved greedy algorithms run in hours in our experiment graphs with a few tens of thousands of nodes.

Based on our results, we believe that fine-tuned heuristics may provide truly scalable solutions to the influence maximization problem with satisfying influence spread and blazingly fast running time. Therefore, contrary to what implied by the conclusion of [5] that traditional heuristics are outperformed by the greedy approximation algorithm, our results shed new lights on the research of heuristic algorithms.

Topics

approximation algorithms database systems heuristic approaches social networks bipartite graphs

Keywords

Uence Algorithm Model Uence Spread Greedy Algorithms Greedy Algorithm Graph Social Time

1. INTRODUCTION
2. IMPROVING THE GREEDY ALGORITHM
2.1 Problem definition and the greedy algorithm
2.2 Improvement for the independent cascade model
2.3 Improvement for the weighted cascade model
3. DEGREE DISCOUNT HEURISTICS
4. EXPERIMENTS
4.1 Experiment setup
4.2 Experiment results
4.3 Discussion on the results
5. CONCLUDING REMARKS
6. REFERENCES

Knowls

Knowl 1 — Degree Discount Formula in Independent Cascade Model
theoretical result
In an undirected graph $G = (V, E)$ under the independent cascade (IC) model with uniform propagation probability $p$ , let $N(v) = \{v\} \cup \{w \in V \mid vw \in E\}$ denote the closed neighborhood of vertex $v$ , and let $\text{Star}(v)$ denote the subgraph induced by $N(v)$ retaining only edges incident to $v$ . Let $d_v$ be the degree of $v$ , and let $t_v$ be the number of neighbors of $v$ that have already been selected as seed nodes.

Assuming $d_v = O(1/p)$ and $t_v = o(1/p)$ as $p \to 0$ , the expected number of additional vertices in $\text{Star}(v)$ influenced by adding $v$ to the seed set is:

$1 + \left(d_v - 2t_v - (d_v - t_v)t_v p + o(t_v)\right) \cdot p$

For a vertex with no seed neighbors ( $t_v = 0$ ), this expected marginal influence in $\text{Star}(v)$ is $1 + d_v p$ . Comparing the two cases implies that when selecting seeds, the effective degree of a vertex $v$ with $t_v$ seed neighbors should be discounted to $dd_v$ :

$dd_v = d_v - 2t_v - (d_v - t_v)t_v p$
Knowl 2 — DegreeDiscountIC Algorithm
algorithm
The DegreeDiscountIC algorithm is a fast heuristic for selecting $k$ seed nodes under the independent cascade (IC) model with propagation probability $p$ . It initializes the discounted degree $dd_v$ of each vertex $v$ to its graph degree $d_v$ and sets its count of seed neighbors $t_v = 0$ . In each of $k$ iterations, it greedily selects the vertex $u$ with the maximum discounted degree, adds $u$ to seed set $S$ , and updates $t_v$ and $dd_v$ for every unselected neighbor $v$ of $u$ .
Input: Undirected graph $G = (V, E)$ , seed set size $k$ , propagation probability $p$
Output: Seed set $S$
Initialize $S = \emptyset$
for each vertex $v \in V$ do
    compute its degree $d_v$
     $dd_v = d_v$
     $t_v = 0$
for $i = 1$ to $k$ do
     $u = \arg\max_{v \in V \setminus S} \{dd_v\}$
     $S = S \cup \{u\}$
    for each neighbor $v \in V \setminus S$ of $u$ do
         $t_v = t_v + 1$
         $dd_v = d_v - 2 t_v - (d_v - t_v) t_v p$
return $S$
When implemented with a Fibonacci heap to maintain maximum discounted degrees, the algorithm runs in $O(k \log n + m)$ time, where $n = |V|$ and $m = |E|$ .
Knowl 3 — NewGreedyIC Algorithm
algorithm
NewGreedyIC accelerates greedy seed selection in the independent cascade model by computing marginal influence spreads across all candidate vertices simultaneously on pre-sampled live-edge graphs. For each of $R$ simulation rounds, an undirected random graph $G'$ is generated by retaining each edge of $G$ with probability $p$ . A linear graph traversal on $G'$ identifies the reachable set $R_{G'}(S)$ from current seed set $S$ and the component sizes $|R_{G'}(\{v\})|$ for all $v \in V$ . The incremental influence of vertex $v \in V \setminus S$ in $G'$ is $|R_{G'}(\{v\})|$ if $v \notin R_{G'}(S)$ and $0$ otherwise.
Input: Graph $G = (V, E)$ , seed set size $k$ , propagation probability $p$ , simulation rounds $R$
Output: Seed set $S$
Initialize $S = \emptyset$
for $i = 1$ to $k$ do
    for each $v \in V \setminus S$ do
         $s_v = 0$
    for $j = 1$ to $R$ do
        compute $G'$ by removing each edge of $G$ independently with probability $1 - p$
        compute $R_{G'}(S)$ , the set of vertices reachable from $S$ in $G'$
        compute $|R_{G'}(\{v\})|$ for all $v \in V$
        for each vertex $v \in V \setminus S$ do
            if $v \notin R_{G'}(S)$ then
                 $s_v = s_v + |R_{G'}(\{v\})|$
    for each $v \in V \setminus S$ do
         $s_v = s_v / R$
     $u = \arg\max_{v \in V \setminus S} \{s_v\}$
     $S = S \cup \{u\}$
return $S$
The algorithm runs in $O(kRm)$ time, achieving an $O(n)$ speedup over the standard greedy algorithm's $O(knRm)$ complexity.
Knowl 4 — NewGreedyWC Algorithm via Reachability Estimation
algorithm
In the weighted cascade (WC) model, each directed edge $\vec{uv}$ activates $v$ independently with probability $1/d_v$ , where $d_v$ is the degree of $v$ in $G$ . Sampled live-edge graphs $G'$ are directed, making all-pairs reachability computation non-trivial. NewGreedyWC collapses strongly connected components of $G'$ into a directed acyclic graph (DAG) $G'^*$ with vertex weights $w(v^*)$ equal to component sizes, then applies Cohen's randomized reachability size estimation algorithm with $T$ iterations.

In iteration $\ell$ , random variables $X_{v^*}^\ell \sim \text{Exp}(w(v^*))$ are assigned to vertices in $G'^*$ , and $Y_{v^*}^\ell = \min_{u^* \in R_{G'^*}(S^* \cup \{v^*\})} X_{u^*}^\ell$ is computed via reverse topological traversal. The unbiased estimator of reachable component weight $|R_{G'}(S \cup \{v\})|$ is $\hat{W}_v = (T - 1) / \sum_{\ell=1}^T Y_{v^*}^\ell$ .
Input: Graph $G = (V, E)$ , seed set size $k$ , simulation rounds $R$ , Cohen iterations $T$
Output: Seed set $S$
Initialize $S = \emptyset$
for $i = 1$ to $k$ do
    Initialize $s_v = 0$ for all $v \in V \setminus S$
    for $j = 1$ to $R$ do
        sample directed graph $G'$ by removing each directed edge $\vec{uv}$ with probability $1 - 1/d_v$
        compute DAG $G'^*$ of strongly connected components of $G'$ and weights $w(v^*)$ for all $v^* \in V^*$
        for $\ell = 1$ to $T$ do
            for each $v^* \in V^*$ do
                sample $X_{v^*}^\ell$ from exponential distribution with mean $1/w(v^*)$
            for each $v^* \in V^*$ do
                 $Y_{v^*}^\ell = \min_{u^* \in R_{G'^*}(S^* \cup \{v^*\})} X_{u^*}^\ell$
        for each $v \in V \setminus S$ do
             $s_v = s_v + (T - 1) / \sum_{\ell=1}^T Y_{v^*}^\ell$
    for each $v \in V \setminus S$ do
         $s_v = s_v / R$
     $u = \arg\max_{v \in V \setminus S} \{s_v\}$
     $S = S \cup \{u\}$
return $S$
The total time complexity is $O(kRTm)$ . A small iteration parameter (such as $T = 5$ ) suffices because the outer loop averages over $R = 20000$ random graphs, canceling individual estimate variance.
Knowl 5 — Mixed Greedy Seed Selection Strategy
model/method
The mixed greedy strategy (MixedGreedyIC for the independent cascade model and MixedGreedyWC for the weighted cascade model) combines global graph-traversal sharing with Cost-Effective Lazy Forward (CELF) optimization to minimize running time while maintaining the $(1 - 1/e)$ approximation guarantee:
1. In the first round ( $i = 1$ , where $S = \emptyset$ ), evaluating all $n$ candidate vertices individually under CELF requires $O(nRm)$ operations. Mixed greedy executes NewGreedyIC or NewGreedyWC in round 1, computing marginal spread estimates for all $n$ vertices simultaneously in $O(Rm)$ or $O(RTm)$ time.
2. In subsequent rounds ( $i = 2, \dots, k$ ), influence spread is submodular and individual cascade simulations explore only localized subgraphs. Mixed greedy uses CELF lazy forward evaluation, which re-evaluates only a small subset of top candidate nodes.
This hybrid eliminates the first-round bottleneck of CELF without incurring the repeated full-graph sampling costs of NewGreedy in rounds $2$ through $k$ .
Knowl 6 — SingleDiscount Heuristic for Influence Maximization
model/method
SingleDiscount is a model-agnostic degree-discount heuristic for influence maximization in an undirected social network graph $G = (V, E)$ . The algorithm selects seeds sequentially up to size $k$ . In each step, it chooses the unselected vertex with the highest degree. Once a vertex $u$ is added to the seed set $S$ , the effective degree of each of its unselected neighbors $v \in N(u) \setminus S$ is decremented by 1.

By subtracting 1 for each neighbor already selected as a seed, SingleDiscount removes the direct edge connecting $v$ to $S$ from $v$ 's degree calculation. This penalizes candidate nodes that are adjacent to existing seeds, reducing seed clustering and redundant influence spread without requiring cascade simulations or propagation probabilities.
Knowl 7 — Empirical Performance and Speedup of Degree Discount Heuristics
empirical result
Experiments on two academic collaboration networks—NetHEPT ( $n = 15,233, m = 58,891$ ) and NetPHY ( $n = 37,154, m = 231,584$ )—under the independent cascade model with $p = 0.01$ and seed size $k = 50$ demonstrate:
1. Influence spread: DegreeDiscountIC essentially matches CELFGreedy on NetHEPT (influence spread 136.4) and achieves within 3.4% of CELFGreedy on NetPHY (314.5 vs 325.7). SingleDiscount achieves spread within 3.6% (NetHEPT) and 8.6% (NetPHY) of CELFGreedy, eliminating roughly half the performance deficit of the pure Degree heuristic relative to Greedy.
2. Running time: DegreeDiscountIC executes in $\approx 3.9$ ms on NetHEPT and $\approx 9.5$ ms on NetPHY, running over six orders of magnitude ( $>10^6\times$ ) faster than CELFGreedy ( $2.91 \times 10^3$ s on NetHEPT, $2.56 \times 10^4$ s on NetPHY).
3. Traditional baseline heuristics perform significantly worse: Distance heuristic spread is 20.9% lower on NetHEPT and 46.3% lower on NetPHY while running in thousands of seconds; pure Degree spread is 8.7% lower on NetHEPT and 16.3% lower on NetPHY.
Knowl 8 — Running Time Improvement of Mixed Greedy Algorithms
empirical result
Evaluating seed selection running times for $k = 50$ seeds on NetHEPT and NetPHY demonstrates that mixed greedy algorithms outperform standard CELF optimization:
1. Independent cascade model ( $p = 0.01$ ): MixedGreedyIC reduces the running time of CELFGreedy by 27% on NetHEPT ( $2.12 \times 10^3$ s vs $2.91 \times 10^3$ s) and by 15% on NetPHY ( $2.18 \times 10^4$ s vs $2.56 \times 10^4$ s) while producing identical influence spread.
2. Weighted cascade model: MixedGreedyWC reduces CELFGreedy running time by 19.0% on NetHEPT ( $3.92 \times 10^3$ s vs $4.84 \times 10^3$ s) and by 34.4% on NetPHY ( $8.16 \times 10^3$ s vs $1.24 \times 10^4$ s).
3. Sensitivity to $p$ : In the IC model, as $p$ increases to $0.02$ and $0.05$ on NetHEPT, CELFGreedy running time escalates to $9.28 \times 10^3$ s and $1.11 \times 10^5$ s due to larger active cascades per lazy evaluation, whereas NewGreedyIC and MixedGreedyIC running times remain virtually constant at $\approx 3.0 \times 10^3$ s, providing more than an order of magnitude speedup.

Knowl 9 — Time Complexity Comparison of Influence Maximization Algorithms

theoretical result

For a graph $G = (V, E)$ with $n = |V|$ vertices and $m = |E|$ edges, selecting $k$ seed nodes with $R$ simulation rounds and $T$ Cohen reachability iterations yields the following asymptotic time complexities:

GeneralGreedy evaluates each of the $n$ candidate vertices with $R$ separate Monte-Carlo simulations of cost $O(m)$ . NewGreedyIC reduces this by pre-generating $R$ random graphs per round and computing reachability for all candidates simultaneously in $O(m)$ time per graph. DegreeDiscountIC eliminates stochastic simulations entirely, operating directly on graph degrees.

Knowl 10 — Cross-Model Robustness under the Linear Threshold Model
empirical result
When seed sets of size $k = 50$ generated by algorithms designed for IC and WC models are evaluated under the Linear Threshold (LT) model on NetHEPT and NetPHY:
1. MixedGreedyWC produces influence spread matching that of CELFGreedy run directly on the LT model on both collaboration graphs, confirming structural and dynamic similarities between weighted cascade and linear threshold propagation.
2. DegreeDiscountIC (parameterized with $p = 0.01$ ) remains highly effective under LT dynamics, achieving influence spread substantially superior to pure Degree, Distance, and Random baselines on both graphs, and exceeding the spread of MixedGreedyIC on NetPHY.
3. SingleDiscount also performs consistently across both networks under LT dynamics, demonstrating that degree discount heuristics provide robust seed selections across different cascade dynamics without requiring model-specific tuning.

Coverage note — None was omitted; all key algorithms, theoretical derivations, complexity results, and empirical evaluations across the independent cascade, weighted cascade, and linear threshold models are covered.

References

1.E. Cohen. Size-estimation framework with applications to transitive closure and reachability. J. Comput. Syst. Sci., 55(3):441–453, 1997.
2.D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. J. Symb. Comput., 9(3):251–280, 1990.
3.P. Domingos and M. Richardson. Mining the network value of customers. In Proceedings of the 7th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 57–66, 2001.
4.M. Granovetter. Threshold models of collective behavior. American J. of Sociology, 83(6):1420–1443, 1978.
5.D. Kempe, J. M. Kleinberg, and É. Tardos. Maximizing the spread of influence through a social network. In Proceedings of the 9th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 137–146, 2003.
6.M. Kimura and K. Saito. Tractable models for information diffusion in social networks. In Proceedings of the 10th European Conference on Principles and Practice of Knowledge Discovery in Databases, pages 259–271, 2006.
7.J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. S. Glance. Cost-effective outbreak detection in networks. In Proceedings of the 13th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 420–429, 2007.
8.M. Richardson and P. Domingos. Mining knowledge-sharing sites for viral marketing. In Proceedings of the 8th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 61–70, 2002.
9.T. C. Schelling. Micromotives and Macrobehavior. Norton, 1978.
10.S. Wasserman and K. Faust. Social Network Analysis: Methods and Applications. Cambridge University Press, 1994.

Citation

MLA

Chen, W., et al. “Efficient Influence Maximization in Social Networks”. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2009, pp. 199–208, https://doi.org/10.1145/1557019.1557047.

APA

Chen, W., Wang, Y., & Yang, S. (2009). Efficient influence maximization in social networks. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 199–208. https://doi.org/10.1145/1557019.1557047

Chicago

Chen, W., Y. Wang, and S. Yang. 2009. “Efficient Influence Maximization in Social Networks”. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 199–208. https://doi.org/10.1145/1557019.1557047.

Harvard

Chen, W., Wang, Y. and Yang, S. (2009) “Efficient influence maximization in social networks”, Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp. 199–208. Available at: https://doi.org/10.1145/1557019.1557047.

Vancouver

1. Chen W, Wang Y, Yang S (2009) Efficient influence maximization in social networks. In: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 199–208

BibTeX

@inproceedings{Chen_2009, series={KDD09}, title={Efficient influence maximization in social networks}, url={http://dx.doi.org/10.1145/1557019.1557047}, DOI={10.1145/1557019.1557047}, booktitle={Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining}, publisher={ACM}, author={Chen, Wei and Wang, Yajun and Yang, Siyu}, year={2009}, month=June, pages={199–208}, collection={KDD09} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Algorithm	Time Complexity
Algorithm 1: GeneralGreedy	$O(knRm)$
Algorithm 2: NewGreedyIC	$O(kRm)$
Algorithm 3: NewGreedyWC	$O(kRTm)$
Algorithm 4: DegreeDiscountIC	$O(k \log n + m)$

Efficient influence maximization in social networks

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Degree Discount Formula in Independent Cascade Model

Knowl 2 — DegreeDiscountIC Algorithm

Knowl 3 — NewGreedyIC Algorithm

Knowl 4 — NewGreedyWC Algorithm via Reachability Estimation

Knowl 5 — Mixed Greedy Seed Selection Strategy

Knowl 6 — SingleDiscount Heuristic for Influence Maximization

Knowl 7 — Empirical Performance and Speedup of Degree Discount Heuristics

Knowl 8 — Running Time Improvement of Mixed Greedy Algorithms

Knowl 9 — Time Complexity Comparison of Influence Maximization Algorithms

Knowl 10 — Cross-Model Robustness under the Linear Threshold Model

References

Citation

BibTeX

Access the Paper