MOLTEN logoResearch

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: 

  1. Network Analysis: quantifying appropriate local measures of importance for individual nodes and edges and global summaries of the network status.
  2. 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.
  3. 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