Graph Spectra for Complex Networks

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