Mathematical Foundations and Applications of Graph Entropy

by Dehmer, Matthias; Emmert-streib, Frank; Chen, Zengqiang; Li, Xueliang; Shi, Yongtang

• ISBN13: 9783527339099
• ISBN10: 3527339094
• eBook ISBN(s): 9783527693252
• Edition: 1st
• Format: Hardcover
• Copyright: 2017-09-12
• Publisher: Wiley-VCH
• More Book Details

Summary

This latest addition to the successful Network Biology series presents current methods for determining the entropy of networks, making it the first to cover the recently established Quantitative Graph Theory.
An excellent international team of editors and contributors provides an up-to-date outlook for the field, covering a broad range of graph entropy-related concepts and methods. The topics range from analyzing mathematical properties of methods right up to applying them in real-life 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.

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 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.

Table of Contents

List of Contributors XI

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 Period-Doubling Accumulation Point 31

1.3.3 Quasi-Periodicity 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 Quasi-periodicity 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 Distance-Based 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 Sphere-Regular 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 Entropy-Based Texture Descriptors 209

7.2.1 Graph Construction 210

7.2.2 Entropy-Based Graph Indices 211

7.2.2.1 Shannons Entropy 212

7.2.2.2 Bonchev and Trinajsti´cs 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 Real-World Example 220

7.5 Analysis of Graph Entropy-Based 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 Vertex-Weighted 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