Connections in complex networks are inherently fluctuating over time and exhibit more dimensionality than analysis based on standard static graph measures can capture. Here, we introduce the concepts of temporal paths and distance in time-varying graphs. We define as temporal small world a time-varying graph in which the links are highly clustered in time, yet the nodes are at small average temporal distances. We explore the small-world behavior in synthetic time-varying networks of mobile agents, and in real social and biological time-varying systems. PACS numbers: 89.75.Hc, 89.75.Fb, 87.19.lj In the last decade, the study of complex networks has attracted a lot of attention in the scientific community as various social, biological and technological systems can be represented and analysed as graphs [1] . Typically, such systems are inherently dynamic, with the links changing and fluctuating over time. Human contacts or relationships change over time because individuals lose old acquaintances, acquire new ones, or move over geographic space [2, 3] . Communication in man-made networks, such as machine connections and social interactions over the Internet, takes place at specific points in time [4] [5] [6] . New links appear while some others disappear in the World-Wide-Web [7] , in patterns of interactions among gene from microarray time experiments [8, 9] or in functional brain networks [10, 11] . The time evolution of a network by the addition, as well as the deletion, of nodes and links has been extensively modelled with the main purpose of reproducing, asymptotically, statistical properties such as scale-free degree distributions [1, 12] . With only a few notable exceptions [13] [14] [15] , less focus has been given to the characterization of the dynamics of complex networks in stationary conditions. In particular, the small-world phenomenon, i.e., the fact that real networks have high clustering coefficient, while the typical distance between their nodes is small as in random graphs, has been investigated in static graphs, neglecting the temporal dimension [16] [17] [18] . The time evolution of a real system, when considered, is usually studied by evaluating the standard static measures (distances and clustering coefficient) on snapshots of the network taken at different times [19, 20] . As we will show below, this approach does not capture entirely the dynamic correlations of a time-varying network. In this Letter, we introduce a measure of the temporal distance between the nodes of time-varying graphs, i.e. graphs with time-fluctuating links. Such temporal distance takes into account the actual time order, duration and correlations between links appearing at different times. This metric, together with a measure of the time-persistence of the links, allows to define and investigate temporal small-world behavior in social and biological networks that change over time. Consider a network with N nodes, where the links can fluctuate in time. The typical example is a social system, with no births or deaths, where the patterns of interaction are changing in time because of the spatial movement of the individuals, or because the individuals lose old acquaintances and get new ones. The system can be described at its maximum resolution sampling time as a time-varying graph, i.e. a discrete sequence (an ordered set) G 1 , G 2 , . . . , G T of T undirected or directed graphs, where T is the length of the sequence. In compact notation, we denote the entire sequence as G = {G t } t=1,2,...,T . A time-varying graph G can be represented by means of a N × N time-dependent adjacency matrix A(t), t = 1, . . . , T , where a ij (t) are the elements of the adjacency matrix of the t-th graph. We indicate as K(t) the number of links in the t-th graph of the sequence. A sequence of graphs is convenient to describe systems where each connection starts at a specific time, and also has a temporal duration. In this sense, timevarying graphs are different from previous temporal approaches [4, 5, 21, 22] designed to characterize systems as email exchanges, where the links have instead no temporal duration, because the exchange is instantaneous. Moreover, a time-varying graph is a different ensemble from those usually studied in the literature [23, 24] . In fact, in a time-varying graph, what matters is not only the probabilty distribution P (G) over the graphs in the ensemble, but also how the graphs are ordered in time. By counting the number of times a given graph G appears in the time sequence, we can construct P (G). To fully describe time-varying graphs we also need to know how graphs are correlated in time. For instance we need to know the conditional probabilities P (G t |G t−1 ) of observing graph G t after graph G t−1 (more in general, the probabilities P (G t |G 1 , G 2 , . . . , G t−1 ) of observing graph G t after the sequence G 1 , G 2 , . . . , G t−1 ). In most cases, the contacts between the same node pair in time-varying systems tend to be clustered in time, i.e. they show persistence over time [4] . For instance, people tend to engage in relations for continuous intervals of time. Hence, a given link has a higher probability to appear in graph G t if it was already present in graph G t−1 . To quantify
In REF , small-world behavior was analyzed in temporal networks using temporal paths.
Small-world behavior in time-varying graphs
Phys. Rev. E 81, 055101(R) (2010)
Medicine Physics