Maximizing multifaceted network influence

Yuchen Li, Ju Fan, George Ovchinnikov, Panagiotis Karras

    Результат исследований: Глава в книге, отчете, сборнике статейМатериалы для конференциирецензирование

    11 Цитирования (Scopus)


    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.

    Язык оригиналаАнглийский
    Название основной публикацииProceedings - 2019 IEEE 35th International Conference on Data Engineering, ICDE 2019
    ИздательIEEE Computer Society
    Число страниц12
    ISBN (электронное издание)9781538674741
    СостояниеОпубликовано - апр. 2019
    Событие35th IEEE International Conference on Data Engineering, ICDE 2019 - Macau, Китай
    Продолжительность: 8 апр. 201911 апр. 2019

    Серия публикаций

    НазваниеProceedings - International Conference on Data Engineering
    ISSN (печатное издание)1084-4627


    Конференция35th IEEE International Conference on Data Engineering, ICDE 2019


    Подробные сведения о темах исследования «Maximizing multifaceted network influence». Вместе они формируют уникальный семантический отпечаток (fingerprint).