Publication Type

Journal Article

Version

publishedVersion

Publication Date

4-2018

Abstract

Influence maximization (IM), which selects a set of k seed users (a.k.a., a seed set) to maximize the influence spread over a social network, is a fundamental problem in a wide range of applications. However, most existing IM algorithms are static and location-unaware. They fail to provide high-quality seed sets efficiently when the social network evolves rapidly and IM queries are location-aware. In this article, we first define two IM queries, namely Stream Influence Maximization (SIM) and Location-aware SIM (LSIM), to track influential users over social streams. Technically, SIM adopts the sliding window model and maintains a seed set with the maximum influence value collectively over the most recent social actions. LSIM further considers social actions are associated with geo-tags and identifies a seed set that maximizes the influence value in a query region over a location-aware social stream. Then, we propose the Sparse Influential Checkpoints (SIC) framework for efficient SIM query processing. SIC maintains a sequence of influential checkpoints over the sliding window and each checkpoint maintains a partial solution for SIM in an append-only substream of social actions. Theoretically, SIC keeps a logarithmic number of checkpoints w.r.t. the size of the sliding window and always returns an approximate solution from one of the checkpoint for the SIM query at any time. Furthermore, we propose the Location-based SIC (LSIC) framework and its improved version LSIC+, both of which process LSIM queries by integrating the SIC framework with a Quadtree spatial index. LSIC can provide approximate solutions for both ad hoc and continuous LSIM queries in real time, while LSIC+ further improves the solution quality of LSIC. Experimental results on real-world datasets demonstrate the effectiveness and efficiency of the proposed frameworks against the state-of-the-art IM algorithms.

Keywords

Data stream, Influence maximization, Region query, Social network, Spatial index, Submodular optimization

Discipline

Databases and Information Systems

Research Areas

Data Science and Engineering

Publication

ACM Transactions on Information Systems

Volume

36

Issue

4

First Page

43: 1

Last Page

35

ISSN

1046-8188

Identifier

10.1145/3230871

Publisher

Association for Computing Machinery (ACM)

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1145/3230871

Download

Share

COinS