Mathematical Foundations and Applications of Graph Entropy

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 Research (Kansas City, USA) and the University of Washington (Seattle, USA). Currently, he is associate professor for Computational Biology at Tampere University of Technology (Finland). His main research interests are in the field of computational medicine, network biology and statistical genomics.

• List of Contributors XI Preface XV1 Entropy and Renormalization in Chaotic Visibility Graphs 1Bartolo Luque, Fernando Jesús Ballesteros, Alberto Robledo, and Lucas Lacasa1.1 Mapping Time Series to Networks 21.1.1 Natural and Horizontal Visibility Algorithms 41.1.2 A Brief Overview of Some Initial Applications 81.1.2.1 Seismicity 81.1.2.2 Hurricanes 81.1.2.3 Turbulence 91.1.2.4 Financial Applications 91.1.2.5 Physiology 91.2 Visibility Graphs and Entropy 101.2.1 Definitions of Entropy in Visibility Graphs 101.2.2 Pesin Theorem in Visibility Graphs 121.2.3 Graph Entropy Optimization and Critical Points 191.3 Renormalization Group Transformations of Horizontal Visibility Graphs 261.3.1 Tangent Bifurcation 291.3.2 Period-Doubling Accumulation Point 311.3.3 Quasi-Periodicity 321.3.4 Entropy Extrema and RG Transformation 341.3.4.1 Intermittency 351.3.4.2 Period Doubling 351.3.4.3 Quasi-periodicity 351.4 Summary 361.5 Acknowledgments 37References 372 Generalized Entropies of Complex and Random Networks 41Vladimir Gudkov2.1 Introduction 412.2 Generalized Entropies 422.3 Entropy of Networks: Definition and Properties 432.4 Application of Generalized Entropy for Network Analysis 452.5 Open Networks 532.6 Summary 59References 603 Information Flow and Entropy Production on Bayesian Networks 63Sosuke Ito and Takahiro Sagawa3.1 Introduction 633.1.1 Background 633.1.2 Basic Ideas of Information Thermodynamics 643.1.3 Outline of this Chapter 653.2 Brief Review of Information Contents 663.2.1 Shannon Entropy 663.2.2 Relative Entropy 673.2.3 Mutual Information 683.2.4 Transfer Entropy 693.3 StochasticThermodynamics for Markovian Dynamics 703.3.1 Setup 703.3.2 Energetics 723.3.3 Entropy Production and Fluctuation Theorem 733.4 Bayesian Networks 763.5 Information Thermodynamics on Bayesian Networks 793.5.1 Setup 793.5.2 Information Contents on Bayesian Networks 803.5.3 Entropy Production 833.5.4 Generalized Second Law 843.6 Examples 863.6.1 Example 1: Markov Chain 863.6.2 Example 2: Feedback Control with a Single Measurement 863.6.3 Example 3: Repeated Feedback Control with Multiple Measurements 893.6.4 Example 4: Markovian Information Exchanges 913.6.5 Example 5: Complex Dynamics 943.7 Summary and Prospects 95References 964 Entropy, Counting, and Fractional Chromatic Number 101Seyed Saeed Changiz Rezaei4.1 Entropy of a Random Variable 1024.2 Relative Entropy and Mutual Information 1044.3 Entropy and Counting 1044.4 Graph Entropy 1074.5 Entropy of a Convex Corner 1074.6 Entropy of a Graph 1084.7 Basic Properties of Graph Entropy 1104.8 Entropy of Some Special Graphs 1124.9 Graph Entropy and Fractional Chromatic Number 1164.10 Symmetric Graphs with respect to Graph Entropy 1194.11 Conclusion 120Appendix 4.A 121References 1305 Graph Entropy: Recent Results and Perspectives 133Xueliang Li and MeiqinWei5.1 Introduction 1335.2 Inequalities and Extremal Properties on (Generalized) Graph Entropies 1395.2.1 Inequalities for Classical Graph Entropies and Parametric Measures 1395.2.2 Graph Entropy Inequalities with Information Functions f V , f P and f C 1415.2.3 Information Theoretic Measures of UHG Graphs 1435.2.4 Bounds for the Entropies of Rooted Trees and Generalized Trees 1465.2.5 Information Inequalities for If (G) based on Different Information Functions 1485.2.6 Extremal Properties of Degree- and Distance-Based Graph Entropies 1535.2.7 Extremality of If �� (G), If 2 (G) If 3 (G) and Entropy Bounds for Dendrimers 1575.2.8 Sphere-Regular Graphs and the Extremality Entropies If 2 (G) and If �� (G) 1635.2.9 Information Inequalities for Generalized Graph Entropies 1665.3 Relationships between Graph Structures, Graph Energies, Topological Indices, and Generalized Graph Entropies 1715.4 Summary and Conclusion 179References 1806 Statistical Methods in Graphs: Parameter Estimation, Model Selection, and Hypothesis Test 183Suzana de Siqueira Santos, Daniel Yasumasa Takahashi, João Ricardo Sato, Carlos Eduardo Ferreira, and André Fujita6.1 Introduction 1836.2 Random Graphs 1846.3 Graph Spectrum 1876.4 Graph Spectral Entropy 1896.5 Kullback–Leibler Divergence 1926.6 Jensen–Shannon Divergence 1926.7 Model Selection and Parameter Estimation 1936.8 Hypothesis Test between Graph Collections 1956.9 Final Considerations 1986.9.1 Model Selection for Protein–Protein Networks 1996.9.2 Hypothesis Test between the Spectral Densities of Functional Brain Networks 2006.9.3 Entropy of Brain Networks 2006.10 Conclusions 2006.11 Acknowledgments 201References 2017 Graph Entropies in Texture Segmentation of Images 203Martin Welk7.1 Introduction 2037.1.1 Structure of the Chapter 2037.1.2 Quantitative Graph Theory 2047.1.3 Graph Models in Image Analysis 2057.1.4 Texture 2067.1.4.1 Complementarity of Texture and Shape 2067.1.4.2 Texture Models 2077.1.4.3 Texture Segmentation 2087.2 Graph Entropy-Based Texture Descriptors 2097.2.1 Graph Construction 2107.2.2 Entropy-Based Graph Indices 2117.2.2.1 Shannon�s Entropy 2127.2.2.2 Bonchev and Trinajsti´c�s Mean Information on Distances 2127.2.2.3 Dehmer Entropies 2137.3 Geodesic Active Contours 2147.3.1 Basic GAC Evolution for Grayscale Images 2147.3.2 Force Terms 2157.3.3 Multichannel Images 2167.3.4 Remarks on Numerics 2167.4 Texture Segmentation Experiments 2177.4.1 First Synthetic Example 2177.4.2 Second Synthetic Example 2187.4.3 Real-World Example 2207.5 Analysis of Graph Entropy-Based Texture Descriptors 2217.5.1 Rewriting the Information Functionals 2217.5.2 Infinite Resolution Limits of Graphs 2227.5.3 Fractal Analysis 2237.6 Conclusion 226References 2278 Information Content Measures and Prediction of Physical Entropy of Organic Compounds 233Chandan Raychaudhury and Debnath Pal8.1 Introduction 2338.2 Method 2368.2.1 Information Content Measures 2368.2.2 Information Content of Partition of a Positive Integer 2408.2.3 Information Content of Graph 2438.2.3.1 Information Content of Graph on Vertex Degree 2458.2.3.2 Information Content of Graph on Topological Distances 2468.2.3.3 Information Content of Vertex-Weighted Graph 2518.2.4 Information Content on the Shortest Molecular Path 2518.2.4.1 Computation of Example Indices 2528.3 Prediction of Physical Entropy 2538.3.1 Prediction of Entropy using InformationTheoretical Indices 2548.4 Conclusion 2568.5 Acknowledgment 257References 2579 Application of Graph Entropy for Knowledge Discovery and Data Mining in Bibliometric Data 259André Calero Valdez, Matthias Dehmer, and Andreas Holzinger9.1 Introduction 2599.1.1 Challenges in Bibliometric Data Sets, or Why ShouldWe Consider Entropy Measures? 2609.1.2 Structure of this Chapter 2619.2 State of the Art 2619.2.1 Graphs and Text Mining 2629.2.2 Graph Entropy for Data Mining and Knowledge Discovery 2639.2.3 Graphs from Bibliometric Data 2649.3 Identifying Collaboration Styles using Graph Entropy from Bibliometric Data 2669.4 Method and Materials 2669.5 Results 2679.6 Discussion and Future Outlook 2719.6.1 Open Problems 2719.6.2 A PoliteWarning 272References 272Index 275