1 Search Results for "Severini, Lorenzo"

Document
DOI: 10.4230/LIPIcs.MFCS.2017.75
Selecting Nodes and Buying Links to Maximize the Information Diffusion in a Network

Authors: Gianlorenzo D'Angelo, Lorenzo Severini, and Yllka Velaj

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

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.
Cite as

Gianlorenzo D'Angelo, Lorenzo Severini, and Yllka Velaj. Selecting Nodes and Buying Links to Maximize the Information Diffusion in a Network. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 75:1-75:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{dangelo_et_al:LIPIcs.MFCS.2017.75,
  author =	{D'Angelo, Gianlorenzo and Severini, Lorenzo and Velaj, Yllka},
  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 =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.75},
  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}
}
  • Refine by Author
  • 1 D'Angelo, Gianlorenzo
  • 1 Severini, Lorenzo
  • 1 Velaj, Yllka

  • Refine by Classification

  • Refine by Keyword
  • 1 Approximation algorithms
  • 1 complex networks
  • 1 independent cascade model
  • 1 information diffusion
  • 1 network augmentation

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact