Analysis of Myopic Network Covering Algorithms.

International audienceMarketing campaigns need to spread their message to the largest target audience. Therefore, it's important to identify and recruit influential individuals: people capable of spreading the message through their social connections. One of the main difficulties is that we usually don't have information about the network, except the one provided by the previously recruited individuals. The problem is modelled as follows: We want to determine a group of n individuals to be recruited in order to maximize the size of the covered set of nodes. The covered set consists on the recruited nodes and their neighbors. The topology of the whole network is unknown. The only information available is the covered subnetwork (the connections between covered nodes). Using this information, we need to recruit a new member at each step from the neighbors of the covered nodes. Under these assumptions, we analyse the performance of different myopic, greedy network covering algorithms and we compare their performances over a variety of social network models.