Scalable influence maximization for prevalent viral marketing in large-scale social networks

Wei ChenChi WangYajun Wang

article2010KDD1,825 citations

Proposes a scalable influence maximization algorithm based on local arborescence structures that scales to million-node social networks while matching the influence spread of standard greedy approaches at orders-of-magnitude faster runtimes.

Listen

Online social networks offer powerful opportunities for word-of-mouth marketing, where selecting a small set of influential initial users (seeds) triggers broad information adoption. Maximizing this influence spread under stochastic propagation models is a critical operational problem. However, standard greedy solutions rely on costly simulations that do not scale to massive graphs, while simple heuristics often yield erratic or low-quality marketing reach.

The article establishes that computing exact influence spread under the independent cascade model is computationally intractable (#P-hard) and designs a fast, scalable heuristic algorithm called Prefix-excluding Maximum Influence Arborescence (PMIA). The goal was to prove the computational hardness of the original problem, develop an algorithm capable of scaling to networks with millions of edges, and maintain influence spread matching traditional greedy approaches.

To achieve this, the approach approximates propagation paths by restricting influence calculations to local directed tree structures (arborescences) around each node. It applies Dijkstra-based shortest-path calculations weighted by propagation probabilities and ignores paths falling below a tunable influence threshold. The team evaluated this framework using simulations across synthetic power-law graphs and several real-world networks—including collaboration networks (NetHEPT, NetPHY, DBLP), product co-purchasing data (Amazon), and review-platform trust networks (Epinions)—ranging from thousands to over two million edges.

The findings show that PMIA scales successfully to graphs with millions of nodes and edges, processing a two-million-edge graph in roughly three minutes, whereas traditional greedy and global shortest-path methods take hours or become completely intractable beyond a few hundred thousand edges. Across all test sets, PMIA achieves influence spread matching or coming within 4% of slow greedy benchmarks. In large graphs, it outperforms alternative scalable heuristics like PageRank and degree discount methods by 100% to 260% in influence spread. Additionally, the threshold parameter acts as an effective operational dial, exhibiting an optimal 'knee point' where practitioners obtain maximum influence quality before computational costs grow.

These results mean organizations can run large-scale viral marketing campaigns and seed selection without the prohibitive compute costs and multi-hour delays of simulation-based methods. PMIA removes the historic trade-off between execution speed and campaign effectiveness. Unlike simpler degree-based heuristics that perform inconsistently across different graph structures, PMIA provides predictable, top-tier performance across varied network topologies.

For practical deployment, organizations should adopt PMIA as a generic engine for seed selection in large-scale viral campaigns. Teams should calibrate the influence threshold by sampling small node subsets to locate the performance knee point, balancing runtime against reach. Furthermore, because PMIA relies on local arborescence structures rather than full-graph evaluations, engineering teams can readily partition graph data across parallel computing infrastructure. Future efforts should also integrate automated social influence mining to estimate edge propagation probabilities directly from live platform interaction data.

The primary limitation of this work is its reliance on synthetic edge propagation models (such as weighted cascade and trivalency settings) or static interaction snapshots rather than live behavioral experiments. While confidence is very high regarding PMIA's algorithmic scalability and theoretical approximation bounds within cascade models, practitioners should validate empirical conversion rates when applying these seed sets to real-world consumer behavior.

Microsoft University of Illinois Urbana-Champaign extensive simulations online social networks viral marketing scalable influence maximization viral marketing large-scale social networks

Chen et al (2010).pdf

Paper: Maximizing the spread of influence through a social network, David Kempe et al. (2003). This seminal paper formally defines the influence maximization problem under diffusion cascade models and establishes the submodular greedy approximation framework that the source builds on and seeks to scale.
Paper: Efficient influence maximization in social networks, Wei Chen et al. (2009). This predecessor work develops the degree discount heuristic and accelerated greedy methods that directly serve as foundational baselines and motivation for the source's scalable heuristics.
Paper: Cost-effective outbreak detection in networks, J. Leskovec et al. (2007). This paper introduces the Cost-Effective Lazy Forward (CELF) optimization for submodular maximization in networks, establishing the primary benchmark for fast greedy cascade optimization.
Paper: Mining the network value of customers, Pedro M. Domingos et al. (2001). This foundational paper first introduced the concept of customer network value and formulated viral marketing as an optimization problem over social networks.
Paper: Mining knowledge-sharing sites for viral marketing, Matthew Richardson et al. (2002). This work establishes scalable probabilistic models for measuring network effects and optimizing viral marketing campaigns across large online networks.

Paper: Everyone's an influencer: quantifying influence on twitter, Eytan Bakshy et al. (2011). This empirical study investigates whether influencers identified by network diffusion principles reliably produce large information cascades in massive real-world social media platforms like Twitter.
Paper: Epidemic processes in complex networks, Romualdo Pastor-Satorras et al. (2015). This comprehensive review synthesizes mathematical theories of epidemic and information diffusion across complex, large-scale network structures.

Cover for Scalable influence maximization for prevalent viral marketing in large-scale social networks

Abstract

Influence maximization, defined by Kempe, Kleinberg, and Tardos (2003), is the problem of finding a small set of seed nodes in a social network that maximizes the spread of influence under certain influence cascade models. The scalability of influence maximization is a key factor for enabling prevalent viral marketing in large-scale online social networks. Prior solutions, such as the greedy algorithm of Kempe et al. (2003) and its improvements are slow and not scalable, while other heuristic algorithms do not provide consistently good performance on influence spreads. In this paper, we design a new heuristic algorithm that is easily scalable to millions of nodes and edges in our experiments. Our algorithm has a simple tunable parameter for users to control the balance between the running time and the influence spread of the algorithm. Our results from extensive simulations on several real-world and synthetic networks demonstrate that our algorithm is currently the best scalable solution to the influence maximization problem: (a) our algorithm scales beyond million-sized graphs where the greedy algorithm becomes infeasible, and (b) in all size ranges, our algorithm performs consistently well in influence spread — it is always among the best algorithms, and in most cases it significantly outperforms all other scalable heuristics to as much as 100%–260% increase in influence spread.

Topics

extensive simulations online social networks viral marketing network architecture

Keywords

scalable influence maximization viral marketing large-scale social networks incremental influence spread social influence mining influence propagation influence cascade models information diffusion distance centrality greedy algorithms

1 Introduction
1.1 Our contribution
1.2 Related work
2 IC model and greedy algorithm
3 MIA model and its algorithm
3.1 Basic MIA model and greedy algorithm
3.2 More efficient greedy algorithm
3.3 Prefix excluding MIA model
4 Experiment
4.1 Experiment setup
4.2 Experiment results
5 Future Work
References
Appendix
A Additional experiment results

Knowls

Knowl 1 — #P-Hardness of Exact Influence Spread Computation in the Independent Cascade Model
theoretical result
In a directed graph $G = (V, E)$ with edge propagation probabilities $pp: E \to [0, 1]$ under the Independent Cascade (IC) model, computing the exact influence spread $\sigma_I(S)$ (the expected number of activated nodes) given an initial seed set $S \subseteq V$ is #P-hard.

This result is established by a polynomial-time reduction from the #P-complete problem of counting the number of $s$ - $t$ connected subgraphs in a directed graph: computing $s$ - $t$ connectivity in graph $G$ with edge activation probabilities $1/2$ reduces to computing the difference between the influence spread of seed set $\{s\}$ in $G$ and the influence spread in an augmented graph $G'$ where a new node $t'$ is added with a single directed edge $(t, t')$ of propagation probability $1$ .
Knowl 2 — Maximum Influence Arborescence (MIA) Model
model/method
Let $G = (V, E)$ be a directed social network graph where each edge $(u, v) \in E$ has propagation probability $pp(u, v) \in [0, 1]$ . For a path $P = \langle u = p_1, p_2, \dots, p_m = v \rangle$ , its propagation probability is $pp(P) = \prod_{i=1}^{m-1} pp(p_i, p_{i+1})$ . Assigning each edge $(u, v)$ a distance weight of $-\log pp(u, v)$ , the Maximum Influence Path (MIP) from $u$ to $v$ corresponds to the shortest path in $G$ :

$MIP_G(u, v) = \arg\max_{P \in \mathcal{P}(G, u, v)} pp(P)$

Given an influence threshold $\theta \in (0, 1]$ , the Maximum Influence In-Arborescence ( $MIIA$ ) and Out-Arborescence ( $MIOA$ ) of a node $v \in V$ are defined by pruning MIPs with probability below $\theta$ :

$MIIA(v, \theta) = \bigcup_{u \in V,\, pp(MIP_G(u, v)) \ge \theta} MIP_G(u, v)$

$MIOA(v, \theta) = \bigcup_{u \in V,\, pp(MIP_G(v, u)) \ge \theta} MIP_G(v, u)$

Under the MIA model, influence from seed set $S \subseteq V$ to each target node $v$ is assumed to propagate exclusively within $MIIA(v, \theta)$ . The total expected influence spread $\sigma_M(S)$ is:

$\sigma_M(S) = \sum_{v \in V} ap(v, S, MIIA(v, \theta))$

where the activation probability $ap(u, S, MIIA(v, \theta))$ of any node $u$ in $MIIA(v, \theta)$ is computed recursively without dependency cycles as:

$ap(u) = \begin{cases} 1 & \text{if } u \in S \\ 0 & \text{if } u \notin S \text{ and } N^{in}(u) = \emptyset \\ 1 - \prod_{w \in N^{in}(u)} (1 - ap(w) \cdot pp(w, u)) & \text{otherwise} \end{cases}$

where $N^{in}(u)$ denotes the set of in-neighbors of $u$ in $MIIA(v, \theta)$ .
Knowl 3 — Submodularity and Approximation Guarantee for the Basic MIA Model
theoretical result
In the basic Maximum Influence Arborescence (MIA) model, the influence spread function $\sigma_M(S) = \sum_{v \in V} ap(v, S, MIIA(v, \theta))$ is non-negative, monotone ( $\sigma_M(S) \le \sigma_M(T)$ for all $S \subseteq T$ ), and submodular ( $\sigma_M(S \cup \{v\}) - \sigma_M(S) \ge \sigma_M(T \cup \{v\}) - \sigma_M(T)$ for all $S \subseteq T \subseteq V$ and $v \in V$ ), with $\sigma_M(\emptyset) = 0$ .

As a consequence:
1. Finding a seed set $S \subseteq V$ of size $k$ that maximizes $\sigma_M(S)$ is NP-hard, and it is NP-hard to approximate within a factor of $(1 - 1/e + \epsilon)$ for any $\epsilon > 0$ .
2. The greedy approximation algorithm—which iteratively selects the seed $u = \arg\max_{w \in V \setminus S} (\sigma_M(S \cup \{w\}) - \sigma_M(S))$ until $k$ seeds are chosen—guarantees a $(1 - 1/e)$ -approximation to the optimal seed set.
Knowl 4 — Influence Linearity and Fast Incremental Influence Update on In-Arborescences
theoretical result
For any node $u$ in an in-arborescence $MIIA(v, \theta)$ , treating the activation probabilities $ap(u)$ and $ap(v)$ as variables while holding the activation probabilities of all other nodes $w \in MIIA(v, \theta) \setminus \{u, v\}$ constant yields a strictly linear relationship:

$ap(v) = \alpha(v, u) \cdot ap(u) + \beta(v, u)$

where $\alpha(v, u)$ and $\beta(v, u)$ are constants independent of $ap(u)$ . The linear coefficient $\alpha(v, u)$ is computed recursively by traversing $MIIA(v, \theta)$ from the root $v$ downward to the leaves:
- $\alpha(v, v) = 1$
- For $u \neq v$ , let $w$ be the unique out-neighbor of $u$ in $MIIA(v, \theta)$ . If $w \in S$ , then $\alpha(v, u) = 0$ (influence from $u$ to $v$ is blocked by seed $w$ ). Otherwise:
$\alpha(v, u) = \alpha(v, w) \cdot pp(u, w) \cdot \prod_{u' \in N^{in}(w) \setminus \{u\}} (1 - ap(u') \cdot pp(u', w))$

When a node $u \in MIIA(v, \theta)$ is selected as a seed, its activation probability increases from $ap(u)$ to $1$ . Due to linearity, its marginal contribution to the activation probability of $v$ is exactly $\alpha(v, u) \cdot (1 - ap(u))$ . This enables evaluating the marginal influence gains of all nodes in an arborescence of size $t$ in $O(t)$ time using two tree traversals, reducing the per-seed candidate evaluation cost from $O(t^2)$ to $O(t)$ .
Knowl 5 — Prefix Excluding MIA (PMIA) Model and Sequence Submodularity
model/method
The Prefix Excluding MIA (PMIA) model extends the MIA model to prevent earlier seeds from blocking the influence propagation of later seeds. Given an ordered sequence of seeds $S = \langle s_1, s_2, \dots, s_m \rangle$ , let $S_i = \langle s_1, \dots, s_{i-1} \rangle$ (with $S_1 = \emptyset$ ), and let $G(S')$ denote the subgraph of $G$ induced by $V \setminus S'$ .
1. Ineffective Seeds: A seed $s_i \in S$ is ineffective for node $v \in V \setminus S$ if its path to $v$ is intercepted by a subsequent seed $s_j$ ( $j > i$ ): $IS(v, S) = \{s_i \in S \mid \exists j > i \text{ s.t. } s_j \in MIP_{G(S_i)}(s_i, v)\}$
2. PMIA In- and Out-Arborescences: For $v \notin S$ : $PMIIA(v, \theta, S) = \left(\bigcup_{s_i \in S \setminus IS(v, S),\, pp(MIP_{G(S_i)}(s_i, v)) \ge \theta} MIP_{G(S_i)}(s_i, v)\right) \cup \left(\bigcup_{u \in V \setminus S,\, pp(MIP_{G(S)}(u, v)) \ge \theta} MIP_{G(S)}(u, v)\right)$ $PMIOA(v, \theta, S) = \bigcup_{u \in V \setminus S,\, pp(MIP_{G(S)}(v, u)) \ge \theta} MIP_{G(S)}(v, u)$
3. Sequence Submodularity: The influence spread $\sigma_P(S) = \sum_{v \in V} ap(v, S, PMIIA(v, \theta, S))$ is sequence submodular ( $f(S_1 \oplus S_2 \oplus \{t\}) - f(S_1 \oplus S_2) \le f(S_1 \oplus \{t\}) - f(S_1)$ ) and prefix monotone ( $f(S_1) \le f(S_2 \oplus S_1)$ ), with $\sigma_P(\emptyset) = 0$ . Consequently, iteratively appending $s_i = \arg\max_{s \in V} \sigma_P(S_{i-1} \oplus \langle s \rangle)$ guarantees a $(1 - 1/e)$ -approximation relative to the optimal seed sequence of length $k$ .
Knowl 6 — The PMIA Greedy Algorithm and Computational Complexity
algorithm
The PMIA algorithm selects $k$ seed nodes to maximize influence spread by maintaining local maximum influence arborescences and incremental influence spreads $IncInf(v)$ for all $v \in V$ in a max-heap.
Input: Directed graph $G = (V, E)$ , seed budget $k$ , influence threshold $\theta$
Output: Seed sequence $S$ of size $k$
Initialize $S = \emptyset$
for each node $v \in V$ do
     $IncInf(v) = 0$
for each node $v \in V$ do
    Compute $PMIIA(v, \theta, S)$ and $PMIOA(v, \theta, S)$
    Set $ap(u, S, PMIIA(v, \theta, S)) = 0$ for all $u \in PMIIA(v, \theta, S)$
    Compute $\alpha(v, u)$ for all $u \in PMIIA(v, \theta, S)$
    for each node $u \in PMIIA(v, \theta, S)$ do
         $IncInf(u) = IncInf(u) + \alpha(v, u) \cdot (1 - ap(u, S, PMIIA(v, \theta, S)))$
for $i = 1$ to $k$ do
     $u = \arg\max_{v \in V \setminus S} \{IncInf(v)\}$
    Compute $PMIOA(u, \theta, S)$
    for each $v \in PMIOA(u, \theta, S) \setminus S$ do
        for each $w \in PMIIA(v, \theta, S) \setminus S$ do
             $IncInf(w) = IncInf(w) - \alpha(v, w) \cdot (1 - ap(w, S, PMIIA(v, \theta, S)))$
     $S = S \cup \{u\}$
    for each $v \in PMIOA(u, \theta, S \setminus \{u\}) \setminus \{u\}$ do
        Compute $PMIIA(v, \theta, S)$
        Compute $ap(w, S, PMIIA(v, \theta, S))$ for all $w \in PMIIA(v, \theta, S)$
        Compute $\alpha(v, w)$ for all $w \in PMIIA(v, \theta, S)$
        for each $w \in PMIIA(v, \theta, S) \setminus S$ do
             $IncInf(w) = IncInf(w) + \alpha(v, w) \cdot (1 - ap(w, S, PMIIA(v, \theta, S)))$
return $S$
Let $n_{i\theta} = \max_{v} |PMIIA(v, \theta, S)|$ , $n_{o\theta} = \max_{v} |PMIOA(v, \theta, S)|$ , and let $t_{i\theta}$ be the maximum time to compute $PMIIA(v, \theta, S)$ using Dijkstra's shortest-path algorithm. The time complexity is $O(n t_{i\theta} + k n_{o\theta} n_{i\theta} \log n)$ , and the space complexity is $O(n (n_{i\theta} + n_{o\theta}))$ . Without the linear relationship optimization, the time complexity would be $O(n t_{i\theta} + k n_{o\theta} n_{i\theta} (n_{i\theta} + \log n))$ .
Knowl 7 — Method for Tuning the Influence Threshold Parameter $\theta$
model/method
The threshold parameter $\theta \in (0, 1]$ controls the tradeoff between execution time and influence spread quality in MIA/PMIA algorithms:
1. Scaling Behavior: The average arborescence size grows as $O(\sqrt{1/\theta})$ . Because the main-loop update complexity depends on $n_{o\theta} n_{i\theta}$ , total runtime scales approximately linearly with $1/\theta$ .
2. Knee-Point Property: The influence spread curve as a function of $1/\theta$ exhibits a clear knee point. Beyond this point, further decreases in $\theta$ (larger $1/\theta$ ) cause arborescence sizes and runtime to grow without yielding meaningful improvements in influence spread.
3. Tuning Procedure: For a given target network:
  - Randomly sample a small subset of nodes in the graph.
  - Compute average arborescence sizes across varying values of $1/\theta$ .
  - Identify the knee point where the rate of growth of the average arborescence size begins to slow down.
  - Set $\theta$ to the value at that knee point for executing the PMIA algorithm (e.g., $\theta = 1/320$ for NetHEPT under the WC model, $\theta = 1/160$ for Epinions under the WC model, and $\theta = 1/20$ for NetHEPT under the TRIVALENCY model).
Knowl 8 — Empirical Scalability and Runtime Performance of PMIA
empirical result
Empirical evaluations on synthetic power-law networks (generated with power-law exponent $2.16$ , ranging from $2\text{K}$ to $256\text{K}$ nodes) and real-world graphs demonstrate the scalability of PMIA:
1. Scalability Threshold: Simulation-based Greedy (with lazy-forward optimization) and shortest-path heuristic SP1M require hours on networks with $\approx 400\text{K}$ edges and become computationally infeasible on graphs with $\ge 500\text{K}$ edges.
2. Running Time Comparisons (selecting $k = 50$ $k = 50$ seeds):
  - On NetHEPT ( $15\text{K}$ nodes, $31\text{K}$ edges, Weighted Cascade model): Greedy requires $1.3\text{ hours}$ , SP1M requires $22\text{ seconds}$ , PageRank requires $0.5\text{ seconds}$ , and PMIA finishes in $1.0\text{ second}$ (over $4600\times$ faster than Greedy).
  - On Epinions ( $76\text{K}$ nodes, $509\text{K}$ edges, Weighted Cascade model): SP1M takes $2.1\text{ hours}$ , whereas PMIA takes $10\text{ seconds}$ ( $>750\times$ speedup).
  - On Amazon ( $262\text{K}$ nodes, $1.2\text{M}$ edges, Weighted Cascade model): SP1M takes $30\text{ hours}$ , while PMIA takes $10\text{ seconds}$ .
  - On DBLP ( $655\text{K}$ nodes, $2.0\text{M}$ edges, Weighted Cascade model): PMIA terminates in $3\text{ minutes}$ ( $172\text{ seconds}$ ), easily scaling to million-edge graphs where Greedy and SP1M cannot run.
Knowl 9 — Empirical Influence Spread Quality of PMIA Across Propagation Models
empirical result
Influence spread evaluations using 20,000 Monte Carlo simulations per seed set across $k = 1$ to $50$ seeds demonstrate:
1. Parity with Simulation Greedy: On graphs where Greedy is feasible (NetHEPT), PMIA matches the influence spread of Greedy under the Weighted Cascade (WC) model and achieves within $3.8\%$ of Greedy under the TRIVALENCY model.
2. Comparison with Fast Heuristics: Scalable heuristics such as DegreeDiscountIC and PageRank show volatile performance across different network structures. PMIA consistently outperforms them:
  - On Epinions (WC model), PMIA achieves $96\%$ and $115\%$ higher influence spread than DegreeDiscountIC and PageRank, respectively.
  - On Amazon (WC model), PMIA outperforms PageRank by $99\%$ and DegreeDiscountIC by $266\%$ .
  - On Amazon (TRIVALENCY model), PMIA outperforms SP1M by $14.1\%$ , PageRank by $23.9\%$ , and DegreeDiscountIC by $41.7\%$ .
3. Stability Across Models: PMIA maintains top-tier influence spread consistently across WC, TRIVALENCY, and Topical Affinity Propagation (TAP) models, whereas single-hop or degree-based heuristics only perform well under specialized conditions (e.g., WeightedDegree on TAP models where diffusion is strictly localized).

Knowl 10 — Benchmark Network Datasets and Propagation Probability Models

experimental setup

The empirical evaluation uses six real-world networks representing diverse graph topologies:

Dataset	NetHEPT	DBLP	Epinions	Amazon	NetPHY	DM
Nodes	15K	655K	76K	262K	37K	679
Edges	31K	2.0M	509K	1.2M	174K	1,687
Average Degree	4.12	6.1	13.4	9.4	12.5	4.97
Maximal Degree	64	588	3,079	425	286	63
Connected Components	1,781	73K	11	1	3,883	1
Largest Component Size	6,794	517K	76K	262K	19,873	679
Average Component Size	8.6	9.0	6.9K	262K	9.57	679

Nonuniform edge propagation probabilities $pp(u, v)$ are generated using three models:

Weighted Cascade (WC): $pp(u, v) = 1 / d_{in}(v)$ , where $d_{in}(v)$ is the in-degree of node $v$ .
TRIVALENCY: $pp(u, v)$ is selected uniformly at random from $\{0.1, 0.01, 0.001\}$ (or $\{0.2, 0.04, 0.008\}$ for high-influence test variants).
Topical Affinity Propagation (TAP): $pp(u, v)$ is derived from topical affinities using topic distributions and structural connections.

Coverage note — None was omitted; all key theoretical proofs (whose standalone results are included as knowls), baseline heuristics (Degree, Random), and future research speculations were subsumed or excluded according to the extraction criteria.

References

1.W. Aiello, F. R. K. Chung, and L. Lu. A random graph model for massive graphs. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, pages 171–180, 2000.
2.S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine. Computer Networks, 30(1-7):107–117, 1998.
3.W. Chen, Y. Wang, and S. Yang. Efficient influence maximization in social networks. In Proceedings of the 15th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2009.
4.L. Cowen, A. Brady, and P. Schmid. DIGG: DynamIc Graph Generator. http://digg.cs.tufts.edu.
5.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.
6.U. Feige. A threshold of $\ln n$ for approximating set cover. Journal of the ACM, 45(4):634–652, 1998.
7.L. Freeman. Centrality in social networks: conceptual clarification. Social Networks, 1:215–239, 1979.
8.D. Gruhl, R. V. Guha, D. Liben-Nowell, and A. Tomkins. Information diffusion through blogspace. In Proceedings of the 13th international conference on World Wide Web, pages 491–501, 2004.
9.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.
10.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.
11.J. Leskovec. Amazon product co-purchasing network, march 02 2003. http://snap.stanford.edu/data/amazon0302.html.
12.J. Leskovec. Epinions social network. http://snap.stanford.edu/data/soc-Epinions1.html.
13.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.
14.I. R. Misner. The World's best known marketing secret: Building your business with word-of-mouth marketing. Bard Press, 2nd edition, 1999.
15.J. Nail. The consumer advertising backlash, May 2004. Forrester Research and Intelliseek Market Research Report.
16.G. Nemhauser, L. Wolsey, and M. Fisher. An analysis of the approximations for maximizing submodular set functions. Mathematical Programming, 14:265–294, 1978.
17.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.
18.M. Streeter and D. Golovin. An online algorithm for maximizing submodular functions. Technical Report Technical Report CMU-CS-07-171, Carnegie Mellon University, 2007.
19.J. Tang, J. Sun, C. Wang, and Z. Yang. Social influence analysis in large-scale networks. In Proceedings of the 15th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2009.
20.L. G. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3):410–421, 1979.
21.V. V. Vazirani. Approximation Algorithms. Springer, 2004.

Citation

MLA

Chen, W., et al. “Scalable Influence Maximization for Prevalent Viral Marketing in Large-scale Social Networks”. Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2010, pp. 1029–38, https://doi.org/10.1145/1835804.1835934.

APA

Chen, W., Wang, C., & Wang, Y. (2010). Scalable influence maximization for prevalent viral marketing in large-scale social networks. Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1029–1038. https://doi.org/10.1145/1835804.1835934

Chicago

Chen, W., C. Wang, and Y. Wang. 2010. “Scalable Influence Maximization for Prevalent Viral Marketing in Large-scale Social Networks”. Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1029–38. https://doi.org/10.1145/1835804.1835934.

Harvard

Chen, W., Wang, C. and Wang, Y. (2010) “Scalable influence maximization for prevalent viral marketing in large-scale social networks”, Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp. 1029–1038. Available at: https://doi.org/10.1145/1835804.1835934.

Vancouver

1. Chen W, Wang C, Wang Y (2010) Scalable influence maximization for prevalent viral marketing in large-scale social networks. In: Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 1029–1038

BibTeX

@inproceedings{Chen_2010, series={KDD ’10}, title={Scalable influence maximization for prevalent viral marketing in large-scale social networks}, url={http://dx.doi.org/10.1145/1835804.1835934}, DOI={10.1145/1835804.1835934}, booktitle={Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining}, publisher={ACM}, author={Chen, Wei and Wang, Chi and Wang, Yajun}, year={2010}, month=July, pages={1029–1038}, collection={KDD ’10} }

Metadata:Crossref

Access the Paper

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

Open PDF

Scalable influence maximization for prevalent viral marketing in large-scale social networks

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — #P-Hardness of Exact Influence Spread Computation in the Independent Cascade Model

Knowl 2 — Maximum Influence Arborescence (MIA) Model

Knowl 3 — Submodularity and Approximation Guarantee for the Basic MIA Model

Knowl 4 — Influence Linearity and Fast Incremental Influence Update on In-Arborescences

Knowl 5 — Prefix Excluding MIA (PMIA) Model and Sequence Submodularity

Knowl 6 — The PMIA Greedy Algorithm and Computational Complexity

Knowl 7 — Method for Tuning the Influence Threshold Parameter $\theta$

Knowl 8 — Empirical Scalability and Runtime Performance of PMIA

Knowl 9 — Empirical Influence Spread Quality of PMIA Across Propagation Models

Knowl 10 — Benchmark Network Datasets and Propagation Probability Models

References

Citation

BibTeX

Access the Paper