Friday 28
Network optimization and telecom applications
Alonso Silva
› 15:00 - 15:20 (20min)
› Bât. B - TD 32
Analysis of Myopic Network Covering Algorithms.
Patricio Reyes  1@  , Alonso Silva  3, 2, *@  
1 : Dept. Statistics. Universidad Carlos III de Madrid [Madrid]  (UC3M)  -  Website
Calle Madrid 126, UC3M - Estadística. 28903 Getafe, Madrid -  Espagne
3 : Laboratory of Information, Network and Communication Sciences  (LINCS)  -  Website
INRIA, Institut Mines-Télécom, Université Pierre et Marie Curie (UPMC) - Paris VI
23 avenue d'Italie 75013 Paris -  France
2 : Alcatel-Lucent Bell Labs France
Alcatel-Lucent Bell Labs France
Centre de Villarceaux, Route de Villejust, 91620, NOZAY, FRANCE -  France
* : Corresponding author

Marketing 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.


Online user: 2