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

Viral marketing campaigns seek to recruit the most influential individuals to cover the largest target audi-ence. This can be modeled as the well-studied max-imum coverage problem. There is a related prob-lem 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 mar-keting campaign. In this work, we are interested on both of these problems. Most of the related litera-ture 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 max-imum coverage problem with different knowledge lev-els about the topology of the network. We quantify the difference between these heuristics and the local and global greedy algorithms.