Social network analysis for routing optimisation in pocket switched networks

Notes during project


Ubiquitous computing becomes an important factor in our lives. Essentially, digital information will start to flow through social networks for several purposes (text messaging, traffic analysis and control, local news). Infrustructure networks that are already in place, are incapable of handling a great amount of network traffic when the same links are being used by many actors at the same time. Opposite to that, social networks are dynamic and gain more bandwidth when more actors are involved. We can extend the infrustructure with the social structure in order to enhance connectivity to mobile services.

This thesis explores routing optimisation in social networks. Using social network analysis, we can identify important nodes in the network and exploit the advantage of their structural significance. Routing optimisation in such networks is much considerable, as it will enable the network to act faster, using limited bandwidth and limited processing power on the mobile devices that are being carried by individuals. Moreover, we present the trade-offs that exist when using central nodes in the network for routing optimisation: While the routing efficiency increases, the unfairness of the protocol on the central nodes is affecting their resource usage.


Cambridge and Queens College

Thesis Simulation code and report

Metrics in social network analysis

Betweenness Centrality

For a graph G: = (V,E) with n vertices, the betweenness CB(v) for vertex v is:

where \CFƒst is the number of shortest geodesic paths from s to t, and \CFƒst(v) is the number of shortest geodesic paths from s to t that pass through the vertex v.

Hue (from red=0 to blue=max) shows the node betweenness.

Eigenvector centrality

Eigenvector centrality is a measure of the importance of a node in a network. It assigns relative scores to all nodes in the network based on the principle that connections to high-scoring nodes contribute more to the score of the node in question than equal connections to low-scoring nodes. Google's PageRank is a variant of the Eigenvector centrality measure.


The node diameter represents higher eigenvector centrality