Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

4-2019

Abstract

An information dissemination campaign is often multifaceted, involving several facets or pieces of information disseminating from different sources. The question then arises, how should we assign such pieces to eligible sources so as to achieve the best viral dissemination results? Past research has studied the problem of Influence Maximization (IM), which is to select a set of k promoters that maximizes the expected reach of a message over a network. However, in this classical IM problem, each promoter spreads out the same unitary piece of information. In this paper, we propose the Optimal Influential Pieces Assignment (OIPA) problem, which is to assign k distinct pieces of an information campaign OIPA to k promoters, so as to achieve the highest viral adoption in a network. We express adoption by users with a logistic model, and show that approximating OIPA within any constant factor is NP-hard. Even so, we propose a branch-and-bound framework for problem with an (1-1/e) approximation ratio. We further optimize this framework with a pruning-intensive progressive upper-bound estimation approach, yielding a (1-1/e-\varepsilon) approximation ratio and significantly lower time complexity, as it relies on the power-law properties of real-world social networks to run efficiently. Our extensive experiments on several real-world datasets show that the proposed approaches consistently outperform intuitive baselines, adopted from state-of-the-art IM algorithms. Furthermore, the progressive approach demonstrates superior efficiency with an up to 24-fold speedup over the plain branch-and-bound approach.

Keywords

Algorithm, Graph, Social influence, Social network

Discipline

Databases and Information Systems | OS and Networks | Social Media | Theory and Algorithms

Research Areas

Data Science and Engineering

Publication

2019 35th IEEE International Conference on Data Engineering: Macau, China, April 8-11: Proceedings

First Page

446

Last Page

457

ISBN

9781538674741

Identifier

10.1109/ICDE.2019.00047

Publisher

IEEE

City or Country

Piscataway, NJ

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1109/ICDE.2019.00047

Download

Share

COinS