^{1,2}, John Tang

^{1}, Mirco Musolesi

^{3}, Giovanni Russo

^{4}, Cecilia Mascolo

^{1}and Vito Latora

^{2,5,6}

### Abstract

Real complex systems are inherently time-varying. Thanks to new communication systems and novel technologies, today it is possible to produce and analyze social and biological networks with detailed information on the time of occurrence and duration of each link. However, standard graph metrics introduced so far in complex network theory are mainly suited for static graphs, i.e., graphs in which the links do not change over time, or graphs built from time-varying systems by aggregating all the links as if they were concurrent in time. In this paper, we extend the notion of connectedness, and the definitions of node and graph components, to the case of *time-varying graphs*, which are represented as time-ordered sequences of graphs defined over a fixed set of nodes. We show that the problem of finding strongly connected components in a time-varying graph can be mapped into the problem of discovering the maximal-cliques in an opportunely constructed static graph, which we name the *affine graph*. It is, therefore, an NP-complete problem. As a practical example, we have performed a temporal component analysis of time-varying graphs constructed from three data sets of human interactions. The results show that taking time into account in the definition of graph components allows to capture important features of real systems. In particular, we observe a large variability in the size of node temporal in- and out-components. This is due to intrinsic fluctuations in the activity patterns of individuals, which cannot be detected by static graph analysis.

Time-varying graphs are a natural model for networked systems in which the relationships among nodes are intrinsically dynamic and fluctuate over time, where links appear and disappear at specific points in time and are often recurrent. Here, we extend the concept of connectedness and the definitions of node and graph components to the case of time-varying graphs, we prove that finding strongly connected components in time-varying graphs is an NP-complete problem and we also report the results of component analysis performed on three real time-varying systems. This analysis confirms that the classical aggregate representations of networks evolving over time wash out most of the richness of the original systems. In particular, static graph erroneously flatten down fluctuations in the size of in- and out-components of nodes, and tends to substantially overestimate the actual size of the connected components of the graph.

This work was partially carried out under the HPC-Europa2 project (project number: 228398) with the support of the European Commission Capacities Area-Research Infrastructures Initiative. This work made also use of the facilities of HECToR, the UK national high performance computing service, which is provided by UoE HPCx, Ltd. at the University of Edinburgh, Cray, Inc., and NAG, Ltd., and funded by the Office of Science and Technology through EPSRC’s High End Computing Programme. This work has been partially supported by the EPSRC Project MOLTEN (EP/l017321/1).

I. INTRODUCTION

II. COMPONENTS IN STATIC GRAPHS

III. COMPONENTS IN TIME-VARYING GRAPHS

IV. THE AFFINE GRAPH OF A TIME-VARYING GRAPH

V. RESULTS

VI. CONCLUSIONS

### Key Topics

- Networks
- 19.0
- Data sets
- 9.0
- Computational complexity
- 6.0
- Data analysis
- 5.0
- Graph theory
- 5.0

## Figures

A directed graph can be partitioned into a set of disjoint weakly connected components (in yellow). Furthermore, each of these components has a rich internal structure, as shown for the GWCC.

A directed graph can be partitioned into a set of disjoint weakly connected components (in yellow). Furthermore, each of these components has a rich internal structure, as shown for the GWCC.

A time-varying graph consisting of a sequence of *M* = 4 graphs with *N* = 5 nodes (panel a) and its corresponding aggregated static graph (panel b). The static representation of graphs discards time ordering of links and time correlations of paths. In the aggregated graph, node 1 and node 2 are neighbors, but in the original time-varying graph they are directly connected only in one of the four graphs of the sequence, namely in . Moreover, in the aggregated graph a path exists from node 1 to node 5 and vice-versa, while in the time-varying graph there exists a temporal path from 5 to 1 but there are no temporal paths from 1 to 5.

A time-varying graph consisting of a sequence of *M* = 4 graphs with *N* = 5 nodes (panel a) and its corresponding aggregated static graph (panel b). The static representation of graphs discards time ordering of links and time correlations of paths. In the aggregated graph, node 1 and node 2 are neighbors, but in the original time-varying graph they are directly connected only in one of the four graphs of the sequence, namely in . Moreover, in the aggregated graph a path exists from node 1 to node 5 and vice-versa, while in the time-varying graph there exists a temporal path from 5 to 1 but there are no temporal paths from 1 to 5.

The affine graph associated to the time-varying graph reported in Fig. 2 . The affine graph is static and undirected, and each of its maximal-cliques corresponds to a strongly connected component of the original time-varying graph .

The affine graph associated to the time-varying graph reported in Fig. 2 . The affine graph is static and undirected, and each of its maximal-cliques corresponds to a strongly connected component of the original time-varying graph .

Size of the temporal in-component (panel a) and out-component (panel b) for each of the *N* = 100 individuals during week 11 of the RM data set. Red circles and blue squares correspond, respectively, to the beginning of the week (WB) and to end of the week (WE). For comparison, the size of the largest connected component of the corresponding aggregated static graph are reported as dashed red line (WB) and solid blue line (WE), respectively.

Size of the temporal in-component (panel a) and out-component (panel b) for each of the *N* = 100 individuals during week 11 of the RM data set. Red circles and blue squares correspond, respectively, to the beginning of the week (WB) and to end of the week (WE). For comparison, the size of the largest connected component of the corresponding aggregated static graph are reported as dashed red line (WB) and solid blue line (WE), respectively.

## Tables

Structural properties of the affine graph corresponding to the time-varying graph of the first 24 h of the week (Monday), and to the whole weeks in the Fall term of RM. We report the number of links (*K*), number of triangles (*T*), number of maximal cliques ( ), average size of maximal cliques ( ), size of the largest maximal clique (*S*), number of largest maximal cliques ( ), number of nodes in the union ( ), and in the intersection ( ) of all largest maximal cliques. The size of the giant component of the corresponding static aggregated graph (*C*) is reported in the rightmost column.

Structural properties of the affine graph corresponding to the time-varying graph of the first 24 h of the week (Monday), and to the whole weeks in the Fall term of RM. We report the number of links (*K*), number of triangles (*T*), number of maximal cliques ( ), average size of maximal cliques ( ), size of the largest maximal clique (*S*), number of largest maximal cliques ( ), number of nodes in the union ( ), and in the intersection ( ) of all largest maximal cliques. The size of the giant component of the corresponding static aggregated graph (*C*) is reported in the rightmost column.

Structural properties of the affine graphs corresponding to time-varying graphs of different hours of the third day and of each of the four days of IC. The graph corresponding to each hour includes all the contacts recorded in that hour, so that, for instance, the first graph is constructed fromthe interactions observed from to . Legend as in Table I .

Structural properties of the affine graphs corresponding to time-varying graphs of different hours of the third day and of each of the four days of IC. The graph corresponding to each hour includes all the contacts recorded in that hour, so that, for instance, the first graph is constructed fromthe interactions observed from to . Legend as in Table I .

Structural properties of the affine graphs corresponding to the time-varying graphs of weeks (upper rows) and pairs of adjacent weeks (lower rows) of FB data set. Legend as in Table I .

Structural properties of the affine graphs corresponding to the time-varying graphs of weeks (upper rows) and pairs of adjacent weeks (lower rows) of FB data set. Legend as in Table I .

Article metrics loading...

Full text loading...

Commenting has been disabled for this content