Components in time-varying graphs
From MaRDI portal
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.
Recommendations
Cites work
- Algorithm 457: finding all cliques of an undirected graph
- Algorithms for maximum independent sets
- Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
- Complex networks: structure and dynamics
- Connectivity and inference problems for temporal networks
- Dynamics of directed graphs: The world-wide Web
- Evolution of the social network of scientific collaborations
- Evolving graphs: dynamical models, inverse problems and propagation
- Finding a Maximum Independent Set
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Information dynamics shape the sexual networks of Internet-mediated prostitution
- On cliques in graphs
- Probabilistic checking of proofs
- Proof verification and the hardness of approximation problems
- Time-stamped graphs and their associated influence digraphs
- What's in a crowd? Analysis of face-to-face behavioral networks
Cited in
(22)- Motif-synchronization: a new method for analysis of dynamic brain networks with EEG
- Discovering patterns in time-varying graphs: a triclustering approach
- Wardrop equilibrium on time-varying graphs
- Modeling nonlocal behavior in epidemics via a reaction-diffusion system incorporating population movement along a network
- Exploring the evolution of node neighborhoods in dynamic networks
- Efficiency centrality in time-varying graphs
- On the expressivity of time-varying graphs
- Immunization strategies for epidemic processes in time-varying contact networks
- Expressivity of Time-Varying Graphs
- The temporal event graph
- Parallel maximum clique algorithms with applications to network analysis
- Robust Time-Varying Undirected Graphs
- On the emergence of large clusters of acoustic power sources at the onset of thermoacoustic instability in a turbulent combustor
- A study of connectivity on dynamic graphs: computing persistent connected components
- On computing large temporal (unilateral) connected components
- EVENT GRAPHS: ADVANCES AND APPLICATIONS OF SECOND-ORDER TIME-UNFOLDED TEMPORAL NETWORK MODELS
- Weighted temporal event graphs and temporal-network connectivity
- On computing optimal temporal branchings
- On computing large temporal (unilateral) connected components
- Time and sequence in networks of social interactions
- Temporally connected components
- On computing optimal temporal branchings and spanning subgraphs
This page was built for publication: Components in time-varying graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2787742)
