Structure and Spectra of Large Networks


One of the main goals in graph theory is to deduce the principal properties and structure of a graph from its spectrum. It is known that eigenvalues are closely related to almost all major invariants of graphs, linking one extremal property to another. There is no question that eigenvalues play a central role in our fundamental understanding of graphs. Moreover, spectral graph theory has applications in e.g. chemistry, theoretical physics, and quantum mechanics. Eigenvalues of graphs are also important in theoretical computer science. The recent progress on expander graphs and eigenvalues was initiated by problems arising in communication networks, while the development of rapidly mixing Markov chains has interwined with advances in randomized approximation algorithms. [Source: Fan R.K. Chung: Spectral Graph Theory, American Mathematical Society]

Within this topic we are interested in:
  • Structure and spectra of large "real world" networks
  • Relationship between optimal partitions and eigenvalues of graphs