Analysis of Complex Networks: From Biology to Linguistics......Page 5
Contents......Page 7
Preface......Page 15
List of Contributors......Page 17
1.1 Introduction......Page 21
1.2 Entropy or the Information Content of Graphs......Page 22
1.3 Groups and Graph Spectra......Page 24
1.4 Approximating Orbits......Page 31
1.4.2 The Point-Deleted Neighborhood Degree Vector......Page 33
1.4.3 Betweenness Centrality......Page 35
1.5 Alternative Bases for Structural Complexity......Page 39
References......Page 41
2.1 Introduction......Page 43
2.1.1 Network Entropies......Page 45
2.1.2 Network Hamiltonians......Page 47
2.1.3 Network Ensembles......Page 48
2.1.4 Some Definitions of Network Measures......Page 50
2.2 Macroscopics: Entropies for Networks......Page 51
2.2.1.1 A Unified Network Model......Page 52
2.3 Microscopics: Hamiltonians of Networks – Network Thermodynamics......Page 55
2.3.1 Topological Phase Transitions......Page 56
2.3.2 A Note on Entropy......Page 57
2.4 Ensembles of Random Networks – Superstatistics......Page 59
2.5 Conclusion......Page 62
References......Page 63
3.1 Introduction......Page 67
3.2 The Small-World Connectivity Descriptors......Page 69
3.3 The Integrated Centrality Measure......Page 72
References......Page 73
4.1 Introduction......Page 75
4.2 Background on Graph Spectra......Page 76
4.3 Spectral Measures of Node Centrality......Page 78
4.3.1 Subgraph Centrality as a Partition Function......Page 80
4.3.2 Application......Page 81
4.4 Global Topological Organization of Complex Networks......Page 82
4.4.1 Spectral Scaling Method......Page 83
4.4.2 Universal Topological Classes of Networks......Page 85
4.4.3 Applications......Page 88
4.5 Communicability in Complex Networks......Page 89
4.5.1 Communicability and Network Communities......Page 91
4.5.2 Detection of Communities: The Communicability Graph......Page 93
4.5.3 Application......Page 94
4.6 Network Bipartivity......Page 96
4.6.1 Detecting Bipartite Substructures in Complex Networks......Page 97
4.7 Conclusion......Page 100
References......Page 101
5.1 Motivation and Background......Page 105
5.1.1 Notation and Terminology......Page 107
5.2 Preliminaries......Page 108
5.3 Connectivity......Page 110
5.4 The Largest Component......Page 113
5.5 Distances in n-Cubes......Page 125
5.6 Conclusion......Page 130
References......Page 131
6.1 Introduction......Page 133
6.2 Graph Edit Distance......Page 135
6.3.1 Optimal Algorithms......Page 138
6.3.2.1 Bipartite Graph Matching......Page 141
6.4.1 Graph Data Sets......Page 145
6.4.3 Dissimilarity-Based Embedding Graph Kernels......Page 149
6.5 Experimental Evaluation......Page 152
6.5.1 Optimal vs. Suboptimal Graph Edit Distance......Page 153
6.5.2 Dissimilarity Embedding Graph Kernels Based on Suboptimal Graph Edit Distance......Page 156
6.6 Summary and Conclusions......Page 159
References......Page 160
7.1 Introduction......Page 165
7.2.1 Some Upper Bounds......Page 167
7.2.2 Some Lower Bounds......Page 174
7.3.1 Hyperenergetic Graphs......Page 176
7.3.3 Equienergetic Graphs......Page 177
7.4 Graphs Extremal with Regard to Energy......Page 182
7.5 Miscellaneous......Page 188
7.6 Concluding Remarks......Page 189
References......Page 190
8.1 Introduction......Page 195
8.2.1 Preliminary Notions......Page 198
8.2.2 Generalized Trees......Page 200
8.2.3 Minimum Spanning Generalized Trees......Page 206
8.2.4 Generalized Shortest Path Trees......Page 210
8.2.5 Shortest Paths Generalized Trees......Page 213
8.2.6 Generalized Shortest Paths Trees......Page 215
8.2.7 Accounting for Orientation: Directed Generalized Trees......Page 218
8.2.8 Generalized Trees, Quality Dimensions, and Conceptual Domains......Page 224
8.2.9 Generalized Forests as Multidomain Conceptual Spaces......Page 228
8.3 Semiotic Systems as Conceptual Graphs......Page 232
References......Page 238
9.1 Introduction......Page 241
9.2 Molecular Graphs......Page 242
9.3 Common Problems with Molecular Graphs......Page 243
9.4 Comparisons and 3D Alignment of Protein Structures......Page 245
9.5 Identification of Macromolecular Assemblies in Crystal Packing......Page 249
9.6 Chemical Graph Formats......Page 251
9.9 Subgraph Isomorphism Solution in SQL......Page 252
9.10 Cycles in Graphs......Page 255
9.11 Aromatic Properties......Page 256
9.12 Planar Subgraphs......Page 257
9.13 Conclusion......Page 258
References......Page 259
10.1 Introduction......Page 265
10.1.1 Properties of Cortical and Neuronal Networks......Page 266
10.1.1.2 Small-World Features......Page 267
10.1.1.3 Scale-Free Features......Page 268
10.1.1.4 Spatial Layout......Page 270
10.1.2 Prediction of Neural Connectivity......Page 272
10.1.3 Activity Spreading......Page 274
10.2.1 Robustness Toward Structural Damage......Page 275
10.2.1.1 Removal of Edges......Page 276
10.2.1.2 Removal of Nodes......Page 277
10.2.2.1 Spatial Growth Can Generate Small-World Networks......Page 278
10.2.2.2 Time Windows Generate Multiple Clusters......Page 279
10.3.1 Spreading in Excitable Media......Page 280
10.3.1.2 Critical Timing for Changing the State of the Cardiac System......Page 281
10.3.2 Topological Inhibition Limits Spreading......Page 282
10.4 Summary......Page 284
References......Page 286
11.1 Introduction......Page 291
11.2 Brief Overview of Network Mapping Methods......Page 293
11.3 Modeling Metabolic Pathway Mappings......Page 295
11.4 Computing Minimum Cost Homomorphisms......Page 297
11.4.1 The Dynamic Programming Algorithm for Multi-Source Tree Patterns......Page 298
11.4.2 Handling Cycles in Patterns......Page 300
11.4.3 Allowing Pattern Vertex Deletion......Page 301
11.5 Mapping Metabolic Pathways......Page 302
11.6 Implications of Pathway Mappings......Page 305
References......Page 311
12.1 Introduction......Page 315
12.2 The Connected List Coloring Problem......Page 316
12.3.1 The Problem of Connected Service Areas......Page 318
12.3.2 No-Idle Scheduling on Parallel Machines......Page 320
12.3.3 Scheduling of Unit Jobs on a p-Batch Machine......Page 321
12.4 A Parameterized Class of Subproblems of the CLC Problem......Page 322
12.5.1 Three NP-Complete Subproblems......Page 324
12.5.2 Five Polynomial-Time Solvable Subproblems......Page 325
12.6 A Basis System of Problems......Page 337
12.7 Conclusion......Page 340
References......Page 342
13.1 Introduction......Page 343
13.2 Preliminaries......Page 344
13.2.1 Median Graphs......Page 345
13.2.1.2 The Canonical Metric Representation and Isometric Dimension......Page 348
13.3.1 Treelike Eequalities and Euler-Type Inequalities for Median Graphs......Page 350
13.3.1.1 Cube-Free Median Graphs......Page 352
13.3.1.3 Median Grid Graphs......Page 353
13.3.2 Euler-Type Inequalities for Quasi-Median Graphs......Page 354
13.3.3 Euler-Type Inequalities for Partial Cubes......Page 355
13.3.4 Treelike Equality for Cage-Amalgamation Graphs......Page 356
13.4 Cube Polynomials......Page 357
13.4.1 Cube Polynomials of Cube-Free Median Graphs......Page 359
13.4.2.1 Rational Roots of Cube Polynomials......Page 360
13.4.2.3 Graphs of Acyclic Cubical Complexes......Page 361
13.4.3 Higher Derivatives of Cube Polynomials......Page 362
13.5 Hamming Polynomials......Page 363
13.5.1 A Different Type of Hamming Polynomial for Cage-Amalgamation Graphs......Page 364
13.6 Maximal Cubes in Median Graphs of Circular Split Systems......Page 365
13.7 Applications in Phylogenetics......Page 366
13.8 Summary and Conclusion......Page 367
References......Page 368
14.1 Introduction......Page 371
14.2 Kernel Elementary Polycycles......Page 375
14.3 Classification of Elementary ({2, 3, 4, 5}, 3)-Polycycles......Page 376
14.5 Classification of Elementary ({2, 3}, 5)-Polycycles......Page 379
14.6 Conclusion......Page 381
Appendix 1: 204 Sporadic Elementary ({2,3,4,5},3)-Polycycles......Page 384
Appendix 2: 57 Sporadic eLementary ({2, 3}, 5)-polycycles......Page 391
References......Page 395
15.1 Introduction......Page 397
15.2.1 The Minimum Cost Dynamic Flow Problem......Page 398
15.2.3 Algorithms for Solving the Optimal Dynamic Flow Problems......Page 400
15.2.5 The Dynamic Model with Flow Storage at Nodes and Integral Constant Demand–Supply Functions......Page 404
15.2.6 Approaches to Solving Dynamic Flow Problems with Different Types of Cost Functions......Page 406
15.2.7 Determining the Optimal Dynamic Flows in Networks with Transit Functions That Depend on Flow and Time......Page 410
15.3.1 The Minimum Cost Dynamic Multicommodity Flow Problem......Page 412
15.3.2 Algorithm for Solving the Minimum Cost Dynamic Multicommodity Flow Problem......Page 414
15.4 Conclusion......Page 418
References......Page 419
16.1 Introduction......Page 421
16.2 Data Preparation......Page 422
16.3 Network Definition......Page 424
16.4 Network Structure......Page 425
16.5 Community Structure......Page 427
16.5.1 Modularity......Page 428
16.6 Communities in the Framework Program Networks......Page 429
16.6.1 Topical Profiles of Communities......Page 431
16.7.1 The Empirical Model......Page 433
16.7.2.3 Variables Accounting for FP Experience of Organizations......Page 435
16.7.2.4 Variables Accounting for Relational Effects......Page 436
16.7.3 Estimation Results......Page 437
16.8 Summary......Page 440
References......Page 441
17.1 Introduction......Page 445
17.2 Trees......Page 446
17.2.1 The Degree Distribution......Page 449
17.2.2 The Height......Page 450
17.2.3 The Profile......Page 451
17.2.4 The Width......Page 454
17.3 Random Mappings......Page 456
17.4.1 Counting Connected Graphs with Wright’s Method......Page 458
17.4.2 Emergence of the Giant Component......Page 460
17.5 Planar Graphs......Page 465
References......Page 469
Index......Page 471
· · · · · · (收起)