Statistical and Machine Learning Approaches for Network Analysis

6.1 Introduction

Graph comparison is a problem that occurs in many branches of computing, from vision to speech processing to systems. Many techniques exist for graph comparison, for example, the edit distance [1] (the number of link and node additions or deletions required to turn one graph into another), or counting the number of common substructures in two graphs [2]. Unfortunately, these methods are too computationally expensive for large graphs such as the Internet topologies studied here. Moreover, they are inappropriate for dynamic graphs, resulting in varying edit distances or substructure counts. Currently used common “metrics” include the clustering coefficient, the assortativity coefficient, the node degree distribution, and the k-core decomposition. However, these are not metrics in the mathematical sense, but rather are measures. This distinction is important as a measure cannot be used to determine unique differences between graphs: two graphs with the same measures may not in fact be the same. For example, two graphs may have the same clustering coefficient but hugely different structures.

In this chapter, we present the weighted spectral distribution (WSD), a true metric in the mathematical sense, which compares graphs based on the distribution of a decomposition of their structure. Specifically, the WSD is based on the spectrum of the normalized Laplacian matrix and is thus strongly associated with the distribution of random walk cycles in a network. A random walk ...