Maximizing multifaceted network influence

Yuchen Li, Ju Fan, George Ovchinnikov, Panagiotis Karras

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    10 Citations (Scopus)

    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.

    Original languageEnglish
    Title of host publicationProceedings - 2019 IEEE 35th International Conference on Data Engineering, ICDE 2019
    PublisherIEEE Computer Society
    Pages446-457
    Number of pages12
    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

    Publication series

    NameProceedings - International Conference on Data Engineering
    Volume2019-April
    ISSN (Print)1084-4627

    Conference

    Conference35th IEEE International Conference on Data Engineering, ICDE 2019
    Country/TerritoryChina
    CityMacau
    Period8/04/1911/04/19

    Keywords

    • Algorithm
    • Graph
    • Social influence
    • Social network

    Fingerprint

    Dive into the research topics of 'Maximizing multifaceted network influence'. Together they form a unique fingerprint.

    Cite this