Temporal Network Theory (Computational Social Sciences)

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