Publication Type

Journal Article

Version

publishedVersion

Publication Date

10-2018

Abstract

Influence Maximization (IM), which selects a set of k users (called seed set) from a social network to maximize the expected number of influenced users (called influence spread), is a key algorithmic problem in social influence analysis. Due to its immense application potential and enormous technical challenges, IM has been extensively studied in the past decade. In this paper, we survey and synthesize a wide spectrum of existing studies on IM from an algorithmic perspective, with a special focus on the following key aspects (1) a review of well-accepted diffusion models that capture information diffusion process and build the foundation of the IM problem, (2) a fine-grained taxonomy to classify existing IM algorithms based on their design objectives, (3) a rigorous theoretical comparison of existing IM algorithms, and (4) a comprehensive study on the applications of IM techniques in combining with novel context features of social networks such as topic, location, and time. Based on this analysis, we then outline the key challenges and research directions to expand the boundary of IM research.

Keywords

Influence maximization, information diffusion, social networks, algorithm design

Discipline

Databases and Information Systems | Theory and Algorithms

Research Areas

Data Science and Engineering

Publication

IEEE Transactions on Knowledge and Data Engineering

Volume

30

Issue

10

First Page

1852

Last Page

1872

ISSN

1041-4347

Identifier

10.1109/TKDE.2018.2807843

Publisher

Institute of Electrical and Electronics Engineers (IEEE)

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1109/TKDE.2018.2807843

Download

Share

COinS