Tag Archives: google

A quiet renaissance of graph theory?

I freely admit to being immensely captivated by graphs. I'm certain to continue writing/thinking about them, so this post probably qualifies as a bit of a warm up.

A researcher in the field would be able to comment better than I can, but I have the impression that Graph Theory is undergoing something of a slow but steady renaissance at the moment. Your typical book on graph theory tends to be a pure theoretical text* with remarkably few pictures given the visual nature of the subject. (I like pictures). Even the 'applied' ones seem to have a fairly narrow range of applications. I think it's fair to say that many books prefer to concentrate on the 'pureness' of the mathematics than discuss applications. My belief is that graphs are an extremely general and flexible concept, and this distance between theory and applications bothers me.

Enter the likes of Spectral Graph Theory (rather quietly and formally). The (only?) major text on this is by Fan Chung. You can find the first four chapters of her book available to download from her website, although its not the easiest entry point to the subject.

In a nutshell, spectral graph theory is the extension of traditional graph theory with the study of a graphs 'spectrum' or eigenvectors/eigenvalues. Chung begins her (1992) book by simply stating that spectral graph theory has "a long history". I notice that she's rather more upbeat in her latest book, "Complex graphs and networks":

In many ways, working on graph theory problems over the years has always seemed like fun and games. Recently, through examples of large sparse graphs in realistic networks, research in graph theory has been forging ahead into an exciting new dimension. Graph theory has emerged as a primary tool for detecting numerous hidden structures in various information networks, including Internet graphs, social networks, biological networks, or more generally, any graph representing relations in massive data sets.

I believe this is very clearly true, but don't just take my word for it. There's at least one truly killer example to offer as evidence for it: PageRank is the basis behind Google's search algorithm and is a great example of graph eigen analysis being put to good effect.

If you clicked and read the wikipedia PageRank article above, you might have noticed the complete absence of any reference to graph theory, spectral or otherwise. Instead there's a description of probability and random surfers leading to Markov Chains and then eigengaps. But this is spectral graph theory, and I think it's actually easier to understand the process as such, where random walks and Markov Chains as good family relations of this modern graph theory.

The ten-thousand foot overview goes something like this.

  • The web is a graph.
  • Any graph can also be thought of as a square matrix. Each row/column is a vertex and the matrix values describe the weights of the edges connecting the vertices - this is called the adjacency matrix.
  • All matrices can be decomposed into pairs of "eigenvectors" and "eigenvalues", in the same way sound can be decomposed into differently pitched waves, or light into different colours (hence the term 'spectral').
  • Examining the spectrum of the matrix/graph/web tells you things about it's structure, in the same way you can discover things about an everyday object by listening to the sound it makes when you strike it

I'll expand on it more another time, but that's the main jist of it. I'm really just trying to convey the generality of the subject as I see it. My little description links together graphs, linear algebra and the frequency domain in a major real world example (the web). These are all huge subjects, and I find their proximity very interesting - even exciting. The subject just seems to have that "obvious" but not yet "evident" quality about it.

If you are curious, I think PageRank is a great algorithm to get you into the subject. Personally, I found the most accessible and practical starting point to be the various course notes, slides and pdfs on Daniel Spielman's homepage - particular the course notes. There are huge aspects of the subject in there I haven't even mentioned yet.

* That's not to say traditional graph theory books they aren't worth a read anyway! Fyi, you can get a pdf of, "Graph Theory", by Reinhard Diestel free online. Although, I haven't read it! Gawd bless the interweb and all who sail in her.