Computational network theory : theoretical foundations and applications / edited by Matthias Dehmer, Frank Emmert-Streib and Stefan Pickl.

Format:

Book

Contributor:

Dehmer, Matthias, 1968-

Emmert-Streib, Frank.

Pickl, Stefan, 1967-

Series:

Quantitative and network biology series ; v. 5.

Quantitative and network biology series ; v. 5

Language:

English

Subjects (All):

Computational intelligence.

Physical Description:

xxxiv, 242 pages : illustrations ; 25 cm.

Place of Publication:

Weinheim : Wiley-VCH Verlang GmbH & Co. KGaA, [2015]

Summary:

This comprehensive introduction to computational network theory as a branch of network theory builds on the understanding that such networks are important tools 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 and special aspects of complex network analysis and operations research. Book jacket.

Contents:

1 Model Selection for Neural Network Models: A Statistical Perspective / Michele La Rocca Rocca, Michele La, Cira Perna Perna, Cira 1

1.1 Introduction 1

1.2 Feedforward Neural Network Models 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 / Ziyu Guan Guan, Ziyu, Xifeng Yan Yan, Xifeng 29

2.1 Introduction 29

2.1.1 Solutions for Measuring Structural Correlations 31

2.2 Related Work 32

2.3 Self Structural Correlation 34

2.3.1 Problem Formulation 34

2.3.2 The Measure 34

2.3.2.1 Random Walk and Hitting Time 35

2.3.2.2 Decayed Hitting Time 36

2.3.3 Computing Decayed Hitting Time 37

2.3.3.1 Iterative Approximation 37

2.3.3.2 A Sampling Algorithm for h(v_i, B) 39

2.3.3.3 Complexity 40

2.3.4 Assessing SSC 41

2.3.4.1 Estimating ρ(V_q) 41

2.3.4.2 Estimating the Significance of ρ(V_q) 42

2.3.5 Empirical Studies 45

2.3.5.1 Datasets 45

2.3.5.2 Performance of DHT Approximation 45

2.3.5.3 Effectiveness on Synthetic Events 47

2.3.5.4 SSC of Real Event 49

2.3.5.5 Scalability of Sampling-alg 51

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.2.1 The Test 54

2.4.2.2 Reference Nodes 56

2.4.3 Reference Node Sampling 56

2.4.3.1 Batch_BFS 57

2.4.3.2 Importance Sampling 58

2.4.3.3 Global Sampling in Whole Graph 61

2.4.3.4 Complexity Analysis 61

2.4.4 Experiments 62

2.4.4.1 Graph Datasets 62

2.4.4.2 Event Simulation Methodology 63

2.4.4.3 Performance Comparison 63

2.4.4.4 Batch Importance Sampling 65

2.4.4.5 Impact of Graph Density 66

2.4.4.6 Efficiency and Scalability 66

2.4.4.7 Real Events 68

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 / Salissou Moutari Moutari, Salissou, Ashraf Ahmed Ahmed, Ashraf 75

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 Matrix Theory: 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.1.1 Spectral Theory and Walks 88

3.5.2 Spectral Characteristics of some Special Graphs and Subgraphs 89

3.5.2.1 Tree 89

3.5.2.2 Bipartite Graph 89

3.5.2.3 Complete Graph 90

3.5.2.4 Regular Graph 90

3.5.2.5 Line Graph 90

3.5.3 Spectral Theory and Graph Colouring 91

3.5.4 Spectral Theory 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 / Grzegorz Halaj Halaj, Grzegorz, Christoffer Kok Kok, Christoffer 97

4.1 Introduction 97

4.2 Research Context 99

4.3 Models 103

4.3.1 Simulated Networks 104

4.3.1.1 Probability Map 105

4.3.1.2 Interbank Network 105

4.3.1.3 Contagion Mechanism 107

4.3.1.4 Fire sales of Illiquid Portfolio 108

4.3.2 Systemic Probability Index 109

4.3.3 Endogenous Networks 110

4.3.3.1 Banks 113

4.3.3.2 First Round-Optimization of Interbank Assets 115

4.3.3.3 Second Round-Accepting Placements According to Funding Needs 116

4.3.3.4 Third Round-Bargaining Game 117

4.3.3.5 Fourth Round-Price Adjustments 118

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 / Natallia Katenka Katenka, Natallia 137

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.3.3.1 Remark 1: LVDF Fixed Neighbourhood Size 145

5.3.3.2 Remark 2: LVDF Regular Grids 146

5.3.3.3 Remark 3: Quality of Approximation 148

5.3.3.4 Remark 4: Detection Performance 148

5.3.3.5 Concluding Remarks 148

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.4.5.1 Remark 1: Accuracy of Target Localization 155

5.4.5.2 Remark 2: Starting Values for Localization 155

5.4.5.3 Remark 3: Robustness to Model Misspecification 156

5.4.5.4 Remark 4: Computational Cost 156

5.4.5.5 Concluding Remarks 157

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.5.3.1 Remark 1: Hybrid Estimation 160

5.5.3.2 Remark 2: Starting Values 160

5.5.3.3 Estimating the Number of Targets 160

5.5.3.4 Concluding Remarks 160

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 / Othon Michail Michail, Othon, Ioannis Chatzigiannakis Chatzigiannakis, Ioannis, Paul G.

Spirakis Spirakis, Paul G. 173

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 Related Work 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.1.1 The Influence Time 196

6.5.1.2 The Moi (Concurrent Progress) 199

6.5.1.3 The Connectivity Time 200

6.5.2 Fast Propagation of Information under Continuous Disconnectivity 201

6.5.3 Termination and Computation 203

6.5.3.1 Nodes Know an Upper Bound on the ct: An Optimal Termination Criterion 204

6.5.3.2 Known Upper Bound on the oit 205

6.5.3.3 Hearing the Future 208

6.6 Local Communication Windows 212

6.7 Conclusions 215

References 216

7 Visualization and Interactive Analysis for Complex Networks by means of Lossless Network Compression / Matthias Reimann Reimann, Matthias, Loïc Royer Royer, Loïc, Simone Daminelli Daminelli, Simone, Michael Schroeder Schroeder, Michael 219

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.6.1.1 Zooming and Network Expansion 233

7.7 Conclusion 234

References 234.

Notes:

Includes bibliographical references and index.

ISBN:

9783527337248

3527337245

OCLC:

898923772