Distance plays a fundamental role in measuring similarity between objects. Various visualization techniques and learning tasks in statistics and machine learning such as shape matching, classification, dimension reduction and clustering often rely on some distance or similarity measure. It is of tremendous importance to have a distance that can incorporate the underlying structure of the object. In this paper, we focus on proposing such a distance between network objects. Our key insight is to define a distance based on the long term diffusion behavior of the whole network. We first introduce a dynamic system on graphs called Laplacian flow. Based on this Laplacian flow, a new version of diffusion distance between networks is proposed. We will demonstrate the utility of the distance and its advantage over various existing distances through explicit examples. The distance is also applied to subsequent learning tasks such as clustering network objects.
@cite_9: In systems of dynamical networks, a fundamental role is played by the pattern of connections which determine the interactions among the individual elements of the network. Such patterns of connections are specified by a graph, whose nodes and edges describe the respective units in the network and their mutual connections; graph theory [1-4] therefore constitute a key role in the characterization and investigation of the properties of network structures. The examples of such structures are wide spanned, and in recent years, the organizational structure and characteristics of physical and social networks such as the worldwideweb [5,6], the Internet [7], collaboration networks [8] and small world societies [9], as well as linguistic [10], neural [9,11] and protein folding networks [12], have received substantial scientific attention. In addition, properties of plastic networks with evolving patterns of connections have been considered in [13,14]. A detailed review of many of these studies was given in [15].
@cite_7: We define a number of natural (from geometric and combi- natorial points of view) deformation spaces of valuations on finite graphs, and study functions over these deformation spaces. These functions in- clude both direct metric invariants (girth, diameter), and spectral invari- ants (the determinant of the Laplace operator, or complexity; bottom non-zero eigenvalue of the Laplace operator). We show that almost all of these functions are, surprisingly, convex, and we characterize the valuations extremizing these invariants.
@cite_17: Comparing graphs to determine the level of underlying structural similarity between them is a widely encountered problem in computer science. It is particularly relevant to the study of Internet topologies, such as the generation of synthetic topologies to represent the Internet's AS topology. We derive a new metric that enables exactly such a structural comparison: the weighted spectral distribution. We then apply this metric to three aspects of the study of the Internet's AS topology. i) We use it to quantify the effect of changing the mixing properties of a simple synthetic network generator. ii) We use this quantitative understanding to examine the evolution of the Internet's AS topology over approximately seven years, finding that the distinction between the Internet core and periphery has blurred over time. iii) We use the metric to derive optimal parameterizations of several widely used AS topology generators with respect to a large-scale measurement of the real AS topology.
Since the graph Laplacian matrix is symmetric and positive-semidefinite, eigenvalues of @math are nonnegative real numbers. Jakobson and Rivin exploited such phenomenon by defining the distance measure by taking normalized sum of squared differences for top eigenvalues @cite_7 . Instead of using eigenvalues directly, some chose to compute the disparity of two approximated distributions of spectrum. Ipsen and Mikhailov, in @cite_9 , suggested to apply kernel density estimation by convolving narrow Lorentz distributions with computed eigenvalues, while employed discrete histogram through binning @cite_17 .