Dehmer Structural Analysis of Complex Networks

1. Auflage 2010
ISBN: 978-0-8176-4789-6
Verlag: Birkhäuser Boston
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 486 Seiten

Filling a gap in literature, this self-contained book presents theoretical and application-oriented results that allow for a structural exploration of complex networks. The work focuses not only on classical graph-theoretic methods, but also demonstrates the usefulness of structural graph theory as a tool for solving interdisciplinary problems. Applications to biology, chemistry, linguistics, and data analysis are emphasized. The book is suitable for a broad, interdisciplinary readership of researchers, practitioners, and graduate students in discrete mathematics, statistics, computer science, machine learning, artificial intelligence, computational and systems biology, cognitive science, computational linguistics, and mathematical chemistry. It may also be used as a supplementary textbook in graduate-level seminars on structural graph analysis, complex networks, or network-based machine learning methods.

Autoren/Hrsg.

Dehmer, Matthias

Inhaltsverzeichnis

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