Applications of Temporal Graph Metrics to Real-World Networks
Real world networks exhibit rich temporal information: friends are added and removed over time in online social networks; the seasons dictate the predator-prey relationship in food webs; and the propagation of a virus depends on the network of human conta
- PDF / 890,361 Bytes
- 25 Pages / 439.36 x 666.15 pts Page_size
- 8 Downloads / 216 Views
Abstract Real world networks exhibit rich temporal information: friends are added and removed over time in online social networks; the seasons dictate the predatorprey relationship in food webs; and the propagation of a virus depends on the network of human contacts throughout the day. Recent studies have demonstrated that static network analysis is perhaps unsuitable in the study of real world network since static paths ignore time order, which, in turn, results in static shortest paths overestimating available links and underestimating their true corresponding lengths. Temporal extensions to centrality and efficiency metrics based on temporal shortest paths have also been proposed. Firstly, we analyse the roles of key individuals of a corporate network ranked according to temporal centrality within the context of a bankruptcy scandal; secondly, we present how such temporal metrics can be used to study the robustness of temporal networks in presence of random errors
J. Tang I. Leontiadis S. Scellato C. Mascolo Computer Laboratory, University of Cambridge 15 JJ Thomson Avenue, Cambridge CB3 0FD, UK V. Nicosia Computer Laboratory, University of Cambridge 15 JJ Thomson Avenue, Cambridge CB3 0FD, UK Laboratorio sui Sistemi Complessi, Scuola Superiore di Catania,Via Valdisavoia 9, 95123 Catania, Italy M. Musolesi () School of Computer Science, University of Birmingham, Edgbaston, Birmingham B15 2TT, UK e-mail: [email protected] V. Latora Laboratorio sui Sistemi Complessi, Scuola Superiore di Catania,Via Valdisavoia 9, 95123 Catania, Italy School of Mathematical Sciences, Queen Mary, University of London, E1 4NS London, UK Dipartimento di Fisica e Astronomia and INFN, Universit´a di Catania and INFN, Via S. Sofia 64, 95123 Catania, Italy P. Holme and J. Saram¨aki (eds.), Temporal Networks, Understanding Complex Systems, DOI 10.1007/978-3-642-36461-7 7, © Springer-Verlag Berlin Heidelberg 2013
135
136
J. Tang et al.
and intelligent attacks; thirdly, we study containment schemes for mobile phone malware which can spread via short range radio, similar to biological viruses; finally, we study how the temporal network structure of human interactions can be exploited to effectively immunise human populations. Through these applications we demonstrate that temporal metrics provide a more accurate and effective analysis of real-world networks compared to their static counterparts.
1 Introduction Temporal graph metrics [48, 49] represent a powerful tool for the analysis of realworld dynamic networks, especially with respect to the aspects for which time plays a fundamental role, such as in the case of spreading of a piece of information or a disease. Indeed, existing metrics are not able to characterise the temporal structure of dynamic networks, for example in terms of centrality of nodes over time. For these reasons, new metrics have been introduced, such as temporal centrality, in order to capture the essential characteristics of time-varying graphs. A detailed description of the metrics used in this chapte
Data Loading...
