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