Temporal Network Theory (Computational Social Sciences)

✍ Scribed by Petter Holme (editor), Jari Saramäki (editor)

• Publisher: Springer
• Year: 2023
• Tongue: English
• Leaves: 486
• Edition: 2
• Category: Library

✦ Synopsis

This book focuses on the theoretical side of temporal network research and gives an overview of the state of the art in the field. Curated by two pioneers in the field who have helped to shape it, the book contains contributions from many leading researchers. Temporal networks fill the border area between network science and time-series analysis and are relevant for epidemic modeling, optimization of transportation and logistics, as well as understanding biological phenomena.

Over the past 20 years, network theory has proven to be one of the most powerful tools for studying and analyzing complex systems. Temporal network theory is perhaps the most recent significant development in the field in recent years, with direct applications to many of the “big data” sets. This book appeals to students, researchers, and professionals interested in theory and temporal networks―a field that has grown tremendously over the last decade.

This second edition of Temporal Network Theory extends the first with three chapters highlighting recent developments in the interface with machine learning.

✦ Table of Contents

Preface to the Second Edition
Preface to the First Edition
Contents
1 A Map of Approaches to Temporal Networks
1.1 Overview
1.2 Temporal Network Data
1.2.1 Events
1.2.2 Boundaries
1.2.3 Connectivity
1.3 Simplifying and Coarse-Graining Temporal Networks
1.3.1 Projections to Static Networks
1.3.2 Separating the Dynamics of Contacts, Links, and Nodes
1.3.3 Mesoscopic Structures
1.3.4 Fundamental Structures
1.4 Important Nodes, Links, and Events
1.4.1 Generalizing Centrality Measures
1.4.2 Controllability
1.4.3 Vaccination, Sentinel Surveillance, and Influence Maximization
1.4.4 Robustness to Failure and Attack
1.5 How Structure Affects Dynamics
1.5.1 Simulating Disease Spreading
1.5.2 Tuning Temporal Network Structure by Randomization
1.5.3 Models of Temporal Networks
1.6 Other Topics
1.7 Future Perspectives
References
2 Fundamental Structures in Temporal Communication Networks
2.1 Introduction
2.2 Network Structure of Communication Events
2.2.1 Synchronous Versus Asynchronous
2.2.2 One-to-One, One-to-Many, Many-to-Many
2.2.3 Connecting to Network Theory
2.2.4 The Case of Many-to-Many, Synchronous Networks
2.3 Frequently Asked Questions
2.3.1 What Do You Mean `Framework'!?
2.3.2 Is the Framework All Done and Ready to Use?
2.3.3 Is It Just for Communication Networks?
2.3.4 Isn't All This Obvious?
2.4 Consequences for Analysis and Modeling
2.4.1 Randomization
2.4.2 Generative Models
2.4.3 Link Prediction and Link Activity
2.4.4 Spreading Processes
2.4.5 Communities
2.5 Conclusion
References
3 Weighted, Bipartite, or Directed Stream Graphs for the Modeling of Temporal Networks
3.1 Introduction
3.2 Weighted Stream Graphs
3.3 Bipartite Stream Graphs
3.4 Directed Stream Graphs
3.5 Conclusion
References
4 Modelling Temporal Networks with Markov Chains, Community Structures and Change Points
4.1 Introduction
4.2 Temporal Networks as Markov Chains
4.3 Markov Chains with Communities
4.4 Markov Chains with Change Points
4.5 Conclusion
References
5 Visualisation of Structure and Processes on Temporal Networks
5.1 Introduction
5.2 Temporal Networks
5.3 Visualisation on and of Temporal Networks
5.3.1 Layouts
5.3.2 Visual Clutter
5.3.3 Estimating Clutter on Temporal Networks
5.4 Visual Insights
5.4.1 Network Data
5.4.2 Temporal Structure
5.4.3 Temporal Activity
5.4.4 Dynamic Processes
5.5 Visual and Computational Limitations
5.6 Conclusion
References
6 Weighted Temporal Event Graphs and Temporal-Network Connectivity
6.1 Introduction
6.2 Mapping Temporal Networks Onto Weighted Event Graphs
6.2.1 Definitions: Vertices, Events, Temporal Network
6.2.2 Definitions: Adjacency and Δt-Adjacency
6.2.3 Definitions: Temporal Connectivity and Temporal Subgraphs
6.2.4 Definitions: Time-Respecting Path and Δt-Constrained Time-Respecting Path
6.2.5 The Weighted Event Graph and Its Thresholded and Reduced Versions
6.2.6 Computational Considerations
6.3 How to Interpret and Use Weighted Event Graphs
6.3.1 How the Basic Features of D and DΔt Map Onto Features of G
6.3.2 Temporal Motifs and DΔt
6.3.3 Components of D and Temporal-Network Percolation
6.4 Discussion and Conclusions
References
7 Exploring Concurrency and Reachability in the Presence of High Temporal Resolution
7.1 Introduction
7.2 Previous Studies on Concurrency and Reachability
7.3 Effects of Concurrency: Empirical Examples
7.3.1 Data
7.3.2 Change to the Interval Representation
7.3.3 Measuring and Controlling Concurrency
7.3.4 Measuring Reachability
7.3.5 Reachability with Concurrency
7.3.6 Accuracy of Reachability from the Interval Representation
7.4 Final Remarks
References
8 Metrics for Temporal Text Networks
8.1 Introduction
8.2 Representing Temporal Text Networks
8.3 Path-Based Metrics
8.3.1 Incidence and Adjacency
8.3.2 Walks and Paths
8.4 Path Lengths
8.5 Empirical Study
8.6 Final Remarks
References
9 Bursty Time Series Analysis for Temporal Networks
9.1 Introduction
9.2 Bursty Time Series Analysis
9.2.1 Measures and Characterizations
9.2.2 Correlation Structure and the Bursty-Get-Burstier Mechanism
9.2.3 Temporal Scaling Behaviors
9.2.4 Limits of the Memory Coefficient in Measuring Correlations
9.3 Effects of Correlations Between IETs on Dynamical Processes
9.4 Discussion
References
10 Challenges in Community Discovery on Temporal Networks
10.1 Introduction
10.2 Representing Dynamic Communities
10.2.1 Fixed Membership Cluster in Temporal Networks
10.2.2 Evolving-Membership Clusters in Temporal Networks
10.2.3 Evolving-Membership Clusters with Events
10.2.4 Community Life-Cycle
10.3 Detecting Dynamic Communities
10.3.1 Different Approaches of Temporal Smoothness
10.3.2 Preservation of Identity: The Ship of Theseus Paradox
10.3.3 Scalability and Computational Complexity
10.4 Handling Different Types of Temporal Networks
10.5 Evaluation of Dynamic Communities
10.5.1 Evaluation Methods and Scores
10.5.2 Generating Dynamic Graphs with Communities
10.6 Libraries and Standard Formats to Work with Dynamic Communities
10.7 Conclusion
References
11 Information Diffusion Backbone
11.1 Introduction
11.2 Network Representation
11.3 Shortest Paths in Static Networks
11.3.1 Construction of the Backbone
11.3.2 Network with i.i.d. Polynomial Link Weights
11.3.3 Link Weight Scaling
11.4 SI Spreading Process on Temporal Networks
11.4.1 Construction of the Backbone
11.4.2 Real-World Temporal Networks
11.4.3 Relationship Between Diffusion Backbones
11.4.4 Identifying the Diffusion Backbone GB(1)
11.5 Conclusion and Discussions
References
12 Continuous-Time Random Walks and Temporal Networks
12.1 Introduction
12.2 Models of Graphs and of Temporal Sequences
12.2.1 Random Graphs
12.2.2 Poisson and Renewal Processes
12.3 Trajectories on Networks
12.3.1 Discrete-Time Dynamics
12.3.2 Fourier Modes
12.3.3 Continuous-Time Dynamics
12.4 Diffusion on Temporal Networks
12.4.1 Active Versus Passive Walks
12.4.2 Bus Paradox and Backtracking Transitions
12.5 Perspectives
References
13 Spreading of Infection on Temporal Networks: An Edge-Centered, Contact-Based Perspective
13.1 Introduction
13.2 Discrete-Time Description
13.3 Continuous-Time Description
13.4 Spectral Properties of the Continuous-Time Model
13.5 Relation to the Edge-Based Compartmental Model
13.6 Relation to the Message-Passing Framework
13.7 Summary and Discussion
References
14 The Effect of Concurrency on Epidemic Threshold in Time-Varying Networks
14.1 Introduction
14.2 Model
14.3 Analysis
14.3.1 SIS Dynamics on a Clique and Extinction Effects
14.3.2 Linear Mapping of the Network State Across a Time Window of Length τ
14.3.3 Epidemic Threshold When all Nodes Have the Same Activity Potential
14.3.4 General Activity Distributions
14.4 Clique-Based Activity-Driven Networks with Attractiveness
14.5 Conclusions
References
15 Dynamics and Control of Stochastically Switching Networks: Beyond Fast Switching
15.1 Introduction
15.2 The Blinking Network Model: Continuous-Time Systems
15.2.1 Historical Perspective: Fast Switching Theory
15.2.2 Beyond Fast Switching: A Motivating Example
15.3 Revealing Windows of Opportunity in Two Stochastically Coupled Maps
15.3.1 Network Model
15.3.2 Mean Square Stability of Synchronization
15.3.3 Preliminary Claims
15.3.4 Necessary Condition for Mean Square Synchronization
15.3.5 Chaotic Dynamics
15.3.6 A Representative Example: Coupled Tent Maps
15.4 Network Synchronization Through Stochastic Broadcasting
15.4.1 Tent Maps Revisited
15.4.2 Stochastic Broadcasting: Fast Switching (m = 1)
15.4.3 Stochastic Broadcasting: Beyond Fast Switching (m > 1)
15.5 Conclusions
References
16 The Effects of Local and Global Link Creation Mechanisms on Contagion Processes Unfolding on Time-Varying Networks
16.1 Introduction
16.2 The Activity-Driven Framework
16.2.1 Model 1: Baseline
16.2.2 Model 2: Global Links Formation Process Driven by Popularity
16.2.3 Model 3: Local Links Formation Process Driven by Social Memory
16.2.4 Model 4: Local Links Formation Process Driven by Communities
16.3 Epidemic Spreading on Activity-Driven Networks: Analytical Approach
16.3.1 SIS Epidemic Processes Unfolding on Model 1: Baseline
16.3.2 SIS Epidemic Processes in Model 2: The Effects of Popularity
16.3.3 SIS Epidemic Processes in Model 3: The Effects of Social Memory
16.3.4 SIS Epidemic Processes in Model 4: The Effects of Communities
16.4 Epidemic Spreading on Activity-Driven Networks: Numerical Simulations
16.5 Conclusions
References
17 Supracentrality Analysis of Temporal Networks with Directed Interlayer Coupling
17.1 Introduction
17.2 Background Information
17.2.1 Analysis of Temporal Networks with Multiplex-Network Representations
17.2.2 Eigenvector-Based Centrality for Time-Independent Networks
17.3 Supracentrality Framework
17.3.1 Supracentrality Matrices
17.3.2 Joint, Marginal, and Conditional Centralities
17.4 Application to a Ph.D. Exchange Network
17.5 Asymptotic Behavior for Small and Large Interlayer-Coupling Strength ω
17.5.1 Layer Decoupling in the Limit of Small ω
17.5.2 Layer Aggregation in the Limit of Large ω
17.6 Discussion
References
18 Approximation Methods for Influence Maximization in Temporal Networks
18.1 Introduction
18.2 Related Work
18.2.1 Model of Information Propagation
18.2.2 Problems Related to Influence Maximization in Temporal Networks
18.2.3 Influence Maximization Methods for Static Networks
18.2.4 Degrees in Temporal Networks
18.2.5 Influence Maximization Methods for Temporal Networks
18.3 Proposed Methods
18.3.1 Dynamic Degree Discount
18.3.2 Dynamic CI
18.3.3 Dynamic RIS
18.4 Experiments
18.5 Experimental Results
18.5.1 Comparison of σ(S) When the Size of Seed Nodes k Changes
18.5.2 Comparison of σ(S) When Susceptibility λ Changes
18.5.3 Comparison of Computational Time When the Size of Seed Nodes k Changes
18.5.4 Parameters of Dynamic CI and Dynamic RIS
18.6 Discussion
18.6.1 Analysis Focused on Diffusion of Each Node
18.6.2 Advantages and Disadvantages of Each of Proposed Methods
18.7 Conclusion
References
19 Temporal Link Prediction Methods Based on Behavioral Synchrony
19.1 Introduction
19.2 Problem Statement and Evaluation Metrics
19.2.1 Temporal Link Prediction
19.2.2 Evaluation Metrics
19.3 Related Work
19.3.1 Link Prediction in Static Network
19.3.2 Link Prediction in Temporal Networks
19.4 From Time Decay Function to Time Vector
19.4.1 Neighborhood-based Similarities with a Temporal Logarithmic Decay Function (NSTD) Link Prediction Model
19.4.2 Neighborhood-based Similarities and Temporal Vector (NSTV) Link Prediction Model
19.4.3 Neighborhood-based Similarities with a Temporal Logarithmic Decay Function and Temporal Vector (NSTDV) Link Prediction Model
19.4.4 Neighborhood-based Similarities Temporal Vector for Heterogeneous Time Layer (NSTHV) Link Prediction Model
19.5 Data
19.6 Experiments
19.6.1 Experimental Setup
19.6.2 Experimental Datasets
19.6.3 Experimental Results
19.7 Conclusion
References
20 A Systematic Derivation and Illustration of Temporal Pair-Based Models
20.1 Overview
20.2 Reduced Master Equations
20.3 Network Model
20.3.1 Temporal Individual-Based Model
20.3.2 Temporal Pair-Based Model
20.4 Epidemic Threshold
20.5 Results
20.5.1 Synthetic Networks
20.5.2 Non-backtracking Matrix
20.5.3 Empirical Networks
20.6 Summary
References
21 Modularity-Based Selection of the Number of Slices in Temporal Network Clustering
21.1 Introduction
21.2 Related Work
21.3 Method
21.4 Results
21.4.1 Expected Modularity Increment in Sequentially Duplicated Networks
21.4.2 Synthetic Data Validation
21.4.3 Real Data
21.5 Discussion
References
22 A Frequency-Structure Approach for Link Stream Analysis
22.1 Introduction
22.2 Definitions and Problem Statement
22.2.1 Definitions
22.2.2 Problem Statement
22.3 A Linear Framework for Link Stream Analysis
22.4 Linear Methods for Graphs
22.4.1 A New Decomposition for Graphs
22.4.2 Partitioning of the Relation-Space
22.4.3 Interpretation as Graph Embedding
22.4.4 Filters for Graphs
22.5 Link Stream Analysis
22.5.1 Frequency-Structure Representation of Link Streams
22.5.2 Filters in Link Streams
22.6 Conclusion
22.7 Appendix
22.7.1 Proof of Lemma 22.1
22.7.2 Proof of Lemma 22.2
22.7.3 Proof of Lemma 22.3
22.7.4 Proof of Lemma 22.4
References
Index