Line Orthogonality in Adjacency Eigenspace with Application to Community Partition
Abstract
Different from Laplacian or normal matrix, the properties of the adjacency eigenspace received much less attention. Recent work showed that nodes projected into the adjacency eigenspace exhibit an orthogonal line pattern and nodes from the same community locate along the same line. In this paper, we conduct theoretical studies based on graph perturbation to demonstrate why this line orthogonality property holds in the adjacency eigenspace and why it generally disappears in the Laplacian and normal eigenspaces. Using the orthogonality property in the adjacency eigenspace, we present a graph partition algorithm, AdjCluster, which ?rst projects node coordinates to the unit sphere and then applies the classic k-means to ?nd clusters. Empirical evaluations on synthetic data and real-world social networks validate our theoretical ?ndings and show the effectiveness of our graph partition algorithm .