License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2017.75
URN: urn:nbn:de:0030-drops-80853
URL: http://drops.dagstuhl.de/opus/volltexte/2017/8085/
Go to the corresponding LIPIcs Volume Portal


D'Angelo, Gianlorenzo ; Severini, Lorenzo ; Velaj, Yllka

Selecting Nodes and Buying Links to Maximize the Information Diffusion in a Network

pdf-format:
LIPIcs-MFCS-2017-75.pdf (0.6 MB)


Abstract

The Independent Cascade Model (ICM) is a widely studied model that aims to capture the dynamics of the information diffusion in social networks and in general complex networks. In this model, we can distinguish between active nodes which spread the information and inactive ones. The process starts from a set of initially active nodes called seeds. Recursively, currently active nodes can activate their neighbours according to a probability distribution on the set of edges. After a certain number of these recursive cycles, a large number of nodes might become active. The process terminates when no further node gets activated. Starting from the work of Domingos and Richardson [Domingos et al. 2001], several studies have been conducted with the aim of shaping a given diffusion process so as to maximize the number of activated nodes at the end of the process. One of the most studied problems has been formalized by Kempe et al. and consists in finding a set of initial seeds that maximizes the expected number of active nodes under a budget constraint [Kempe et al. 2003]. In this paper we study a generalization of the problem of Kempe et al. in which we are allowed to spend part of the budget to create new edges incident to the seeds. That is, the budget can be spent to buy seeds or edges according to a cost function. The problem does not admin a PTAS, unless P=NP. We propose two approximation algorithms: the former one gives an approximation ratio that depends on the edge costs and increases when these costs are high; the latter algorithm gives a constant approximation guarantee which is greater than that of the first algorithm when the edge costs can be small.

BibTeX - Entry

@InProceedings{dangelo_et_al:LIPIcs:2017:8085,
  author =	{Gianlorenzo D'Angelo and Lorenzo Severini and Yllka Velaj},
  title =	{{Selecting Nodes and Buying Links to Maximize the Information Diffusion in a Network}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{75:1--75:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8085},
  URN =		{urn:nbn:de:0030-drops-80853},
  doi =		{10.4230/LIPIcs.MFCS.2017.75},
  annote =	{Keywords: Approximation algorithms, information diffusion, complex networks, independent cascade model, network augmentation}
}

Keywords: Approximation algorithms, information diffusion, complex networks, independent cascade model, network augmentation
Seminar: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Issue Date: 2017
Date of publication: 22.11.2017


DROPS-Home | Fulltext Search | Imprint Published by LZI