Graph Spectra for Complex Networks

by Piet Van Mieghem

• ISBN13: 9780521194587
• ISBN10: 052119458X
• Format: Hardcover
• Copyright: 2011-01-17
• Publisher: Cambridge University Press

Summary

Analyzing the behavior of complex networks is an important element in the design of new man-made structures such as communication systems and biologically engineered molecules. Because any complex network can be represented by a graph, and therefore in turn by a matrix, graph theory has become a powerful tool in the investigation of network performance. This self-contained book provides a concise introduction to the theory of graph spectra and its applications to the study of complex networks. Covering a range of types of graphs and topics important to the analysis of complex systems, this guide provides the mathematical foundation needed to understand and apply spectral insight to real-world systems. In particular, the general properties of both the adjacency and Laplacian spectrum of graphs are derived and applied to complex networks. An ideal resource for researchers and students in communications networking as well as in physics and mathematics.

Author Biography

Piet Van Mieghem is a Professor at the Delft University of Technology with a Chair in Telecommunication Networks, and Chairman of the Network Architectures and Services (NAS) section. His main research interests lie in the modeling and analysis of complex networks (such as biological, brain, social, infrastructural, etc. networks) and in new Internet-like architectures and algorithms for future communications networks.

Table of Contents

Preface	p. ix
Acknowledgements	p. xiii
Symbols	p. xv
Introduction	p. 1
Interpretation and contemplation	p. 2
Outline of the book	p. 5
Classes of graphs	p. 7
Outlook	p. 10
Spectra of graphs	p. 11
Algebraic graph theory	p. 13
Graph related matrices	p. 13
Walks and paths	p. 25
Eigenvalues of the adjacency matrix	p. 29
General properties	p. 29
The number of walks	p. 33
Regular graphs	p. 43
Bounds for the largest, positive eigenvalue ¿1	p. 46
Eigenvalue spacings	p. 55
Additional properties	p. 58
The stochastic matrix P = ¿-1A	p. 63
Eigenvalues of the Laplacian Q	p. 67
General properties	p. 67
Second smallest eigenvalue of the Laplacian Q	p. 80
Partitioning of a graph	p. 89
The modularity and the modularity matrix M	p. 96
Bounds for the diameter	p. 108
Eigenvalues of graphs and subgraphs	p. 109
Spectra of special types of graphs	p. 115
The complete graph	p. 115
A small-world graph	p. 115
A circuit on N nodes	p. 123
A path of N - 1 hops	p. 124
A path of h hops	p. 129
The wheel WN+1	p. 129
The complete bipartite graph Km,n	p. 129
A general bipartite graph	p. 131
Complete multi-partite graph	p. 135
An m-fully meshed star topology	p. 138
A chain of cliques	p. 147
The lattice	p. 154
Density function of the eigenvalues	p. 159
Definitions	p. 159
The density when N → ∞	p. 161
Examples of spectral density functions	p. 163
Density of a sparse regular graph	p. 166
Random matrix theory	p. 169
Spectra of complex networks	p. 179
Simple observations	p. 179
Distribution of the Laplacian eigenvalues and of the degree	p. 181
Functional brain network	p. 184
Rewiring Watts-Strogatz small-world graphs	p. 185
Assortativity	p. 187
Reconstructability of complex networks	p. 196
Reaching consensus	p. 199
Spectral graph metrics	p. 200
Eigensystem and polynomials	p. 209
Eigensystem of a matrix	p. 211
Eigenvalues and eigenvectors	p. 211
Functions of a matrix	p. 219
Hermitian and real symmetric matrices	p. 222
Vector and matrix norms	p. 230
Non-negative matrices	p. 235
Positive (semi) definiteness	p. 240
Interlacing	p. 243
Eigenstructure of the product AB	p. 252
Formulae of determinants	p. 255
Polynomials with real coefficients	p. 263
General properties	p. 263
Transforming polynomials	p. 270
Interpolation	p. 274
The Euclidean algorithm	p. 277
Descartes' rule of signs	p. 282
The number of real zeros in an interval	p. 292
Locations of zeros in the complex plane	p. 295
Zeros of complex functions	p. 302
Bounds on values of a polynomial	p. 305
Bounds for the spacing between zeros	p. 306
Bounds on the zeros of a polynomial	p. 308
Orthogonal polynomials	p. 313
Definitions	p. 313
Properties	p. 315
The three-term recursion	p. 317
Zeros of orthogonal polynomials	p. 323
Gaussian quadrature	p. 326
The Jacobi matrix	p. 331
References	p. 339
Index	p. 345
Table of Contents provided by Ingram. All Rights Reserved.