Edinburgh Research Explorer

Efficient Influence Maximization Under Network Uncertainty

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

Related Edinburgh Organisations

Open Access permissions

Open

Documents

https://ieeexplore.ieee.org/document/8845088
Original languageEnglish
Title of host publication IEEE INFOCOM 2019 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages365-371
Number of pages7
ISBN (Electronic)978-1-7281-1878-9
ISBN (Print)978-1-7281-1879-6
DOIs
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
https://infocom2019.ieee-infocom.org/workshop-communications-and-networking-aspects-online-social-networks

Workshop

WorkshopThe First IEEE INFOCOM Workshop on the Communications and Networking Aspects of Online Social Networks (CAOS’19)
Abbreviated titleINFOCOM 2019
CountryFrance
CityParis
Period29/04/192/05/19
Internet address

Abstract

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.

Download statistics

No data available

ID: 82194310