Van Mieghem P. Graph Spectra for Complex Networks

Cambridge University Press, 2011. — 364 p.During the first years of the third millennium, considerable interest arose in complex networks such as the Internet, the World Wide Web, biological networks, utility infrastructures (for transport of energy, waste, water, trains, cars and aircrafts), social networks, human brain networks, and so on. It was realized that complex networks are omnipresent and of crucial importance to humanity, whose still augmenting living standards increasingly depend on complex networks. Around the beginning of the new era, general laws such as preferential attachment and the power law of the degree were observed in many, totally different complex networks. This fascinating coincidence gave birth to an area of new research that is still continuing today. But, as is often the case in science, deeper investigations lead to more questions and to the conclusion that so little is understood of (large) networks. For example, the rather simple but highly relevant question What is a robust network? seems beyond the realm of present understanding. The most natural way to embark on solving the question consists of proposing a set of metrics that tend to specify and quantify robustness. Soon one discovers that there is no universal set of metrics, and that the metrics of any set are dependent on each other and on the structure of the network.
Any complex network can be represented by a graph. Any graph can be represented by an adjacency matrix, from which other matrices such as the Laplacian are derived. These graph related matrices are defined in Chapter
2. One of the most beautiful aspects of linear algebra is the notion that, to each matrix, a set of eigenvalues with corresponding eigenvectors can be associated. The physical meaning of an eigen system is best understood by regarding the matrix as a geometric transformation of points in a space. Those points define a vector: a line segment from an origin that ends in the particular point and that is directed from origin to end. The transformation (rotation, translation, scaling) of the vector is again a vector in the same space, but generally different from the original vector. The vector that after the transformation turns out to be proportional with itself is called an eigenvector and the proportionality strength or the scaling factor is the eigenvalue. The Dutch and German adjective eigen means something that is inherent to itself, a characteristic or fundamental property. Thus, knowing that each graph is represented by a matrix, it is natural to investigate the eigensystem, the set of all eigenvalues with corresponding eigenvectors because the eigensystem characterizes the graph. Stronger even, since both the adjacency and Laplacian matrix are symmetric, there is a one to one correspondence between the matrix and the eigensystem, established in art.
In a broader context, transformations have proved very fruitful in science. The most prominent is undoubtedly the Fourier (or Laplace) transform. Many branches of science ranging from mathematics, physics and engineering abound with examples that show the power and beauty of the Fourier transform. The general principle of such transforms is that one may study the problem in either of two domains: in the original one and in the domain after transformation, and that there exists a one to one correspondence between both domains. For example, a signal is a continuous function of time that may represent a message or some information produced over time. Some properties of the signal are more appropriately studied in the time domain, while others are in the transformed domain, the frequency domain. This analogy motivates us to investigate some properties of a graph in the topology domain, represented by a graph consisting of a set of nodes connected by a set of links, while other properties may be more conveniently dealt with in the spectral domain, specified by the set of eigenvalues and eigenvectors.
The duality between topology and spectral domain is, of course, not new and has been studied in the field of mathematics called algebraic graph theory. Several books on the topic, for example by Cvetković et al. (1995); Biggs (1996); Godsil and Royle (2001) and recently by Cvetković et al. (2009), have already appeared. Notwithstanding these books, the present one is different in a few aspects. First, I have tried to build up the theory as a connected set of basic building blocks, called articles, which are abbreviated by art. The presentation in article style was inspired by great scholars in past, such as Gauss (1801) in his great treatise Disquisitiones Arithmeticae, Titchmarsh (1964) in his Theory of Functions, and Hardy and Wright (1968) in their splendid Introduction to the Theory of Numbers, and many others that cannot be mentioned all. To some extent, it is a turning back to the past, where books were written for peers, and without exercise sections, which currently seem standard in almost all books. Thus, this book does not contain exercises.
Second, the book focuses on general theory that applies to all graphs, and much less to particular graphs with special properties, of which the Petersen graph, shown in Fig. 2.3, is perhaps the champion among all. In that aspect, the book does not deal with a zoo of special graphs and their properties, but confines itself to a few classes of graphs that depend at least on a single parameter, such as the number of nodes, that can be varied. Complex networks all differ and vary in at least some parameters. Less justifiable is the omission of multigraphs, directed graphs and weighted graphs. Third, I have attempted to make the book as self-contained as possible and, as a peculiar consequence, the original appendices consumed about half of the book! Thus, I decided to create two parts, the main part I on the spectra, while part II overviews interesting results in linear algebra and the theory of polynomials that are used in part I. Since each chapter in part II discusses a wide area in mathematics, in fact, separate books on each topic are required. Hence, only the basic theory is discussed, while advanced topics are not covered, because the goal to include part II was to support part I. Beside being supportive, part II contains interesting theory that opens possibilities to advance spectral results. For example, Laguerre’s beautiful Theorem 51 may once be applied to the characteristic polynomials of a class of graphs with the same number of negative, positive and zero eigenvalues of the adjacency matrix.
A drawback is that the book does not contain a detailed list of references pointing to the original, first published papers: it was not my intention to survey the literature on the spectra of graphs, but rather to write a cohesive manuscript on results and on methodology. Sometimes, different methods or new proofs of a same result are presented. The monograph by Cvetković et al. (1995), complemented by Cvetković et al. (2009), still remains the invaluable source for references and tables of graph spectra.
The book is a temporal reflection of the current state of the art: during the process of writing, progress is being made. In particular, the many bounds that typify the field are continuously improved. The obvious expectation is that future progress will increasingly shape and fine tune the field into hopefully maturity. Hence, the book will surely need to be updated and all input is most welcome. Finally, I hope that the book may be of use to others and that it may stimulate and excite people to dive into the fascinating world of complex networks with the rigorous devices of algebraic graph theory offered here.Part I Spectra of graphs.
Algebraic graph theory.
Eigenvalues of the adjacency matrix.
Eigenvalues of the Laplacian Q.
Spectra of special types of graphs.
Density function of the eigenvalues.
Spectra of complex networks.
Part II Eigensystem and polynomials.
Eigensystem of a matrix.
Polynomials with real coefficients.
Orthogonal polynomials.