Computational Network Theory

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.

• Color Plates XVPreface XXXIList of Contributors XXXIII1 Model Selection for Neural Network Models: A Statistical Perspective 1Michele La Rocca and Cira Perna1.1 Introduction 11.2 Feedforward Neural NetworkModels 21.3 Model Selection 41.3.1 Feature Selection by Relevance Measures 61.3.2 Some Numerical Examples 101.3.3 Application to Real Data 121.4 The Selection of the Hidden Layer Size 141.4.1 A Reality Check Approach 151.4.2 Numerical Examples by Using the Reality Check 161.4.3 Testing Superior Predictive Ability for Neural Network Modeling 191.4.4 Some Numerical Results Using Test of Superior Predictive Ability 211.4.5 An Application to Real Data 231.5 Concluding Remarks 26References 262 Measuring Structural Correlations in Graphs 29Ziyu Guan and Xifeng Yan2.1 Introduction 292.1.1 Solutions for Measuring Structural Correlations 312.2 RelatedWork 322.3 Self Structural Correlation 342.3.1 Problem Formulation 342.3.2 The Measure 342.3.3 Computing Decayed Hitting Time 372.3.4 Assessing SSC 412.3.5 Empirical Studies 452.3.6 Discussions 512.4 Two-Event Structural Correlation 522.4.1 Preliminaries and Problem Formulation 522.4.2 Measuring TESC 532.4.3 Reference Node Sampling 562.4.4 Experiments 622.4.5 Discussions 702.5 Conclusions 72Acknowledgments 72References 723 Spectral Graph Theory and Structural Analysis of Complex Networks: An Introduction 75Salissou Moutari and Ashraf Ahmed3.1 Introduction 753.2 Graph Theory: Some Basic Concepts 763.2.1 Connectivity in Graphs 773.2.2 Subgraphs and Special Graphs 803.3 MatrixTheory: Some Basic Concepts 813.3.1 Trace and Determinant of a Matrix 813.3.2 Eigenvalues and Eigenvectors of a Matrix 823.4 Graph Matrices 833.4.1 Adjacency Matrix 843.4.2 Incidence Matrix 843.4.3 Degree Matrix and Diffusion Matrix 853.4.4 Laplace Matrix 853.4.5 Cut-Set Matrix 863.4.6 Path Matrix 863.5 Spectral Graph Theory: Some Basic Results 863.5.1 Spectral Characterization of Graph Connectivity 873.5.2 Spectral Characteristics of some Special Graphs and Subgraphs 893.5.3 SpectralTheory and Graph Colouring 913.5.4 SpectralTheory and Graph Drawing 913.6 Computational Challenges for Spectral Graph Analysis 913.6.1 Krylov Subspace Methods 913.6.2 Constrained Optimization Approach 943.7 Conclusion 94References 954 Contagion in Interbank Networks 97Grzegorz Ha³aj and Christoffer Kok4.1 Introduction 974.2 Research Context 994.3 Models 1034.3.1 Simulated Networks 1044.3.2 Systemic Probability Index 1094.3.3 Endogenous Networks 1104.4 Results 1194.4.1 Data 1194.4.2 Simulated Networks 1204.4.3 Structure of Endogenous Interbank Networks 1234.5 Stress Testing Applications 1274.6 Conclusions 130References 1315 Detection, Localization, and Tracking of a Single and Multiple Targets with Wireless Sensor Networks 137Natallia Katenka5.1 Introduction and Overview 1375.2 Data Collection and Fusion by WSN 1385.3 Target Detection 1415.3.1 Target Detection from Value Fusion (Energies) 1425.3.2 Target Detection from Ordinary Decision Fusion 1435.3.3 Target Detection from Local Vote Decision Fusion 1445.4 Single Target Localization and Diagnostic 1495.4.1 Localization and Diagnostic from Value Fusion (Energies) 1505.4.2 Localization and Diagnostic from Ordinary Decision Fusion 1515.4.3 Localization and Diagnostic from Local Vote Decision Fusion 1525.4.4 Hybrid Maximum Likelihood Estimates 1535.4.5 Properties of Maximum-Likelihood Estimates 1545.5 Multiple Target Localization and Diagnostic 1575.5.1 Multiple Target Localization from Energies 1585.5.2 Multiple Target Localization from Binary Decisions 1585.5.3 Multiple Target Localization from Corrected Decisions 1595.6 Multiple Target Tracking 1615.7 Applications and Case Studies 1655.7.1 The NEST Project 1665.7.2 The ZebraNet Project 1685.8 Final Remarks 170References 1716 Computing in Dynamic Networks 173Othon Michail, Ioannis Chatzigiannakis, and Paul G. Spirakis6.1 Introduction 1736.1.1 Motivation-State of the Art 1736.1.2 Structure of the Chapter 1776.2 Preliminaries 1776.2.1 The Dynamic Network Model 1776.2.2 Problem Definitions 1796.3 Spread of Influence in Dynamic Graphs (Causal Influence) 1806.4 Naming and Counting in Anonymous Unknown Dynamic Networks 1826.4.1 Further RelatedWork 1836.4.2 Static Networks with Broadcast 1836.4.3 Dynamic Networks with Broadcast 1866.4.4 Dynamic Networks with One-to-Each 1886.4.5 Higher Dynamicity 1956.5 Causality, Influence, and Computation in Possibly Disconnected Synchronous Dynamic Networks 1966.5.1 Our Metrics 1966.5.2 Fast Propagation of Information under Continuous Disconnectivity 2016.5.3 Termination and Computation 2036.6 Local CommunicationWindows 2126.7 Conclusions 215References 2167 Visualization and Interactive Analysis for Complex Networks by means of Lossless Network Compression 219Matthias Reimann, Loic Royer, Simone Daminelli, and Michael Schroeder7.1 Introduction 2197.1.1 Illustrative Example 2217.2 Power Graph Algorithm 2217.2.1 Formal Definition of Power Graphs 2217.2.2 Semantics of Power Graphs 2227.2.3 Power Graph Conditions 2227.2.4 Edge Reduction and Relative Edge Reduction 2237.2.5 Power Graph Extraction 2257.3 Validation – Edge Reduction Differs from Random 2277.4 Graph Comparison with Power Graphs 2287.5 Excursus: Layout of Power Graphs 2297.6 Interactive Visual Analytics 2317.6.1 Power Edge Filtering 2327.7 Conclusion 234References 234Index 237

"The authors 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 homogeneous style, this reference is equally suitable for courses on computational networks." (Zentralblatt MATH 2016)