Research
Objectives
We will develop and apply mathematical concepts and computational tools aimed at technological networks whose topology varies over time. Three complementary strands will be followed:
- Network Analysis: quantifying appropriate local measures of importance for individual nodes and edges and global summaries of the network status.
- Network Modeling: specifying and studying realistic models for the ‘birth’ and ‘death’ of edges in order to produce explanatory, calibrated models that generalize traditional static random graph classes.
- Network Prediction: real time identification of network ‘phase changes’, quantification of uncertainty and inference over possible future states.
Novel methodologies will be tested on large scale data focusing on online and mobile human behaviour, with both a push and a pull coming from the project’s Strategic Technology Advisor and our industrial partners.
Background
Computer Laboratory, University of Cambridge
At the Computer Lab we have been investigating, along with our
partners at the University of Catania, the importance of taking into
account temporal information when analysing empirically observed
networks.
Our first study evaluated the basic notion of shortest temporal
paths used extensively in graph theory, using empirical datasets. We
showed that as static graphs ignore the time order of contacts, the
available links are overestimated and the true shortest paths are
underestimated [1][2]. In addition, by measuring the speed that a
temporal graph changes compared to the average shortest temporal path
length, we uncover small- world behaviour in temporal graphs [3].
We have also extended the notion of important or key nodes in a
network, more commonly known as centrality. Since two key measures,
namely closeness and betweenness, are based on shortest paths in a
static graph, we can define temporal centrality based on temporal
shortest paths.
We evaluated these new temporal centrality measures from two
perspectives: firstly, semantic with a corporate email dataset with
known user roles [4], and process driven, in short range mobile
worm containment [5].
Our most recent work has investigated the concepts of temporally
connected components and demonstrated that temporal analysis gives us a
better understanding of the diffusion properties of real contact
networks that is missed by static analysis [6].
More information can be found at the STNA:
Spatio-Temporal Network Analysis page.
Key Publications:
[1] John Tang, Mirco
Musolesi, Cecilia Mascolo and Vito Latora. Temporal Distance
Metrics for Social Network Analysis. In Proceedings of the 2nd ACM
SIGCOMM Workshop on Online Social Networks (WOSN ’09). Aug 2009,
[2] John Tang, Mirco Musolesi,
Cecilia Mascolo and Vito Latora. Characterising
Temporal Distance and Reachability in Mobile and Online Social Networks.
In ACM SIGCOMM Computer Communication Review (CCR). Vol. 40 (1), pp.
118-124. Jan 2010.
[3] John Tang, Salvatore
Scellato, Mirco Musolesi, Cecilia Mascolo and Vito Latora. Small World
Behavior in Time-Varying Graphs. In Physical Review E, Vol. 81 (5),
055101 (R), May 2010.
[4] John Tang, Mirco Musolesi,
Cecilia Mascolo, Vito Latora and Vincenzo Nicosia. Analysing
Information Flows and Key Mediators through Temporal Centrality Metrics.
In Proceedings of the 3rd ACM SIGOPS Workshop on Social Networks
Systems (SNS ’10), Apr 2010.
[5] John Tang, Cecilia Mascolo,
Mirco Musolesi and Vito Latora. Exploiting
Temporal Complex Network Metrics in Mobile Malware Containment. In
Proceedings of the 12th IEEE International Symposium on a World of
Wireless, Mobile and Multimedia Networks (WOWMOM ’11), June 2011.
[6] Vincenzo Nicosia, John
Tang, Mirco Musolesi, Gianni Russo, Cecilia Mascolo and Vito Latora. Components in time-varying graphs.
Under Review, arxiv: http://arxiv.org/abs/1106.2134