Structural Analysis of Complex Networks (eBook)

Preface 6
Contents 
10 
Contributors 12
Chapter 1: 
16 
1.1 Introduction 16
1.2 Important Network Classes 17
1.2.1 Simple Networks 17
1.2.2 Random Networks 17
1.2.3 Degree Distribution 18
1.2.4 Clustering Coefficient 19
1.2.5 Small-World Networks 19
1.2.6 Scale-Free Networks 19
1.2.7 Trees 20
1.2.8 Generalized Trees 21
1.3 Structural Network Analysis 23
1.3.1 Degree Distribution 23
1.3.2 Clustering Coefficient 23
1.3.3 Path-Based Measures 23
Distance Matrix 24
Mean or Characteristic Distance 24
j-Sphere 24
Eccentricity, Diameter, and Radius 24
Degree, Degree Statistics, and Edge Density 25
1.3.4 Centrality Measures 25
Point Centrality 26
Degree Centrality 26
Betweenness Centrality 26
Closeness Centrality 26
Graph Centrality 27
Degree Centrality 27
Betweenness Centrality 27
Closeness Centrality 28
Extended Centrality Measures 28
Eigenvector Centrality 28
Joint Betweenness Centrality 28
1.3.5 Comparative Network Analysis 29
Measures Based on Isomorphic Relations 29
Measures Based on Graph Transformations 30
Measures Based on Graph Grammars 31
Methods Based on Machine Learning Techniques 31
1.3.6 Community or Module Detection 32
1.4 Information-Theoretic Methods 35
1.5 Conclusions 36
References 37
Chapter 2: 
42 
2.1 Introduction and Notation 43
2.1.1 Examples of M-Partitions 43
2.1.2 Hereditary Properties 44
2.1.3 Reducibility 46
2.1.4 Examples of Some Reducible Bounds 47
2.1.5 Minimal Reducible Bounds for Outerplanar and Planar Graphs 47
2.1.6 Minimal Reducible Bounds for Some Other Classes of Graphs 48
2.1.7 Complexity of Some Selected Graph Partition Problems 49
2.2 k-Clustering 50
2.2.1 Minimum k-Clustering 50
2.2.2 Strongly Chordal Graphs 51
2.2.3 Hereditary Clique-Helly Graphs 52
2.2.4 Minimum k-Clustering in HCHC 53
2.2.5 Balanced Graphs 55
2.3 Matching Cutset 56
2.4 Acyclic Colourings 57
2.4.1 Selected Results 57
2.4.2 Brooks-Type Results 58
2.4.3 Improper Acyclic Colouring 58
References 60
Chapter 3: 
63 
3.1 Overview of Chapter 63
3.2 Distance, Diameter and Radius 64
3.2.1 Diameter and Radius 64
3.2.2 Bounds for the Radius and Diameter 65
3.2.3 Changes in Diameter and Radius with Edge and Vertex Removal 66
3.2.4 Matrices and Walks 67
3.3 Other Measures of Centrality 68
3.4 Special Graph Classes 69
3.4.1 Chordal Graphs 69
3.4.2 Cartesian Products 70
3.4.3 Distance Hereditary Graphs 71
3.4.4 Random Graphs 72
3.5 Average Distance 72
3.5.1 Bounds on the Average Distance 73
3.5.2 The Average Distance and Other Graph Invariants 74
3.5.3 Edge Removal and the Average Distance 75
3.5.4 Vertex Removal and Average Distance 76
3.6 Directed Graphs 77
3.6.1 The Average Distance of Digraphs 77
3.6.2 Tournaments 78
3.7 Convexity 78
3.8 Metric Dimension 80
3.9 Algorithms and Complexity 81
3.9.1 Shortest Paths 81
3.9.2 All Pairs Shortest Paths 81
3.10 Steiner Distances 82
3.10.1 Extending Distance Measures 82
3.10.2 Steiner Intervals and Graph Convexity 83
References 84
Chapter 4: 
87 
4.1 Introduction 88
4.2 Bounds on the Domination Number 89
4.3 Two Other Types of Domination 92
4.4 Results on Criticality 96
4.4.1 k–Edge-Critical Graphs 97
4.4.2 k-t-Edge-Critical Graphs 100
4.4.3 k-c-Edge-Critical Graphs 102
4.4.4 k–Vertex-Critical Graphs 103
4.4.5 k-P-Vertex-Critical Graphs Where P{t, c} 105
4.5 Matching Properties 108
4.5.1 3-P-Edge-Critical Graphs and Matching Properties 108
4.5.2 3-P-Vertex-Critical Graphs and Matching Properties 110
4.6 Summary and Conclusions 112
References 113
Chapter 5: 
119 
5.1 Adjacency Operator and Dyadic Representation 120
5.2 Spectral Invariants 122
5.3 Products for Graphs 130
5.4 Directed Path and Tree 134
5.5 Two Entropies for Graphs 141
5.6 Ziv's Entropy and Coding 146
5.7 Notes 149
References 149
Chapter 6: 
151 
6.1 Introduction 151
6.2 Markov Shifts and Finite Directed Graphs 153
6.3 Sofic Shifts and Finite Labeled Graphs 154
6.4 Coded Shifts 156
6.5 -Graph Systems and Symbolic Matrix Systems 156
6.6 Strong Shift Equivalences and Shift Equivalences 160
6.7 Nonnegative Matrix Systems 168
6.8 Dimension Groups, K-Groups, and Bowen–Franks Groups 171
6.9 Spectrum, -Entropy, and Volume Entropy 175
6.10 Example 179
6.11 Remark: Relation to K-Theory for C*-Algebras 179
6.12 Conclusions and Further Work 180
References 180
Chapter 7: 
183 
7.1 About Graph Decompositions and Factorizations 183
7.1.1 Ad Hoc Wireless Network Design 184
7.1.2 Description of the Graph Theory Problem 184
7.1.3 Necessary Conditions for Decompositions 185
7.1.4 Sufficient Conditions for Decompositions 187
a 
188 
b, s, and r- 
189 
7.1.5 Necessary Conditions for Factorizations 189
7.1.6 Sufficient Conditions for Factorizations 190
Factorizing Regular Complete Bipartite Graphs 190
r 
191 
Blended -Labeling 192
Swapping Labeling 193
2n-Cyclic Labeling 194
Fixing Labeling 195
7.2 Advanced Methods 197
7.2.1 N-Z Construction 197
7.2.2 Limitations 198
7.3 Overview of Known Results 199
7.3.1 Trees 199
7.3.2 Disproof of Kubesa's Conjecture 201
7.3.3 Packings, Coverings, and Orthogonal Double Covers 201
7.4 Recursive Construction 201
7.4.1 About the Method 202
7.4.2 The Method of Recursive Labeling 204
7.4.3 Examples 206
7.4.4 Comparison to Previously Defined Labelings 207
7.5 Conclusion 207
7.5.1 Further Possible Generalizations 208
7.5.2 Further Extensions 208
References 209
Chapter 8: 
211 
8.1 Introduction 211
8.2 Cartesian Products 214
8.3 Median Graphs 218
8.4 Algorithms and Complexity 221
8.5 Boundary and Geodetic Sets 224
8.6 Related Concepts 226
8.7 Summary and Conclusion 228
References 229
Chapter 9: 
233 
9.1 Introduction 233
9.2 Preliminary Notions 234
9.2.1 Basic Concepts 234
9.2.2 Deletion and Contraction 235
9.2.3 The Rank and Nullity Functions for Graphs 236
9.2.4 Planar Graphs and Duality 236
9.3 Defining the Tutte Polynomial 237
9.3.1 Linear Recursion Definition 237
9.3.2 Rank-Nullity Generating Function Definition 239
9.3.3 Spanning Trees Expansion Definition 239
9.4 Universality of the Tutte Polynomial 240
9.5 Combinatorial Interpretations of Some Evaluations 241
9.5.1 Spanning Subgraphs 241
9.5.2 The Tutte Polynomial when y=x 243
9.5.3 Orientations and Score Vectors 244
9.6 Some Specializations 245
9.6.1 The Chromatic Polynomial 246
9.6.2 The Bad Coloring Polynomial 247
9.6.3 The Flow Polynomial 249
9.6.4 Abelian Sandpile Models 250
9.6.5 The Reliability Polynomial 252
9.6.6 The Shelling Polynomial 254
9.7 Some Properties of the Tutte Polynomial 256
9.7.1 The Beta Invariant 256
9.7.2 Coefficient Relations 258
9.7.3 Zeros of the Tutte Polynomial 259
9.7.4 Derivatives of the Tutte Polynomial 261
9.7.5 Convolution and the Tutte Polynomial 262
9.8 The Complexity of the Tutte Polynomial 263
9.9 Conclusion 265
References 265
Chapter 10: 
270 
10.1 Introduction 270
10.2 Formulating Graph Polynomials 271
10.3 Some Interrelated Polynomial Invariants 273
10.3.1 Characteristic and Matching Polynomials 273
10.3.2 Ehrhart Polynomial 278
10.3.3 The Topological Tutte Polynomial of Bollobás and Riordan 280
10.3.4 Martin, or Circuit Partition, Polynomials 283
10.3.5 Interlace Polynomial 285
10.4 Multivariable Extensions 288
10.4.1 Generalized Coloring Polynomials and the U-Polynomial 288
10.4.2 The Parametrized Tutte Polynomial 291
10.4.3 The Generalized Transition Polynomial 293
10.5 Two Applications 296
10.5.1 DNA Sequencing 296
10.5.2 The Potts Model of Statistical Mechanics 298
10.6 Conclusion 300
References 300
Chapter 11: 
306 
11.1 Introduction 306
11.1.1 The Reconstruction Conjecture 306
11.1.2 Reconstruction Problems and Zeroes of Krawtchouk Polynomials 307
11.1.3 Outline of Chapter 308
11.1.4 Main Result 309
11.2 Krawtchouk Polynomials 309
11.2.1 Basic Facts 309
11.2.2 Zeroes and Upper Bounds 311
11.3 The Diophantine Equation Pkn(x)=g(y) 312
11.3.1 Introduction 312
11.3.2 The Criterion of Bilu and Tichy 313
11.4 The Discrete Laguerre Inequality 315
11.4.1 Introduction and Statement 315
11.4.2 Krasikov's Application to Krawtchouk Polynomials 315
11.5 Monotonicity of Stationary Points and Indecomposability 317
11.5.1 Definitions 317
11.5.2 Decomposition and Orthogonal Polynomials 318
11.6 Stationary Points of Krawtchouk Polynomials 319
11.6.1 Iteration of Krasikov's Bound 319
11.6.2 Admissible Parameter Ranges 320
11.7 Decomposition of Krawtchouk Polynomials 321
11.7.1 An Indecomposability Criterion 321
11.7.2 Application to Krawtchouk Polynomials 322
11.8 Decompositions with Standard Pairs 326
11.8.1 Introduction 326
11.8.2 Case deg= n 327
11.8.3 Case deg= k with k=2k' and Pkn=(x2-nx) 327
11.8.4 Case deg= 1 327
11.9 Summary and Conclusion 328
References 329
Chapter 12: 
331 
12.1 Introduction 331
Reconstruction Conjecture 333
12.2 Most Graphs Are Dissimilar 334
12.2.1 Empirical Evidence 338
12.3 Graphs with Large Subgraph Similarity 339
12.3.1 Large Values of rn 339
12.3.2 Large Values of rn 340
Strong Reconstruction Conjecture 343
12.4 Algorithmic and Other Issues 343
12.5 Conclusion 345
References 345
Chapter 13: 
347 
13.1 Introduction 347
13.2 Relatedness of Classes 349
13.3 Relatedness of Graphs 351
13.4 Towards a Characterization of Relatedness 356
13.5 Some Specific Relatednesses 357
13.6 Distantly Related Graphs 361
13.7 The Chromatic Metric 364
13.8 Conclusion 367
References 368
Chapter 14: 
369 
14.1 Introduction 369
14.2 Eigenvalues of the Adjacency Matrix 371
14.3 Eigenvalues of the Laplacian 372
14.4 Eigenvalues of the Normalized Laplacian 374
14.5 Graph Partitioning Using Eigenvalues and Eigenvectors 374
14.6 Epidemic Spreading in Networks 385
14.7 Eigenvalues and Other Graph Invariants 387
14.8 Conclusions 388
References 389
Chapter 15: 
392 
15.1 Introduction 392
15.2 Context-Sensitive Spanning Trees 394
15.2.1 Minimum Spanning Markovian Trees 400
15.2.2 Damped Markovian Trees 407
15.3 Conclusion 411
References 412
Chapter 16: 
413 
16.1 Introduction 413
16.2 Networks and Their Properties 414
16.2.1 Metrics 415
16.2.2 Network Characterization 415
16.3 Techniques of Link Mining 417
16.3.1 Community Finding 417
16.3.2 Node Ranking 419
16.3.3 Influence Maximization 421
16.3.4 Link Prediction 423
16.3.5 Link-Based Classification 424
16.4 Conclusion 425
References 426
Chapter 17: 
430 
17.1 Introduction 430
17.2 Structural Properties of RNA Molecules 431
17.3 Secondary Structure as Outerplanar Graph 432
17.4 Classification of Structural Elements 434
17.5 Counting Secondary Structures 434
17.6 Structure Prediction Using Simple Base-Pairing Rules 435
17.7 Structure Prediction Using the Loop-Based Energy Model 436
17.8 Prediction of Base-Pairing Probabilities 439
17.9 Tree Representations of Secondary Structures 440
17.10 Comparing Secondary Structures Using Tree Editing 441
17.11 Summary and Conclusion 444
References 445
Chapter 18: 
447 
18.1 Introduction: Functional Classification and Protein Interaction Networks 447
18.2 Functional Annotation and Protein Interaction Networks 449
18.2.1 The Gene Ontology Consortium and MIPS Functional Catalogue 449
18.2.2 Protein–Protein Interaction Networks 450
18.3 Mathematical Formulation and Preliminaries 451
18.3.1 Notation and Mathematical Background 451
18.3.2 Protein Function Prediction: Formal Statement 452
18.4 Topology and Protein Function 453
18.5 Graph-Based Algorithms for PFP 455
18.5.1 Majority Rule 455
18.5.2 Chi-Squared Scheme 456
18.5.3 Maximally Consistent Assignments and Functional Flow 457
The Vazquez Method 458
The Karaoz Method 459
The Nabieva Method 460
18.5.4 Markov Random Fields and Level-2 Neighbours 461
Markov Random Field Approaches 461
Algorithms Based on Level-2 Neighbours 462
18.6 Validation and Comparison of Methods 462
18.7 Discussion and Conclusions 467
References 468
Chapter 19: Applications of Perfect Matchings in Chemistry 470
19.1 Introduction 470
19.2 Existence and Enumeration of Perfect Matchings 472
19.3 Applications of the Number of Kekulé Structures in Chemistry 476
19.4 Algebraic Kekulé Structures 477
19.5 Coding of Kekulé Structures 479
19.6 Classification of Kekulé Structures 480
19.7 Resonance Graph 482
19.8 Anti-Kekulé Number 485
19.9 Conclusion 487
References 487
Index 490