Coverage centralities for temporal networks*,**
National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo
2 JST, ERATO, Kawarabayashi Large Graph Project, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan
3 Department of Computer Science, The University of Tokyo, 3-7-1 Hongo, Bunkyo-ku, Tokyo 113-8654, Japan
4 Preferred Infrastructure, Inc., 2-40-1 Hongo, Bunkyo-ku, Tokyo 113-0033, Japan
Received: 23 June 2015
Received in final form: 23 December 2015
Published online: 8 February 2016
Structure of real networked systems, such as social relationship, can be modeled as temporal networks in which each edge appears only at the prescribed time. Understanding the structure of temporal networks requires quantifying the importance of a temporal vertex, which is a pair of vertex index and time. In this paper, we define two centrality measures of a temporal vertex based on the fastest temporal paths which use the temporal vertex. The definition is free from parameters and robust against the change in time scale on which we focus. In addition, we can efficiently compute these centrality values for all temporal vertices. Using the two centrality measures, we reveal that distributions of these centrality values of real-world temporal networks are heterogeneous. For various datasets, we also demonstrate that a majority of the highly central temporal vertices are located within a narrow time window around a particular time. In other words, there is a bottleneck time at which most information sent in the temporal network passes through a small number of temporal vertices, which suggests an important role of these temporal vertices in spreading phenomena.
Contribution to the Topical Issue “Temporal Network Theory and Applications”, edited by Petter Holme.
Supplementary material in the form of one pdf file available from the Journal web page at http://dx.doi.org/10.1140/epjb/e2016-60498-7
© The Author(s) 2016. This article is published with open access at Springerlink.com
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.