Communicability in the massive social networks

Developing viable algorithms for scale-up

Given a social network, represented by the relationships between the people in it, some of the key questions which we address in our work are: “Who is the most influential person in the network?”, or “Who is the person who knows most about what is going on in the network?” If, for example, a company wanted to advertise a product, then choosing the big broadcasters in the network and advertising to them can guarantee that the company’s message reaches a wider audience, while if someone wanted to hear the latest rumours in the network, then they would sit next to someone who is a great receiver.

Apart from marketing, another potential application for this is in defence, where one might want to infiltrate or disrupt a network of terrorists; also, our work could potentially be applied in devising optimal strategies for the vaccination of people: people who are great “broadcasters” would have higher priority for vaccination than the rest.

Examples of social networks, which we are interested in are: Facebook, Twitter, networks of telephone calls and email interactions, blog networks, citation networks, to mention but a few. The companies, which we are currently in contact with are big telephone companies and companies for (online) marketing. They have records of the interactions between very large networks of people, usually in the order of 1 000 000 individuals, or even more.

With the advances of digital technology, these interactions are recorded in real time, e.g. monthly, daily, hourly, etc. From the point of view of mathematics, this means that it is no longer adequate to model networks as static objects, and new techniques have to be developed, which take into account the extra information, which companies are ready to give us. In other words, we have to be able to take into account and extract useful information from the extra dimension, that is, the dynamics of the network. In terms of mathematical theory, recent works by E. Estrada (c.f. [Estrada and Hatano, 2008]) and P. Grindrod (c.f. [Grindrod et al., 2011]) provide, amongst other things, the tools and methodology needed for discovering significant broadcasters and receivers in evolving networks. However, one of the challenges in this project is that of scalability. In other words, our task is to implement algorithms, which make possible the application of the theory to very large (real) networks.

We have (successfully) tested our algorithms on real data, in the form of records from daily telephone communications, for one month, between approximately 3.5 mln. people. This work is being prepared as a paper for The All Hands Meeting. Also, another test for our methodology was provided in the form of fMRI brain scans. In the brain, as in a social network, one can use the interactions between different parts of the brain in order to discover areas, which are responsible for sending tasks to other parts of the brain, and areas, which mostly “receive orders” and are responsible for taking action, for example.

by D. Vukadinović Greetham, P. Grindrod and Z. Stoyanov – Reading University