Components in time-varying graphs
arXiv:1106.2134 · doi:10.1063/1.3697996
Abstract
Real complex systems are inherently time-varying. Thanks to new communication systems and novel technologies, it is today 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.
arXiv comment12 pages, 4 figures, 3 tables
References in corpus (18)
- Error and attack tolerance of complex networks
- Understanding individual human mobility patterns
- Synchronization in complex networks
- Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
- Evolution of the social network of scientific collaborations
- What's in a crowd? Analysis of face-to-face behavioral networks
- Path lengths, correlations, and centrality in temporal networks
- The dynamical strength of social ties in information spreading
- Small-world behavior in time-varying graphs
- Giant strongly connected component of directed networks
- Temporal Graphs
- Information dynamics shape the networks of Internet-mediated prostitution
- Network reachability of real-world contact sequences
- Synchronization in networks of mobile oscillators
- Dynamical and bursty interactions in social networks
- Dynamics of directed graphs: the world-wide Web
- Disease spreading in populations of moving agents
- Information Super-Diffusion on Structured Networks
Cited by in corpus (13)
- Modern temporal network theory: A colloquium
- Graph Metrics for Temporal Networks
- Disease spread through animal movements: a static and temporal network analysis of pig trade in Germany
- Immunization strategies for epidemic processes in time-varying contact networks
- Spatio-temporal networks: reachability, centrality and robustness
- Emergence of synchronization in multiplex networks of mobile Rössler oscillators
- Evolutionary dynamics of time-resolved social interactions
- Importance of individual events in temporal networks
- Temporal networks of face-to-face human interactions
- The Temporal Event Graph
- Exploring the Evolution of Node Neighborhoods in Dynamic Networks
- Only Time Will Tell: Modelling Information Diffusion in Code Review with Time-Varying Hypergraphs
- Higher-order shortest paths in hypergraphs