Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

8-2017

Abstract

Influence maximization (IM), which selects a set of k users(called seeds) to maximize the influence spread over a social network, is a fundamental problem in a wide range of applications such as viral marketing and network monitoring.Existing IM solutions fail to consider the highly dynamic nature of social influence, which results in either poor seed qualities or long processing time when the network evolves.To address this problem, we define a novel IM query named Stream Influence Maximization (SIM) on social streams.Technically, SIM adopts the sliding window model and maintains a set of k seeds with the largest influence value over the most recent social actions. Next, we propose the Influential Checkpoints (IC) framework to facilitate continuous SIM query processing. The IC framework creates a checkpoint for each window shift and ensures an ε-approximate solution.To improve its efficiency, we further devise a Sparse Influential Checkpoints (SIC) framework which selectively keeps O(log Nβ) checkpoints for a sliding window of size N and maintains an ε(1−β)2-approximate solution. Experimental results on both real-world and synthetic datasets confirm the effectiveness and efficiency of our proposed frameworks against the state-of-the-art IM approaches.

Discipline

Databases and Information Systems | Social Media

Research Areas

Data Science and Engineering

Publication

Proceedings of the VLDB Endowment: 43rd International Conference on Very Large Data Bases, Munich, Germany, 2017 August 28 - September 1

Volume

10

First Page

805

Last Page

816

Identifier

10.14778/3067421.3067429

Publisher

VLDB Endowment

City or Country

Stanford, CA

Additional URL

https://www.vldb.org/pvldb/vol10/p805-wang.pdf

Download

Share

COinS