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

I. PROBLEM STATEMENT

IV. DYNAG FOR DYNAMIC TOP-K IM

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 .

II. PREVIOUS METHODS FOR TOP-K IM

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:

V. EXPERIMENTS

Efficiency

Algorithm CELF [5]

3. Studies the contribution

4. For any and any ,

Linux server

Intel Core i7 3.2GHz

C/C++

: 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

( ) =

( )

=

( )= ( )=

=

( )

III. DATA ANALYSIS

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

stable.

RESEARCH POSTER PRESENTATION DESIGN 2012

www.PosterPresentations.com

REFERENCES

[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.

ACKNOWLEDGEMENT

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).

CONTACT

Dr. Hao WANG: [email protected] / [email protected]

Dr. Ryan Leong Hou U: [email protected]