6.9 Conclusions
Comparison of graph structures is a frequently encountered problem across many scientific areas. To perform a meaningful comparison requires the definition of a cost–function that encodes those features of each graph considered important. While the spectrum of a graph encodes a graph's features, the raw spectrum contains too much information to be useful on its own. In this chapter, we have introduced a new metric, the weighted spectral distribution, that improves on the raw graph spectrum by discounting those eigenvalues believed to be less significant and noisy, while emphasizing the contribution of those believed to be important and information-rich.
We then showed the use of this cost–function to optimize the selection of parameter values for the subject of Internet topology generation. The cost–function defined by the weighted graph spectrum was shown to lead to parameter choices that are appropriate in the context of the particular problem domain: Internet topology generation. In particular, we showed that the parameter choices so made are close to the default values and, in for one particular graph-generator (BA), fall within the expected region. In addition, as the metric is formed through summation, it is possible to go further and identify the particular eigenvalues that are responsible for significant differences. Although it is currently difficult to assign specific features to specific eigenvalues, we hope that this will also become a feature of the weighted spectral distribution in the future. Finally, we briefly demonstrated a technique for projecting the raw WSD distributions into a lower dimensional space. This makes comparison of different distributions straightforward, as shown by the clear evolution of the Internet's topology viewed through the UCLA dataset.
Notes
1. That is, the eigenvalues at the center of the spectrum.
2. The eigenvalues of a given graph are deterministic and so distribution here is not meant in a statistical sense.
3. K can be increased depending on the granularity required.
4. We found similar results for other parameters and topology generators.
5. Multiplied by a factor of ten for clarity.
6. The six comes from the fact that the random walk can start in one of the three nodes and go in one of the two directions. It can be viewed in our case as really just a nuisance scaling factor.
7. Note that if we had used the adjacency matrix instead of the normalized Laplacian the rewiring would have no effect on the sum of the eigenvalues.
8. This is closely related to the settling times in Markov chains, which are often expressed in terms of the largest nontrivial eigenvalue. It differs in that the Walk Laplacian and not the normalized Laplacian is used.
9. In Ref. [12] we present an even larger set of measures.
10. http://www.routeviews.org/
12. http://www.caida.org/tools/measurement/Skitter/
13. http://irl.cs.ucla.edu/topology/
14. http://www.ripe.net/db/irr.html
15. http://abilene.internet2.edu/
16. We present an extended set of metrics in Ref. [12] which further support our claims; we restrict ourselves here to only the most significant results.