Aarhus University Seal / Aarhus Universitets segl

Panagiotis Karras

Maximizing multifaceted network influence

Publikation: Bidrag til bog/antologi/rapport/proceedingKonferencebidrag i proceedingsForskningpeer 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.

OriginalsprogEngelsk
TitelProceedings - 2019 IEEE 35th International Conference on Data Engineering, ICDE 2019
Antal sider12
ForlagIEEE
Udgivelsesårapr. 2019
Sider446-457
Artikelnummer8731520
ISBN (Elektronisk)9781538674741
DOI
StatusUdgivet - apr. 2019
Begivenhed35th IEEE International Conference on Data Engineering, ICDE 2019 - Macau, Kina
Varighed: 8 apr. 201911 apr. 2019

Konference

Konference35th IEEE International Conference on Data Engineering, ICDE 2019
LandKina
ByMacau
Periode08/04/201911/04/2019
SerietitelProceedings of the International Conference on Data Engineering
Vol/bind2019 April
ISSN1063-6382

Se relationer på Aarhus Universitet Citationsformater

ID: 160581422