This comprehensive introduction to computational network theory as a branch of network theory builds on the understanding that such networks are a tool to derive or verify hypotheses by applying computational techniques to large scale network data.The highly experienced team of editors and high-profile authors from around the world present and explain a number of methods that are representative of computational network theory, derived from graph theory, as well as computational and statistical techniques.With its coherent structure and homogenous style, this reference is equally suitable for courses on computational networks.
Color Plates XV
Preface XXXI
List of Contributors XXXIII
1 Model Selection for Neural Network Models: A Statistical Perspective 1Michele La Rocca and Cira Perna
1.1 Introduction 1
1.2 Feedforward Neural NetworkModels 2
1.3 Model Selection 4
1.3.1 Feature Selection by Relevance Measures 6
1.3.2 Some Numerical Examples 10
1.3.3 Application to Real Data 12
1.4 The Selection of the Hidden Layer Size 14
1.4.1 A Reality Check Approach 15
1.4.2 Numerical Examples by Using the Reality Check 16
1.4.3 Testing Superior Predictive Ability for Neural Network Modeling 19
1.4.4 Some Numerical Results Using Test of Superior Predictive Ability 21
1.4.5 An Application to Real Data 23
1.5 Concluding Remarks 26
References 26
2 Measuring Structural Correlations in Graphs 29Ziyu Guan and Xifeng Yan
2.1 Introduction 29
2.1.1 Solutions for Measuring Structural Correlations 31
2.2 RelatedWork 32
2.3 Self Structural Correlation 34
2.3.1 Problem Formulation 34
2.3.2 The Measure 34
2.3.3 Computing Decayed Hitting Time 37
2.3.4 Assessing SSC 41
2.3.5 Empirical Studies 45
2.3.6 Discussions 51
2.4 Two-Event Structural Correlation 52
2.4.1 Preliminaries and Problem Formulation 52
2.4.2 Measuring TESC 53
2.4.3 Reference Node Sampling 56
2.4.4 Experiments 62
2.4.5 Discussions 70
2.5 Conclusions 72
Acknowledgments 72
References 72
3 Spectral Graph Theory and Structural Analysis of Complex Networks: An Introduction 75Salissou Moutari and Ashraf Ahmed
3.1 Introduction 75
3.2 Graph Theory: Some Basic Concepts 76
3.2.1 Connectivity in Graphs 77
3.2.2 Subgraphs and Special Graphs 80
3.3 MatrixTheory: Some Basic Concepts 81
3.3.1 Trace and Determinant of a Matrix 81
3.3.2 Eigenvalues and Eigenvectors of a Matrix 82
3.4 Graph Matrices 83
3.4.1 Adjacency Matrix 84
3.4.2 Incidence Matrix 84
3.4.3 Degree Matrix and Diffusion Matrix 85
3.4.4 Laplace Matrix 85
3.4.5 Cut-Set Matrix 86
3.4.6 Path Matrix 86
3.5 Spectral Graph Theory: Some Basic Results 86
3.5.1 Spectral Characterization of Graph Connectivity 87
3.5.2 Spectral Characteristics of some Special Graphs and Subgraphs 89
3.5.3 SpectralTheory and Graph Colouring 91
3.5.4 SpectralTheory and Graph Drawing 91
3.6 Computational Challenges for Spectral Graph Analysis 91
3.6.1 Krylov Subspace Methods 91
3.6.2 Constrained Optimization Approach 94
3.7 Conclusion 94
References 95
4 Contagion in Interbank Networks 97Grzegorz Ha?aj and Christoffer Kok
4.1 Introduction 97
4.2 Research Context 99
4.3 Models 103
4.3.1 Simulated Networks 104
4.3.2 Systemic Probability Index 109
4.3.3 Endogenous Networks 110
4.4 Results 119
4.4.1 Data 119
4.4.2 Simulated Networks 120
4.4.3 Structure of Endogenous Interbank Networks 123
4.5 Stress Testing Applications 127
4.6 Conclusions 130
References 131
5 Detection, Localization, and Tracking of a Single and Multiple Targets with Wireless Sensor Networks 137Natallia Katenka
5.1 Introduction and Overview 137
5.2 Data Collection and Fusion by WSN 138
5.3 Target Detection 141
5.3.1 Target Detection from Value Fusion (Energies) 142
5.3.2 Target Detection from Ordinary Decision Fusion 143
5.3.3 Target Detection from Local Vote Decision Fusion 144
5.4 Single Target Localization and Diagnostic 149
5.4.1 Localization and Diagnostic from Value Fusion (Energies) 150
5.4.2 Localization and Diagnostic from Ordinary Decision Fusion 151
5.4.3 Localization and Diagnostic from Local Vote Decision Fusion 152
5.4.4 Hybrid Maximum Likelihood Estimates 153
5.4.5 Properties of Maximum-Likelihood Estimates 154
5.5 Multiple Target Localization and Diagnostic 157
5.5.1 Multiple Target Localization from Energies 158
5.5.2 Multiple Target Localization from Binary Decisions 158
5.5.3 Multiple Target Localization from Corrected Decisions 159
5.6 Multiple Target Tracking 161
5.7 Applications and Case Studies 165
5.7.1 The NEST Project 166
5.7.2 The ZebraNet Project 168
5.8 Final Remarks 170
References 171
6 Computing in Dynamic Networks 173Othon Michail, Ioannis Chatzigiannakis, and Paul G. Spirakis
6.1 Introduction 173
6.1.1 Motivation-State of the Art 173
6.1.2 Structure of the Chapter 177
6.2 Preliminaries 177
6.2.1 The Dynamic Network Model 177
6.2.2 Problem Definitions 179
6.3 Spread of Influence in Dynamic Graphs (Causal Influence) 180
6.4 Naming and Counting in Anonymous Unknown Dynamic Networks 182
6.4.1 Further RelatedWork 183
6.4.2 Static Networks with Broadcast 183
6.4.3 Dynamic Networks with Broadcast 186
6.4.4 Dynamic Networks with One-to-Each 188
6.4.5 Higher Dynamicity 195
6.5 Causality, Influence, and Computation in Possibly Disconnected Synchronous Dynamic Networks 196
6.5.1 Our Metrics 196
6.5.2 Fast Propagation of Information under Continuous Disconnectivity 201
6.5.3 Termination and Computation 203
6.6 Local CommunicationWindows 212
6.7 Conclusions 215
References 216
7 Visualization and Interactive Analysis for Complex Networks by means of Lossless Network Compression 219Matthias Reimann, Loic Royer, Simone Daminelli, and Michael Schroeder
7.1 Introduction 219
7.1.1 Illustrative Example 221
7.2 Power Graph Algorithm 221
7.2.1 Formal Definition of Power Graphs 221
7.2.2 Semantics of Power Graphs 222
7.2.3 Power Graph Conditions 222
7.2.4 Edge Reduction and Relative Edge Reduction 223
7.2.5 Power Graph Extraction 225
7.3 Validation ? Edge Reduction Differs from Random 227
7.4 Graph Comparison with Power Graphs 228
7.5 Excursus: Layout of Power Graphs 229
7.6 Interactive Visual Analytics 231
7.6.1 Power Edge Filtering 232
7.7 Conclusion 234
References 234
Index 237
