The principal components analysis of a graph, and its relationships to spectral clustering

摘要: This work presents a novel procedure for computing (1) distances between nodes of weighted, undirected, graph, called the Euclidean Commute Time Distance (ECTD), and (2) subspace projection graph that preserves as much variance possible, in terms ECTD – principal components analysis graph. It is based on Markov-chain model random walk through The assigns transition probabilities to links nodes, so walker can jump from node node. A quantity, average commute time, computes time taken by reaching j first when starting i, coming back i. square root this ECTD, distance measure any two has nice property decreasing number paths connecting increases "length" path decreases. be computed pseudoinverse Laplacian matrix which kernel. We finally define Principal Components Analysis (PCA) ECTD. PCA some interesting with spectral theory, particular clustering.