King's College London

Research portal

Overexposure-aware influence maximization

Research output: Contribution to journalArticlepeer-review

Grigorios Loukidis, Robert Gwadera, Shing-Wan Chang

Original languageEnglish
Article number39
JournalAcm Transactions On Internet Technology
Issue number4
Accepted/In press19 Jun 2020
PublishedNov 2020


  • Overexposure_ACM_TOIT

    Overexposure_ACM_TOIT.pdf, 1.01 MB, application/pdf

    Uploaded date:19 Jun 2020

    Version:Accepted author manuscript

King's Authors


Viral marketing campaigns are often negatively affected by overexposure. Overexposure occurs when users become less likely to favor a promoted product after receiving information about the product from too large a fraction of their friends. Yet, existing influence diffusion models do not take overexposure into account, effectively overestimating the number of users who favor the product and diffuse information about it. In this work, we propose the first influence diffusion model that captures overexposure. In our model, Latency Aware Independent Cascade Model with Overexposure (LAICO), the activation probability of a node representing a user is multiplied (discounted) by an overexposure score, which is calculated based on the ratio between the estimated and the maximum possible number of attempts performed to activate the node. We also study the influence maximization problem under LAICO. Since the spread function in LAICO is non-submodular, algorithms for submodular maximization are not appropriate to address the problem. Therefore, we develop an approximation algorithm that exploits monotone submodular upper and lower bound functions of spread, and a heuristic that aims to maximize a proxy function of spread iteratively. Our experiments show the effectiveness and efficiency of our algorithms.

Download statistics

No data available

View graph of relations

© 2020 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454