Graph Spectra for Complex Networks

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 2010 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. Cover......Page 1 Title......Page 3 Copyright......Page 4 Dedication......Page 5 Contents......Page 7 Preface......Page 11 Acknowledgements......Page 15 Linear algebra......Page 17 Graph theory......Page 18 1 Introduction......Page 19 1.1 Interpretation and contemplation......Page 20 1.2 Outline of the book......Page 23 1.3 Classes of graphs......Page 25 1.4 Outlook......Page 28 Part I: Spectra of graphs......Page 29 2.1 Graph related matrices......Page 31 2.1.1 The incidence matrix B......Page 33 2.1.2 The line graph......Page 35 2.1.3 The quotient graph......Page 39 2.2 Walks and paths......Page 43 3.1 General properties......Page 47 3.2 The number of walks......Page 51 3.3 Regular graphs......Page 61 3.4 Bounds for the largest, positive eigenvalue lambda1......Page 64 3.5 Eigenvalue spacings......Page 73 3.6 Additional properties......Page 76 3.7 The stochastic matrix.........Page 81 4.1 General properties......Page 85 4.1.1 Eigenvalues and connectivity......Page 91 4.1.2 The number of spanning trees and the Laplacian Q......Page 92 4.1.3 The complexity......Page 94 4.2.1 Upper bounds for.........Page 98 4.2.2 Lower bounds for.........Page 100 4.3 Partitioning of a graph......Page 107 4.4 The modularity and the modularity matrix M......Page 114 4.5 Bounds for the diameter......Page 126 4.6 Eigenvalues of graphs and subgraphs......Page 127 5.2 A small-world graph......Page 133 5.2.1 The eigenvalue structure of a circulant matrix......Page 134 5.2.2 The spectrum of a small-world graph......Page 137 5.3 A circuit on N nodes......Page 141 5.4 A path of N - 1 hops......Page 142 5.7 The complete bipartite graph.........Page 147 5.8.1 Undirected bipartite graph......Page 149 5.8.2 Directed bipartite graph......Page 150 5.8.3 Symmetry in the spectrum of an adjacency matrix A......Page 151 5.8.4 Laplacian spectrum of a tree......Page 152 5.9 Complete multi-partite graph......Page 153 5.10 An m-fully meshed star topology......Page 156 5.10.1 Fully-interconnected stars linked to two separate groups......Page 160 5.10.2 Star-like, two-hierarchical structure......Page 161 5.10.3 Complementary double cone......Page 163 5.11 A chain of cliques......Page 165 5.11.1 Orthogonal polynomials......Page 169 5.12 The lattice......Page 172 6.1 Definitions......Page 177 6.2 The density when.........Page 179 6.3 Examples of spectral density functions......Page 181 6.4 Density of a sparse regular graph......Page 184 6.5 Random matrix theory......Page 187 6.5.1 Wigner’s Semicircle Law......Page 188 6.5.2 The Marcenko-Pastur Law......Page 194 7.1.1 A graph with eigenvalue.........Page 197 7.1.3 A graph with eigenvalue.........Page 198 7.2 Distribution of the Laplacian eigenvalues and of the degree......Page 199 7.3 Functional brain network......Page 202 7.4 Rewiring Watts-Strogatz small-world graphs......Page 203 7.5.1 Theory......Page 205 7.5.1.1 Discussion of (7.4)......Page 207 7.5.1.2 Relation between.........Page 209 7.5.2 Degree-preserving rewiring......Page 210 7.6 Reconstructability of complex networks......Page 214 7.6.1 Theory......Page 215 7.7 Reaching consensus......Page 217 7.8 Spectral graph metrics......Page 218 7.8.2 Graph energy......Page 219 7.8.3 Effective graph resistance......Page 221 Part II: Eigensystem and polynomials......Page 227 8.1 Eigenvalues and eigenvectors......Page 229 8.2 Functions of a matrix......Page 237 8.3 Hermitian and real symmetric matrices......Page 240 8.4 Vector and matrix norms......Page 248 8.4.1 Properties of norms......Page 249 8.4.2 Applications of norms......Page 252 8.5 Non-negative matrices......Page 253 8.6 Positive (semi) definiteness......Page 258 8.7 Interlacing......Page 261 8.8 Eigenstructure of the product AB......Page 270 8.9 Formulae of determinants......Page 273 9.1 General properties......Page 281 9.2 Transforming polynomials......Page 288 9.3 Interpolation......Page 292 9.4 The Euclidean algorithm......Page 295 9.5 Descartes’ rule of signs......Page 300 9.6 The number of real zeros in an interval......Page 310 9.7 Locations of zeros in the complex plane......Page 313 9.8 Zeros of complex functions......Page 320 9.9 Bounds on values of a polynomial......Page 323 9.10 Bounds for the spacing between zeros......Page 324 9.11 Bounds on the zeros of a polynomial......Page 326 10.1 Definitions......Page 331 10.2 Properties......Page 333 10.3 The three-term recursion......Page 335 10.4 Zeros of orthogonal polynomials......Page 341 10.5 Gaussian quadrature......Page 344 10.6 The Jacobi matrix......Page 349 References......Page 357 Index......Page 363 Cover 1 Title 3 Copyright 4 Dedication 5 Contents 7 Preface 11 Acknowledgements 15 Symbols 17 Linear algebra 17 Probability theory 18 Graph theory 18 1 Introduction 19 1.1 Interpretation and contemplation 20 1.2 Outline of the book 23 1.3 Classes of graphs 25 1.4 Outlook 28 Part I: Spectra of graphs 29 2 Algebraic graph theory 31 2.1 Graph related matrices 31 2.1.1 The incidence matrix B 33 2.1.2 The line graph 35 2.1.3 The quotient graph 39 2.2 Walks and paths 43 3 Eigenvalues of the adjacency matrix 47 3.1 General properties 47 3.2 The number of walks 51 3.3 Regular graphs 61 3.4 Bounds for the largest, positive eigenvalue lambda1 64 3.5 Eigenvalue spacings 73 3.6 Additional properties 76 3.7 The stochastic matrix... 81 4 Eigenvalues of the Laplacian Q 85 4.1 General properties 85 4.1.1 Eigenvalues and connectivity 91 4.1.2 The number of spanning trees and the Laplacian Q 92 4.1.3 The complexity 94 4.2 Second smallest eigenvalue of the Laplacian Q 98 4.2.1 Upper bounds for... 98 4.2.2 Lower bounds for... 100 4.3 Partitioning of a graph 107 4.4 The modularity and the modularity matrix M 114 4.5 Bounds for the diameter 126 4.6 Eigenvalues of graphs and subgraphs 127 5 Spectra of special types of graphs 133 5.1 The complete graph 133 5.2 A small-world graph 133 5.2.1 The eigenvalue structure of a circulant matrix 134 5.2.2 The spectrum of a small-world graph 137 5.3 A circuit on N nodes 141 5.4 A path of N - 1 hops 142 5.5 A path of h hops 147 5.6 The wheel... 147 5.7 The complete bipartite graph... 147 5.8 A general bipartite graph 149 5.8.1 Undirected bipartite graph 149 5.8.2 Directed bipartite graph 150 5.8.3 Symmetry in the spectrum of an adjacency matrix A 151 5.8.4 Laplacian spectrum of a tree 152 5.9 Complete multi-partite graph 153 5.10 An m-fully meshed star topology 156 5.10.1 Fully-interconnected stars linked to two separate groups 160 5.10.2 Star-like, two-hierarchical structure 161 5.10.3 Complementary double cone 163 5.11 A chain of cliques 165 5.11.1 Orthogonal polynomials 169 5.12 The lattice 172 6 Density function of the eigenvalues 177 6.1 Definitions 177 6.2 The density when... 179 6.3 Examples of spectral density functions 181 6.4 Density of a sparse regular graph 184 6.5 Random matrix theory 187 6.5.1 Wigner’s Semicircle Law 188 6.5.2 The Marcenko-Pastur Law 194 7 Spectra of complex networks 197 7.1 Simple observations 197 7.1.1 A graph with eigenvalue... 197 7.1.2 A graph with eigenvalue... 198 7.1.3 A graph with eigenvalue... 198 7.2 Distribution of the Laplacian eigenvalues and of the degree 199 7.3 Functional brain network 202 7.4 Rewiring Watts-Strogatz small-world graphs 203 7.5 Assortativity 205 7.5.1 Theory 205 7.5.1.1 Discussion of (7.4) 207 7.5.1.2 Relation between... 209 7.5.1.3 Relation between... 210 7.5.2 Degree-preserving rewiring 210 7.6 Reconstructability of complex networks 214 7.6.1 Theory 215 7.6.2 The average the reconstructability coeficient... 217 7.7 Reaching consensus 217 7.8 Spectral graph metrics 218 7.8.1 Eigenvector centrality 219 7.8.2 Graph energy 219 7.8.3 Effective graph resistance 221 Part II: Eigensystem and polynomials 227 8 Eigensystem of a matrix 229 8.1 Eigenvalues and eigenvectors 229 8.2 Functions of a matrix 237 8.3 Hermitian and real symmetric matrices 240 8.4 Vector and matrix norms 248 8.4.1 Properties of norms 249 8.4.2 Applications of norms 252 8.5 Non-negative matrices 253 8.6 Positive (semi) definiteness 258 8.7 Interlacing 261 8.8 Eigenstructure of the product AB 270 8.9 Formulae of determinants 273 9 Polynomials with real coefficients 281 9.1 General properties 281 9.2 Transforming polynomials 288 9.3 Interpolation 292 9.4 The Euclidean algorithm 295 9.5 Descartes’ rule of signs 300 9.6 The number of real zeros in an interval 310 9.7 Locations of zeros in the complex plane 313 9.8 Zeros of complex functions 320 9.9 Bounds on values of a polynomial 323 9.10 Bounds for the spacing between zeros 324 9.11 Bounds on the zeros of a polynomial 326 10 Orthogonal polynomials 331 10.1 Definitions 331 10.2 Properties 333 10.3 The three-term recursion 335 10.4 Zeros of orthogonal polynomials 341 10.5 Gaussian quadrature 344 10.6 The Jacobi matrix 349 References 357 Index 363 Machine Generated Contents Note: 1. Introduction -- 1.1. Interpretation And Contemplation -- 1.2. Outline Of The Book -- 1.3. Classes Of Graphs -- 1.4. Outlook -- Pt. I Spectra Of Graphs -- 2. Algebraic Graph Theory -- 2.1. Graph Related Matrices -- 2.2. Walks And Paths -- 3. Eigenvalues Of The Adjacency Matrix -- 3.1. General Properties -- 3.2. The Number Of Walks -- 3.3. Regular Graphs -- 3.4. Bounds For The Largest, Positive Eigenvalue & Lambda;1 -- 3.5. Eigenvalue Spacings -- 3.6. Additional Properties -- 3.7. The Stochastic Matrix P = & Delta;-1 A -- 4. Eigenvalues Of The Laplacian Q -- 4.1. General Properties -- 4.2. Second Smallest Eigenvalue Of The Laplacian Q -- 4.3. Partitioning Of A Graph -- 4.4. The Modularity And The Modularity Matrix M -- 4.5. Bounds For The Diameter -- 4.6. Eigenvalues Of Graphs And Subgraphs -- 5. Spectra Of Special Types Of Graphs -- 5.1. The Complete Graph. 5.2. A Small-world Graph -- 5.3. A Circuit On N Nodes -- 5.4. A Path Of N -- 1 Hops -- 5.5. A Path Of H Hops -- 5.6. The Wheel Wn+1 -- 5.7. The Complete Bipartite Graph Km, N -- 5.8. A General Bipartite Graph -- 5.9. Complete Multi-partite Graph -- 5.10. An M-fully Meshed Star Topology -- 5.11. A Chain Of Cliques -- 5.12. The Lattice -- 6. Density Function Of The Eigenvalues -- 6.1. Definitions -- 6.2. The Density When N & Rarr; & Infin; -- 6.3. Examples Of Spectral Density Functions -- 6.4. Density Of A Sparse Regular Graph -- 6.5. Random Matrix Theory -- 7. Spectra Of Complex Networks -- 7.1. Simple Observations -- 7.2. Distribution Of The Laplacian Eigenvalues And Of The Degree -- 7.3. Functional Brain Network -- 7.4. Rewiring Watts-strogatz Small-world Graphs -- 7.5. Assortativity -- 7.6. Reconstructability Of Complex Networks -- 7.7. Reaching Consensus -- 7.8. Spectral Graph Metrics -- Pt. Ii Eigensystem And Polynomials -- 8. Eigensystem Of A Matrix. 8.1. Eigenvalues And Eigenvectors -- 8.2. Functions Of A Matrix -- 8.3. Hermitian And Real Symmetric Matrices -- 8.4. Vector And Matrix Norms -- 8.5. Non-negative Matrices -- 8.6. Positive (semi) Definiteness -- 8.7. Interlacing -- 8.8. Eigenstructure Of The Product Ab -- 8.9. Formulae Of Determinants -- 9. Polynomials With Real Coefficients -- 9.1. General Properties -- 9.2. Transforming Polynomials -- 9.3. Interpolation -- 9.4. The Euclidean Algorithm -- 9.5. Descartes' Rule Of Signs -- 9.6. The Number Of Real Zeros In An Interval -- 9.7. Locations Of Zeros In The Complex Plane -- 9.8. Zeros Of Complex Functions -- 9.9. Bounds On Values Of A Polynomial -- 9.10. Bounds For The Spacing Between Zeros -- 9.11. Bounds On The Zeros Of A Polynomial -- 10. Orthogonal Polynomials -- 10.1. Definitions -- 10.2. Properties -- 10.3. The Three-term Recursion -- 10.4. Zeros Of Orthogonal Polynomials -- 10.5. Gaussian Quadrature -- 10.6. The Jacobi Matrix. Piet Van Mieghem. Includes Bibliographical References (p. 339-343) And Index. A concise and self-contained 2010 introduction to the theory of graph spectra and its applications to the study of complex networks. Covering a range of types of graphs, this guide provides the mathematical foundation needed to understand and apply spectral insight to real-world communications systems and networks.