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.
Recently, an interesting work adopted diffusion dynamics on a graph to characterize and distinguish networks. The work is based on the manifold learning method called Diffusion Maps @cite_1 , where the distance between two nodes takes all possible paths in between into account across different timescale. This implies that each network and its topological properties can be well presented by the diffusion process. In @cite_13 , adopted such idea to define graph diffusion distance that measures dissimilarity of two networks and showed it is indeed a metric.
@cite_13 @cite_1
2962824627 1992151851
Nonlinear manifold learning algorithms, such as diffusion maps, have been fruitfully applied in recent years to the analysis of large and complex data sets. However, such algorithms still encounter challenges when faced with real data. One such challenge is the existence of “repeated eigendirections,” which obscures the detection of the true dimensionality of the underlying manifold and arises when several embedding coordinates parametrize the same direction in the intrinsic geometry of the data set. We propose an algorithm, based on local linear regression, to automatically detect coordinates corresponding to repeated eigendirections. We construct a more parsimonious embedding using only the eigenvectors corresponding to unique eigendirections, and we show that this reduced diffusion maps embedding induces a metric which is equivalent to the standard diffusion distance. We first demonstrate the utility and flexibility of our approach on synthetic data sets. We then apply our algorithm to data collected from a stochastic model of cellular chemotaxis, where our approach for factoring out repeated eigendirections allows us to detect changes in dynamical behavior and the underlying intrinsic system dimensionality directly from data. Topological properties of "scale-free" networks are investigated by determining their spectral dimensions d(S), which reflect a diffusion process in the corresponding graphs. Data bases for citation networks and metabolic networks together with simulation results from the growing network model [A.-L. Barabasi and R. Albert, Science 286, 509 (1999)] are probed. For completeness and comparisons lattice, random and small-world models are also investigated. We find that d(S) is around 3 for citation and metabolic networks, which is significantly different from the growing network model, for which d(S) is approximately 7.5. This signals a substantial difference in network topology despite the observed similarities in vertex-order distributions. In addition, the diffusion analysis indicates that the citation networks are treelike in structure, whereas the metabolic networks contain many loops. (Less)