Social Networks

Last week I attended the presentation Limits of Social Mobilization given by Esteban Moro. He talked about an article related to the DARPA Network Challenge, a competition to locate 10 balloons across the United States. The article focused on the winning team strategy: the team organized a (social) network of people across the USA to locate the balloons, with the promise of sharing the prize if they won.

The key to success was to recruit members all over USA in a very short time. The recruitment strategy was based on rewards. Thus, participants had incentive to involve others. As a result, the network achieved 5,000 participants and they complete the task in less than 9 hours after balloon launch.

The DARPA Challenge is an example of covering in a geographical network. But covering is also important in non geographical networks. For example, in marketing, the goal is to spread the message to a huge number of people/buyers, whitin budget. Campaigns seek to recruit influential individuals to be able to cover a large target audience throught their social connections (Avrachenkov et al. (2012)). Notice that you don’t have to send your message directly to the whole network. The recruiter’s connections will do the job for you. For example, in the DARPA Challenge, not all the participants were located in United States, however they helped to connect members in USA. As you can imagine, not all the 5,000 participants located the balloons, but all of them contributed to find them through their connections.

However there are some differences between the DARPA challenge strategy and the marketing problem. In the first one, the idea is to recruit as many members as possible. In the marketing strategy, recruitment is limited by the budget. Moreover, recruitment must be made with partial information about the members and their connections. As the number of recruited members increases, so does the information about their connections. This information leads to better decisions for further recruitments.

In a joint work with Alonso Silva (at Alcatel-Lucent Bell Labs), we are testing different methods to cover networks. We start with an unknown network and we recruit the first node at random. Once the node is recruited, we get information about their connections (called observed members). Recruited and observed members form the covered network. The following recruited members are chosen according to their connections with the current covered network. The goal is to cover the whole network with the minimum number of recruited members.

Using the tools provided by Esteban Moro in his blog, we describe the covering simulations via videos. The following video shows one of these simulations. Recruited members are depicted in red and observed nodes are in yellow. At each time, one uncovered node is recruited. The new member corresponds to a node with a large number of uncovered connections. In this way, the method tries to choose a top contributor to our covering (see Avrachenkov et al. (2012)).

( Can’t see the video below? Click here. )

References