Maximizing multifaceted network influence

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

DOI

  • Yuchen Li, Singapore Management University
  • ,
  • Ju Fan, Renmin University of China
  • ,
  • George Ovchinnikov, Skolkovo Institute of Science and Technology
  • ,
  • Panagiotis Karras

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.

Original languageEnglish
Title of host publicationProceedings - 2019 IEEE 35th International Conference on Data Engineering, ICDE 2019
Number of pages12
PublisherIEEE
Publication yearApr 2019
Pages446-457
Article number8731520
ISBN (Electronic)9781538674741
DOIs
Publication statusPublished - Apr 2019
Event35th IEEE International Conference on Data Engineering, ICDE 2019 - Macau, China
Duration: 8 Apr 201911 Apr 2019

Conference

Conference35th IEEE International Conference on Data Engineering, ICDE 2019
LandChina
ByMacau
Periode08/04/201911/04/2019
SeriesProceedings - International Conference on Data Engineering
Volume2019-April
ISSN1084-4627

    Research areas

  • Algorithm, Graph, Social influence, Social network

See relations at Aarhus University Citationformats

ID: 160581422