Spatio-Temporal Graph Data Analytics (eBook)

Preface 5
Acknowledgements 7
Contents 8
1 Introduction 10
1.1 Urban Road Networks 10
1.2 Social Networks 12
2 Fundamental Concepts for Spatio-Temporal Graphs 14
2.1 Road Network Datasets 14
2.1.1 Key Concepts in Road Network Datasets 15
2.1.2 Data-Collection vs Querying Reference Frame in Road Networks 17
2.2 Social Network Datasets 18
2.2.1 Key Concepts in Social Network Datasets 18
2.3 Conclusion 20
3 Representational Models for Spatio-Temporal Graphs 21
3.1 Models at Conceptual Level 21
3.1.1 Lagrangian Xgraphs 24
3.2 Data Structures for Algorithms 26
3.2.1 Temporal Digraphs 27
3.2.2 Temporal Digraphs for Holistic Properties and TurnDelays 29
3.3 Conclusion 31
4 Fastest Path for a Single Departure-Time 32
4.1 Problem Definition 32
4.1.1 Important Considerations 33
4.2 Dijkstra's Algorithm for the Fastest Path Problem 35
4.2.1 Latest Departure Path Problem 37
4.3 A* Search for the Fastest Path Problem 39
4.3.1 Using Lower Bound on Travel-Time 39
4.3.2 Using a Hierarchical Lower Bound on Travel-Time 40
4.4 Bi-directional Search for the Fastest Path Problem 43
4.5 Adapting Fastest Path Algorithm for Centrality Metrics 46
4.6 Conclusions 47
5 Advanced Concepts: Critical Time Point Based Approaches 49
5.1 Formal Problem Definition 51
5.2 Computational Structure of the ALSP Problem 52
5.3 Critical Time-Point Based ALSP Solver (CTAS) 54
5.3.1 CTAS Algorithm 54
5.3.2 Execution Trace 56
5.4 Correctness and Completeness CTAS Algorithm 58
5.5 Experimental Evaluation of CTAS 60
5.6 Conclusions 63
6 Advanced Concepts: Bi-Directional Search for Temporal Digraphs 64
6.1 Computational Structure of Temporal Bi-Directional Search 65
6.1.1 Forward Search Basic Concepts 66
6.1.2 Trace Search Basic Concepts 68
6.2 Temporal Bi-Directional Search for ALSP Problem 70
6.2.1 BD-CTAS Algorithm 73
6.3 Analytical Analysis of Temporal Bi-Directional Search 78
6.3.1 Correctness of BD-CTAS Algorithm 78
6.4 Conclusion 80
7 Knowledge Discovery: Temporal Disaggregation in Social Interaction Data 81
7.1 Basic Concepts and Problem Definition 82
7.2 Formation of Temporal Paths in TDSN 84
7.3 Community Identification in TDSNs 86
7.3.1 Approach for the Detection of Transient Communities 87
7.3.2 Running Example for Transient Community Detection 87
7.4 Node Influence Measures in TDSNs 89
7.4.1 Temporal Katz Centrality 89
7.5 Case Study on TDSN 90
7.5.1 Metric used for Experimentation 91
7.5.2 Experiment 1 92
7.5.3 Experiment 2 93
7.5.4 Experiment 3 94
7.6 Conclusion 95
8 Trend Topics: Engine Data Analytics 96
8.1 Statistically Significant Hot Route Discovery 96
8.1.1 Potential Next Steps 98
8.2 Conclusion 99
References 100