Computational Network Theory Theoretical Foundations and Applications

by Dehmer, Matthias; Emmert-streib, Frank; Pickl, Stefan

• ISBN13: 9783527337248
• ISBN10: 3527337245
• Edition: 1st
• Format: Hardcover
• Copyright: 2015-11-16
• Publisher: Wiley-Blackwell

Summary

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.

Author Biography

Matthias Dehmer studied mathematics at the University of Siegen (Germany) and received his Ph.D. in computer science from the Technical University of Darmstadt (Germany). Afterwards, he was a research fellow at Vienna Bio Center (Austria), Vienna University of Technology, and University of Coimbra (Portugal). He obtained his habilitation in applied discrete mathematics from the Vienna University of Technology. Currently, he is Professor at UMIT - The Health and Life Sciences University (Austria) and also holds a position at the Universität der Bundeswehr München. His research interests are in applied mathematics, bioinformatics, systems biology, graph theory, complexity and information theory. He has written over 180 publications in his research areas.

Frank Emmert-Streib studied physics at the University of Siegen (Germany) gaining his PhD in theoretical physics from the University of Bremen (Germany). He received postdoctoral training from the Stowers Institute for Medical Re- search (Kansas City, USA) and the University of Washington (Seattle, USA). Currently, he is an associate professor at the Queen's University Belfast (UK) at the Center for Cancer Research and Cell Biology heading the Computational Biology and Machine Learning Laboratory. His main research interests are in the field of computational medicine, network biology and statistical genomics.

Table of Contents

Color Plates XV

Preface XXXI

List of Contributors XXXIII

1 Model Selection for Neural Network Models: A Statistical Perspective 1
Michele 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 29
Ziyu 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 75
Salissou 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 97
Grzegorz 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 137
Natallia 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 173
Othon 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 219
Matthias 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