On Dynamic Top-k Influence Maximization Hao Wang1, Nana

On Dynamic Top-k Influence Maximization Hao Wang1, Nana

On Dynamic Top-k Influence Maximization
Hao Wang1, Nana Pan2, Leong Hou U2, Bohan Zhan2, Zhiguo Gong2
1. State Key Laboratory for Novel Software Technology, Nanjing University
2. Department of Computer and Information Science, University of Macau



Background / Motivation
Finding those people who are the most influential in a social network is important in viral
marketing as it helps companies to identify proper users for promoting their products
and services.
Independent Cascade (IC) Model of Information Diffusion

Key Idea
1. Verify the validity of previous top-k influential vertices. Once the top- vertex in is no
longer the top- in , recompute .
2. Two-phase verification, handling strengthened edges and weakened edges separately (
Verifying under Edge-strengthening ()
Delta random subgraph
1 probabilistic backward traversal to find

1 probabilistic forward traversal to find
Lemma 1. If then ; if then does NOT contribute
to of any .
Based on Lemma 1 we estimate and .

Given a directed weighted graph , the influence of a seed is
Top-k Influence Maximization Problem (previously studied [1, 4, 5])
Given a directed weighted graph , find a set of k vertices, , such that for any size-k
subset , .
Dynamic Top-k Influence Maximization Problem (our focus)
Assume that over time the graph evolves to . Given the top-k vertices in , , find the top-k
vertices in .

NP-hardness of Top-k Influence Maximization
Kempe et al. proved that (i) the problem of top-k influence maximization is NP-hard, and
(ii) the set function is submodular [4].

Verifying under Edge-weakening ( )
values computed in the last verification step are natural upper bounds of , thus we
employ a CELF-like procedure to find based on the upper bounds.
Verifying () under Edge-strengthening ()
We investigate the contribution
Lemma 2. .
Verifying () under Edge-weakening ( )
We investigate the contribution and the delta influence .
Lemma 3. .

for do
for do

Algorithm Greedy [4]
1. Generates a chain of
2. Approximation ratio:


Algorithm CELF [5]
3. Studies the contribution
4. For any and any ,

Linux server
Intel Core i7 3.2GHz

: a heap with values for all
for do
while not evaluated

Algorithm MixedGreedy [1]
Improves the 1st iteration of CELF by
using Cohens estimation [3]
1. Generates random subgraphs
2. In each subgraph, for each vertex
estimates its reachability
3. Invokes CELF

Computational cost of MixedGreedy and DynaG on Brightkite (Days 401-450 & Days 601-650)

Sensitivity w.r.t. the graph update ratios

Dataset: NetPHY [1]
: percentage of strengthened edges
: percentage of weakened edges

Principle of Cohens Estimation [3]

( )

{ | }

Intuition If has a large reachable area, then with
high probability that is relatively small.

MixedGreedy Estimation
1. In a random subgraph, perform Cohens estimation times to get for all
2. Average over random subgraphs
( ) =

( )


( )= ( )=


( )

Key Observations on Network Dynamics (from Brightkite & Gowalla [2])
1. Within a short period of time, the graph update ratio (i.e., the percentage of updated
edges among all edges) is not high;
2. The set of top influential vertices is relatively stable;
3. Even when the set of top influential vertices changes, the change is minor (e.g.,
position switching between the -th and -th vertices);
4. Even when the set of top influential vertices changes, the influence value remains



[1] Y.-C. Chen, W.-C. Peng, and S.-Y. Lee. Efficient algorithms for influence maximization in
social networks. KAIS, 33(3):577601, 2012.
[2] E. Cho, S. A. Myers, and J. Leskovec. Friendship and mobility: user movement in locationbased social networks. In KDD, 2011.
[3] E. Cohen. Size-estimation framework with applications to transitive closure and reachability.
JCSS, 55(3):441453, 1997.
[4] D. Kempe, J. M. Kleinberg, and . Tardos. Maximizing the spread of influence through a
social network. In KDD, 2003.
[5] J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. M. VanBriesen, and N. S. Glance. Costeffective outbreak detection in networks. In KDD, 2007.

The authors would like to acknowledge the support from the National Natural Science
Foundation of China (grant 61432008), and the support from the Research Committee of
University of Macau (grant MYRG109(Y1-L3)-FST12-ULH and MYRG2014-00106-FST).

Dr. Hao WANG: [email protected] / [email protected]
Dr. Ryan Leong Hou U: [email protected]

Recently Viewed Presentations

  • LaTe middle Ages - Craig's E-portfolio

    LaTe middle Ages - Craig's E-portfolio

    LaTe middle Ages. A time for some horrible history. Middle Ages Events. Bubonic Plague. Little Ice Age. The Papal Schism. The Challenge of the Church. 100 years war. The Black Death (Same thing) ... Edgar Allen Poe's short story about...
  • Title Placed Here - Be Leaderly

    Title Placed Here - Be Leaderly

    — Julie Muller Neff, EVP, SMACNA Western Washington "Four U.S.-based and global studies clearly show that sponsorship — not mentorship — is how power is transferred in the workplace." Why You Need A Sponsor — Not A Mentor — To...
  • Division of Strategic Planning

    Division of Strategic Planning

    Energy Division Organization April 2019 Energy Efficiency Branch Functions Energy Efficiency Branch AB 793 - Home Energy Management Marketing, Education and Outreach Financing Programs Workforce, Education and Training Experimental Design/ Randomized Control Trials HOPPS - Oversight Market Studies Zero Net...
  • The Odyssey, Books 1-4, 6, 8, 14

    The Odyssey, Books 1-4, 6, 8, 14

    Nausikaa says goodbye to Odysseus - he replies gently (8.457-468). What song does Odysseus ask Demodocus to sing? How does he react when he hears the song? Alkinoos asks Odysseus his identity and story (8.535-586). Books 9-12 In these books...
  • A Painter at Work, . 1st century BCE-1st century CE. 17 7/8 ...

    A Painter at Work, . 1st century BCE-1st century CE. 17 7/8 ...

    Diocletian's political restructuring is paralleled by a radically new, hard style of geometric abstraction, esp notable in portraits of the tetrarchs. This portrait depicts a tetrarch with startlingly alert, searing eyes. This piece is the antithesis of the suave Classicism...
  • From Classical to Contemporary

    From Classical to Contemporary

    Literary mash-ups: Seth Grahame-Smith's Pride and Prejudice and Zombies (2009); Ryan C. Thomas' The Undead World of Oz (2009); Nickolas Cook's Alice in Zombieland (2011), Gena Showalter's Alice in Zombieland (2012) Dramedy as hybrid form Characters, theme, genre, mode of...
  • Présentation PowerPoint

    Présentation PowerPoint

    Simple, Double, Quadruple (and so does the cost..) PATTERNING. 6-Transistor implementation do not work correctly in nano-CMOS. XOR GATE. 6T - Bug ! ?? ?=1, ???=?, ???? ???=? ...
  • Jesus Christ is Central to All Human History - ericdrichards.com

    Jesus Christ is Central to All Human History - ericdrichards.com

    Moses 4:3-4. Fallen Spirits "Every person who desires and strives to be a Saint is closely watched by fallen spirits that came here when Lucifer fell, and by the spirits of wicked persons who have been here in tabernacles and...