Mathematical Foundations and Applications of Graph EntropyISBN: 9783527339099
296 pages
September 2017

Description
An excellent international team of editors and contributors provides an uptodate outlook for the field, covering a broad range of graph entropyrelated concepts and methods. The topics range from analyzing mathematical properties of methods right up to applying them in reallife areas.
Filling a gap in the contemporary literature this is an invaluable reference for a number of disciplines, including mathematicians, computer scientists, computational biologists, and structural chemists.
Table of Contents
Preface XV
1 Entropy and Renormalization in Chaotic Visibility Graphs 1
Bartolo Luque, Fernando Jesús Ballesteros, Alberto Robledo, and Lucas Lacasa
1.1 Mapping Time Series to Networks 2
1.1.1 Natural and Horizontal Visibility Algorithms 4
1.1.2 A Brief Overview of Some Initial Applications 8
1.1.2.1 Seismicity 8
1.1.2.2 Hurricanes 8
1.1.2.3 Turbulence 9
1.1.2.4 Financial Applications 9
1.1.2.5 Physiology 9
1.2 Visibility Graphs and Entropy 10
1.2.1 Definitions of Entropy in Visibility Graphs 10
1.2.2 Pesin Theorem in Visibility Graphs 12
1.2.3 Graph Entropy Optimization and Critical Points 19
1.3 Renormalization Group Transformations of Horizontal Visibility Graphs 26
1.3.1 Tangent Bifurcation 29
1.3.2 PeriodDoubling Accumulation Point 31
1.3.3 QuasiPeriodicity 32
1.3.4 Entropy Extrema and RG Transformation 34
1.3.4.1 Intermittency 35
1.3.4.2 Period Doubling 35
1.3.4.3 Quasiperiodicity 35
1.4 Summary 36
1.5 Acknowledgments 37
References 37
2 Generalized Entropies of Complex and Random Networks 41
Vladimir Gudkov
2.1 Introduction 41
2.2 Generalized Entropies 42
2.3 Entropy of Networks: Definition and Properties 43
2.4 Application of Generalized Entropy for Network Analysis 45
2.5 Open Networks 53
2.6 Summary 59
References 60
3 Information Flow and Entropy Production on Bayesian Networks 63
Sosuke Ito and Takahiro Sagawa
3.1 Introduction 63
3.1.1 Background 63
3.1.2 Basic Ideas of Information Thermodynamics 64
3.1.3 Outline of this Chapter 65
3.2 Brief Review of Information Contents 66
3.2.1 Shannon Entropy 66
3.2.2 Relative Entropy 67
3.2.3 Mutual Information 68
3.2.4 Transfer Entropy 69
3.3 StochasticThermodynamics for Markovian Dynamics 70
3.3.1 Setup 70
3.3.2 Energetics 72
3.3.3 Entropy Production and Fluctuation Theorem 73
3.4 Bayesian Networks 76
3.5 Information Thermodynamics on Bayesian Networks 79
3.5.1 Setup 79
3.5.2 Information Contents on Bayesian Networks 80
3.5.3 Entropy Production 83
3.5.4 Generalized Second Law 84
3.6 Examples 86
3.6.1 Example 1: Markov Chain 86
3.6.2 Example 2: Feedback Control with a Single Measurement 86
3.6.3 Example 3: Repeated Feedback Control with Multiple Measurements 89
3.6.4 Example 4: Markovian Information Exchanges 91
3.6.5 Example 5: Complex Dynamics 94
3.7 Summary and Prospects 95
References 96
4 Entropy, Counting, and Fractional Chromatic Number 101
Seyed Saeed Changiz Rezaei
4.1 Entropy of a Random Variable 102
4.2 Relative Entropy and Mutual Information 104
4.3 Entropy and Counting 104
4.4 Graph Entropy 107
4.5 Entropy of a Convex Corner 107
4.6 Entropy of a Graph 108
4.7 Basic Properties of Graph Entropy 110
4.8 Entropy of Some Special Graphs 112
4.9 Graph Entropy and Fractional Chromatic Number 116
4.10 Symmetric Graphs with respect to Graph Entropy 119
4.11 Conclusion 120
Appendix 4.A 121
References 130
5 Graph Entropy: Recent Results and Perspectives 133
Xueliang Li and MeiqinWei
5.1 Introduction 133
5.2 Inequalities and Extremal Properties on (Generalized) Graph Entropies 139
5.2.1 Inequalities for Classical Graph Entropies and Parametric Measures 139
5.2.2 Graph Entropy Inequalities with Information Functions f V , f P and f C 141
5.2.3 Information Theoretic Measures of UHG Graphs 143
5.2.4 Bounds for the Entropies of Rooted Trees and Generalized Trees 146
5.2.5 Information Inequalities for If (G) based on Different Information Functions 148
5.2.6 Extremal Properties of Degree and DistanceBased Graph Entropies 153
5.2.7 Extremality of If �� (G), If 2 (G) If 3 (G) and Entropy Bounds for Dendrimers 157
5.2.8 SphereRegular Graphs and the Extremality Entropies If 2 (G) and If �� (G) 163
5.2.9 Information Inequalities for Generalized Graph Entropies 166
5.3 Relationships between Graph Structures, Graph Energies, Topological Indices, and Generalized Graph Entropies 171
5.4 Summary and Conclusion 179
References 180
6 Statistical Methods in Graphs: Parameter Estimation, Model Selection, and Hypothesis Test 183
Suzana de Siqueira Santos, Daniel Yasumasa Takahashi, João Ricardo Sato, Carlos Eduardo Ferreira, and André Fujita
6.1 Introduction 183
6.2 Random Graphs 184
6.3 Graph Spectrum 187
6.4 Graph Spectral Entropy 189
6.5 Kullback Leibler Divergence 192
6.6 Jensen Shannon Divergence 192
6.7 Model Selection and Parameter Estimation 193
6.8 Hypothesis Test between Graph Collections 195
6.9 Final Considerations 198
6.9.1 Model Selection for Protein Protein Networks 199
6.9.2 Hypothesis Test between the Spectral Densities of Functional Brain Networks 200
6.9.3 Entropy of Brain Networks 200
6.10 Conclusions 200
6.11 Acknowledgments 201
References 201
7 Graph Entropies in Texture Segmentation of Images 203
Martin Welk
7.1 Introduction 203
7.1.1 Structure of the Chapter 203
7.1.2 Quantitative Graph Theory 204
7.1.3 Graph Models in Image Analysis 205
7.1.4 Texture 206
7.1.4.1 Complementarity of Texture and Shape 206
7.1.4.2 Texture Models 207
7.1.4.3 Texture Segmentation 208
7.2 Graph EntropyBased Texture Descriptors 209
7.2.1 Graph Construction 210
7.2.2 EntropyBased Graph Indices 211
7.2.2.1 Shannon s Entropy 212
7.2.2.2 Bonchev and Trinajsti´c s Mean Information on Distances 212
7.2.2.3 Dehmer Entropies 213
7.3 Geodesic Active Contours 214
7.3.1 Basic GAC Evolution for Grayscale Images 214
7.3.2 Force Terms 215
7.3.3 Multichannel Images 216
7.3.4 Remarks on Numerics 216
7.4 Texture Segmentation Experiments 217
7.4.1 First Synthetic Example 217
7.4.2 Second Synthetic Example 218
7.4.3 RealWorld Example 220
7.5 Analysis of Graph EntropyBased Texture Descriptors 221
7.5.1 Rewriting the Information Functionals 221
7.5.2 Infinite Resolution Limits of Graphs 222
7.5.3 Fractal Analysis 223
7.6 Conclusion 226
References 227
8 Information Content Measures and Prediction of Physical Entropy of Organic Compounds 233
Chandan Raychaudhury and Debnath Pal
8.1 Introduction 233
8.2 Method 236
8.2.1 Information Content Measures 236
8.2.2 Information Content of Partition of a Positive Integer 240
8.2.3 Information Content of Graph 243
8.2.3.1 Information Content of Graph on Vertex Degree 245
8.2.3.2 Information Content of Graph on Topological Distances 246
8.2.3.3 Information Content of VertexWeighted Graph 251
8.2.4 Information Content on the Shortest Molecular Path 251
8.2.4.1 Computation of Example Indices 252
8.3 Prediction of Physical Entropy 253
8.3.1 Prediction of Entropy using InformationTheoretical Indices 254
8.4 Conclusion 256
8.5 Acknowledgment 257
References 257
9 Application of Graph Entropy for Knowledge Discovery and Data Mining in Bibliometric Data 259
André Calero Valdez, Matthias Dehmer, and Andreas Holzinger
9.1 Introduction 259
9.1.1 Challenges in Bibliometric Data Sets, or Why ShouldWe Consider Entropy Measures? 260
9.1.2 Structure of this Chapter 261
9.2 State of the Art 261
9.2.1 Graphs and Text Mining 262
9.2.2 Graph Entropy for Data Mining and Knowledge Discovery 263
9.2.3 Graphs from Bibliometric Data 264
9.3 Identifying Collaboration Styles using Graph Entropy from Bibliometric Data 266
9.4 Method and Materials 266
9.5 Results 267
9.6 Discussion and Future Outlook 271
9.6.1 Open Problems 271
9.6.2 A PoliteWarning 272
References 272
Index 275
Author Information
Frank EmmertStreib 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.