Maximizing multifaceted network influence

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


  • 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
Publication yearApr 2019
Article number8731520
ISBN (Electronic)9781538674741
Publication statusPublished - Apr 2019
Event35th IEEE International Conference on Data Engineering, ICDE 2019 - Macau, China
Duration: 8 Apr 201911 Apr 2019


Conference35th IEEE International Conference on Data Engineering, ICDE 2019
SeriesProceedings of the International Conference on Data Engineering
Volume2019 April

    Research areas

  • Algorithm, Graph, Social influence, Social network

See relations at Aarhus University Citationformats

ID: 160581422