Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download

https://hal.inria.fr/hal-00922517
Contributor : Alonso Silva <>
Submitted on : Friday, December 27, 2013 - 1:20:15 PM
Last modification on : Thursday, December 10, 2020 - 10:56:40 AM
Long-term archiving on: : Friday, March 28, 2014 - 4:50:50 PM

Files

pato11.pdf
Files produced by the author(s)

Identifiers

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

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⟩

Share

Metrics

Record views

472

Files downloads

1340