Maximum Coverage and Maximum Connected Covering in Social Networks with Partial Topology Information

Abstract : Viral marketing campaigns seek to recruit the most influential individuals to cover the largest target audience. This can be modeled as the well-studied maximum coverage problem. There is a related problem when the recruited nodes are connected. It is called the maximum connected cover problem. This problem ensures a strong coordination between the influential nodes which are the backbone of the marketing campaign. In this work, we are interested on both of these problems. Most of the related literature assumes knowledge about the topology of the network. Even in that case, the problem is known to be NP-hard. In this work, we propose heuristics to the maximum connected cover problem and the maximum coverage problem with different knowledge levels about the topology of the network. We quantify the difference between these heuristics and the local and global greedy algorithms.
Type de document :
Communication dans un congrès
6th IEEE International Workshop on Network Science for Communication Networks, May 2014, Toronto, Canada
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00922517
Contributeur : Alonso Silva <>
Soumis le : vendredi 27 décembre 2013 - 13:20:15
Dernière modification le : mardi 24 avril 2018 - 13:35:06
Document(s) archivé(s) le : vendredi 28 mars 2014 - 16:50:50

Fichiers

pato11.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00922517, version 1
  • ARXIV : 1312.7249

Collections

Citation

Patricio Reyes, Alonso Silva. Maximum Coverage and Maximum Connected Covering in Social Networks with Partial Topology Information. 6th IEEE International Workshop on Network Science for Communication Networks, May 2014, Toronto, Canada. 〈hal-00922517〉

Partager

Métriques

Consultations de la notice

391

Téléchargements de fichiers

758