Line Orthogonality in Adjacency Eigenspace with Application to Community Partition

Wu, Leting; Ying, Xiaowei; Wu, Xintao; Zhou, Zhi-Hua

doi:10.5591/978-1-57735-516-8/IJCAI11-391

Line Orthogonality in Adjacency Eigenspace with Application to Community Partition

Leting Wu, Xiaowei Ying, Xintao Wu, Zhi-Hua Zhou

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 2349-2353.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-391

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 first projects node coordinates to the unit sphere and then applies the classic k-means to find clusters. Empirical evaluations on synthetic data and real-world social networks validate our theoretical findings and show the effectiveness of our graph partition algorithm.

Leting Wu, Xiaowei Ying, Xintao Wu, and Zhi-Hua Zhou. 2011. Line Orthogonality in Adjacency Eigenspace with Application to Community Partition. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 2349–2353. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-391

@inproceedings{ijcai2011p391,
  title     = {Line Orthogonality in Adjacency Eigenspace with Application to Community Partition},
  author    = {Wu, Leting and Ying, Xiaowei and Wu, Xintao and Zhou, Zhi-Hua},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {2349--2353},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-391},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-391},
}

TY  - CPAPER
TI  - Line Orthogonality in Adjacency Eigenspace with Application to Community Partition
AU  - Wu, Leting
AU  - Ying, Xiaowei
AU  - Wu, Xintao
AU  - Zhou, Zhi-Hua
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 2349
EP  - 2353
DO  - 10.5591/978-1-57735-516-8/IJCAI11-391
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-391
ER  -