Graph Metrics for Temporal Networks

Abstract

Temporal networks, i.e., networks in which the interactions among a set of elementary units change over time, can be modelled in terms of time-varying graphs, which are time-ordered sequences of graphs over a set of nodes. In such graphs, the concepts of node adjacency and reachability crucially depend on the exact temporal ordering of the links. Consequently, all the concepts and metrics proposed and used for the characterisation of static complex networks have to be redefined or appropriately extended to time-varying graphs, in order to take into account the effects of time ordering on causality. In this chapter we discuss how to represent temporal networks and we review the definitions of walks, paths, connectedness and connected components valid for graphs in which the links fluctuate over time. We then focus on temporal node-node distance, and we discuss how to characterise link persistence and the temporal small-world behaviour in this class of networks. Finally, we discuss the extension of classic centrality measures, including closeness, betweenness and spectral centrality, to the case of time-varying graphs, and we review the work on temporal motifs analysis and the definition of modularity for temporal graphs.

26 pages, 5 figures, Chapter in Temporal Networks (Petter Holme and Jari Saramäki editors). Springer. Berlin, Heidelberg 2013

References in corpus (11)

• Modularity and community structure in networks
• Community structure in directed networks
• Small But Slow World: How Network Topology and Burstiness Slow Down Spreading
• Path lengths, correlations, and centrality in temporal networks
• Extending the definition of modularity to directed graphs with overlapping communities
• Size reduction of complex networks preserving modularity
• Network reachability of real-world contact sequences
• Dynamical and bursty interactions in social networks
• Persistence and periodicity in a dynamic proximity network
• Microdynamics in stationary complex networks
• Applications of Temporal Graph Metrics to Real-World Networks

Cited by in corpus (33)

• Modern temporal network theory: A colloquium
• Stream Graphs and Link Streams for the Modeling of Interactions over Time
• On Proximity and Structural Role-based Embeddings in Networks: Misconceptions, Techniques, and Applications
• Spatio-temporal networks: reachability, centrality and robustness
• Persistence in Complex Systems
• Applications of Temporal Graph Metrics to Real-World Networks
• Time Centrality in Dynamic Complex Networks
• Coverage centralities for temporal networks
• Entropy Measures of Human Communication Dynamics
• A Network Science perspective of Graph Convolutional Networks: A survey
• A Framework for Generalizing Graph-based Representation Learning Methods
• Exploring the Evolution of Node Neighborhoods in Dynamic Networks
• Using Compressed Suffix-Arrays for a Compact Representation of Temporal-Graphs
• Computing Betweenness Centrality in Link Streams
• Dynamic Node Embeddings from Edge Streams
• Algorithmic Aspects of Temporal Betweenness
• Centralities in complex networks
• Social network analysis of manga: similarities to real-world social networks and trends over decades
• Flow of temporal network properties under local aggregation and time shuffling: a tool for characterizing, comparing and classifying temporal networks
• Temporal Network Motifs: Models, Limitations, Evaluation
• Proposal for a Correction to the Temporal Correlation Coefficient Calculation for Temporal Networks
• The Atlas for the Aspiring Network Scientist
• Dynamic Graph Metrics: Tutorial, Toolbox, and Tale
• Dynamical Properties of Interaction Data
• Benchmarking Measures of Network Influence
• Unveiling the relation between herding and liquidity with trader lead-lag networks
• A Stochastic Geo-spatiotemporal Bipartite Network to Optimize GCOOS Sensor Placement Strategies
• STROOBnet Optimization via GPU-Accelerated Proximal Recurrence Strategies
• The Right Way to Search Evolving Graphs
• A Network-based Multimodal Data Fusion Approach for Characterizing Dynamic Multimodal Physiological Patterns
• Team dynamics during the delivery of a large-scale, engineered system
• An Efficient Procedure for Mining Egocentric Temporal Motifs
• The Ties that Bind Networks: Weak Ties Facilitate the Emergence of Collective Memories