Mathematical foundations and applications of graph entropy

Cover......Page 1
Title Page......Page 5
Copyright......Page 6
Contents......Page 7
List of Contributors......Page 13
Preface......Page 17
Chapter 1 Entropy and Renormalization in Chaotic Visibility Graphs......Page 19
 1.1 Mapping Time Series to Networks......Page 20
  1.1.1 Natural and Horizontal Visibility Algorithms......Page 22
   1.1.2.2 Hurricanes......Page 26
   1.1.2.5 Physiology......Page 27
  1.2.1 Definitions of Entropy in Visibility Graphs......Page 28
  1.2.2 Pesin Theorem in Visibility Graphs......Page 30
  1.2.3 Graph Entropy Optimization and Critical Points......Page 37
 1.3 Renormalization Group Transformations of Horizontal Visibility Graphs......Page 44
  1.3.1 Tangent Bifurcation......Page 47
  1.3.2 Period-Doubling Accumulation Point......Page 49
  1.3.3 Quasi-Periodicity......Page 50
  1.3.4 Entropy Extrema and RG Transformation......Page 52
   1.3.4.3 Quasi-periodicity......Page 53
 1.4 Summary......Page 54
 References......Page 55
 2.1 Introduction......Page 59
 2.2 Generalized Entropies......Page 60
 2.3 Entropy of Networks: Definition and Properties......Page 61
 2.4 Application of Generalized Entropy for Network Analysis......Page 63
 2.5 Open Networks......Page 71
 2.6 Summary......Page 77
 References......Page 78
  3.1.1 Background......Page 81
  3.1.2 Basic Ideas of Information Thermodynamics......Page 82
  3.1.3 Outline of this Chapter......Page 83
  3.2.1 Shannon Entropy......Page 84
  3.2.2 Relative Entropy......Page 85
  3.2.3 Mutual Information......Page 86
  3.2.4 Transfer Entropy......Page 87
  3.3.1 Setup......Page 88
  3.3.2 Energetics......Page 90
  3.3.3 Entropy Production and Fluctuation Theorem......Page 91
 3.4 Bayesian Networks......Page 94
  3.5.1 Setup......Page 97
  3.5.2 Information Contents on Bayesian Networks......Page 98
  3.5.3 Entropy Production......Page 101
  3.5.4 Generalized Second Law......Page 102
  3.6.2 Example 2: Feedback Control with a Single Measurement......Page 104
  3.6.3 Example 3: Repeated Feedback Control with Multiple Measurements......Page 107
  3.6.4 Example 4: Markovian Information Exchanges......Page 109
  3.6.5 Example 5: Complex Dynamics......Page 112
 3.7 Summary and Prospects......Page 113
 References......Page 114
Chapter 4 Entropy, Counting, and Fractional Chromatic Number......Page 119
 4.1 Entropy of a Random Variable......Page 120
 4.3 Entropy and Counting......Page 122
 4.5 Entropy of a Convex Corner......Page 125
 4.6 Entropy of a Graph......Page 126
 4.7 Basic Properties of Graph Entropy......Page 128
 4.8 Entropy of Some Special Graphs......Page 130
 4.9 Graph Entropy and Fractional Chromatic Number......Page 134
 4.10 Symmetric Graphs with respect to Graph Entropy......Page 137
 4.11 Conclusion......Page 138
 Appendix 4.A......Page 139
 References......Page 148
 5.1 Introduction......Page 151
  5.2.1 Inequalities for Classical Graph Entropies and Parametric Measures......Page 157
  5.2.2 Graph Entropy Inequalities with Information Functions fV, fP and fC......Page 159
  5.2.3 Information Theoretic Measures of UHG Graphs......Page 161
  5.2.4 Bounds for the Entropies of Rooted Trees and Generalized Trees......Page 164
  5.2.5 Information Inequalities for If(G) based on Different Information Functions......Page 166
  5.2.6 Extremal Properties of Degree- and Distance-Based Graph Entropies......Page 171
  5.2.7 Extremality of If��(G), If2(G), If3(G) and Entropy Bounds for Dendrimers......Page 175
  5.2.8 Sphere-Regular Graphs and the Extremality Entropies If2 and If��(G)......Page 181
  5.2.9 Information Inequalities for Generalized Graph Entropies......Page 184
 5.3 Relationships between Graph Structures, Graph Energies, Topological Indices, and Generalized Graph Entropies......Page 189
 5.4 Summary and Conclusion......Page 197
 References......Page 198
 6.1 Introduction......Page 201
 6.2 Random Graphs......Page 202
 6.3 Graph Spectrum......Page 205
 6.4 Graph Spectral Entropy......Page 207
 6.6 Jensen-Shannon Divergence......Page 210
 6.7 Model Selection and Parameter Estimation......Page 211
 6.8 Hypothesis Test between Graph Collections......Page 213
 6.9 Final Considerations......Page 216
  6.9.1 Model Selection for Protein-Protein Networks......Page 217
 6.10 Conclusions......Page 218
 References......Page 219
  7.1.1 Structure of the Chapter......Page 221
  7.1.2 Quantitative Graph Theory......Page 222
  7.1.3 Graph Models in Image Analysis......Page 223
   7.1.4.1 Complementarity of Texture and Shape......Page 224
   7.1.4.2 Texture Models......Page 225
   7.1.4.3 Texture Segmentation......Page 226
 7.2 Graph Entropy-Based Texture Descriptors......Page 227
  7.2.1 Graph Construction......Page 228
  7.2.2 Entropy-Based Graph Indices......Page 229
   7.2.2.2 Bonchev and Trinajstic's Mean Information on Distances......Page 230
   7.2.2.3 Dehmer Entropies......Page 231
  7.3.1 Basic GAC Evolution for Grayscale Images......Page 232
  7.3.2 Force Terms......Page 233
  7.3.4 Remarks on Numerics......Page 234
  7.4.1 First Synthetic Example......Page 235
  7.4.2 Second Synthetic Example......Page 236
  7.4.3 Real-World Example......Page 238
  7.5.1 Rewriting the Information Functionals......Page 239
  7.5.2 Infinite Resolution Limits of Graphs......Page 240
  7.5.3 Fractal Analysis......Page 241
 7.6 Conclusion......Page 244
 References......Page 245
 8.1 Introduction......Page 251
  8.2.1 Information Content Measures......Page 254
  8.2.2 Information Content of Partition of a Positive Integer......Page 258
  8.2.3 Information Content of Graph......Page 261
   8.2.3.1 Information Content of Graph on Vertex Degree......Page 263
   8.2.3.2 Information Content of Graph on Topological Distances......Page 264
  8.2.4 Information Content on the Shortest Molecular Path......Page 269
   8.2.4.1 Computation of Example Indices......Page 270
 8.3 Prediction of Physical Entropy......Page 271
  8.3.1 Prediction of Entropy using Information Theoretical Indices......Page 272
 8.4 Conclusion......Page 274
 References......Page 275
 9.1 Introduction......Page 277
  9.1.1 Challenges in Bibliometric Data Sets, or Why Should We Consider Entropy Measures?......Page 278
 9.2 State of the Art......Page 279
  9.2.1 Graphs and Text Mining......Page 280
  9.2.2 Graph Entropy for Data Mining and Knowledge Discovery......Page 281
  9.2.3 Graphs from Bibliometric Data......Page 282
 9.4 Method and Materials......Page 284
 9.5 Results......Page 285
  9.6.1 Open Problems......Page 289
 References......Page 290
Index......Page 293
EULA......Page 299