Efficient Influence Maximization Under Network Uncertainty

Soheil Eshgi, Setareh Maghsudi, Valerio Restocchi, Sebastian Stein, Leandros Tassiulas

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We consider the influence maximization (IM) problem in a partially visible social network. The goal is to design a decision-making framework for an autonomous agent to select a limited set of influential seed nodes to spread a message as widely as possible across the network. We consider the realistic case where only a partial section of the network is visible to the agent, while the rest is one of a finite set of known structures, each with a given realization probability. We show that solving the IM problem in this setting is NP-hard, and we provide analytical guarantees for the performance of a novel computationally-efficient seed-selection approximation algorithm for the agent. In empirical experiments on real-world social networks, we demonstrate the efficiency of our scheme and show that it outperforms state-of-the-art approaches that do not model the uncertainty.
Original languageEnglish
Title of host publication IEEE INFOCOM 2019 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)
Place of PublicationParis, France
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages7
ISBN (Electronic)978-1-7281-1878-9
ISBN (Print)978-1-7281-1879-6
Publication statusPublished - 23 Sep 2019
EventThe First IEEE INFOCOM Workshop on the Communications and Networking Aspects of Online Social Networks (CAOS’19): in conjunction with IEEE INFOCOM 2019 - Paris, France
Duration: 29 Apr 20192 May 2019


WorkshopThe First IEEE INFOCOM Workshop on the Communications and Networking Aspects of Online Social Networks (CAOS’19)
Abbreviated titleINFOCOM 2019
Internet address


Dive into the research topics of 'Efficient Influence Maximization Under Network Uncertainty'. Together they form a unique fingerprint.

Cite this