模式识别与人工智能
Thursday, Apr. 3, 2025 Home      About Journal      Editorial Board      Instructions      Ethics Statement      Contact Us                   中文
  2006, Vol. 19 Issue (5): 674-679    DOI:
Researches and Applications Current Issue| Next Issue| Archive| Adv Search |
Graph Spectral Decomposition and Clustering
KONG Min1,2, CHEN SiBao1, ZHAO HaiFeng1, LUO Bin1
1.School of Computer Science and Technology, Anhui University, Hefei 230039
2.Department of Machine and Electron Engineering, West Anhui University, Lu’an 237012

Download: PDF (876 KB)   HTML (1 KB) 
Export: BibTeX | EndNote (RIS)      
Abstract  This paper explore how to use spectral methods for embedding and clustering unweighted graphs. The leading eignvectors of the graph adjacency matrix are employed to define eignmodes of the adjacency matrix. For each eigenmode, vectors of spectral properties are computed as feature vectors. These properties include the eigenmode perimeter, eigenmode volume, Cheeger number, intermode adjacency matrices and intermode edgedistance. Then these vectors are embedded in a patternspace using two contrasting approachs. The first of these involves performing principal or independent component analysis on the covariance matrix for the spectral pattern vectors. The second approach involves performing multidimensional scaling on the L2 norm for pairs of patten vectors. This paper also illustrate the utility of the embedding methods on neighbourhood graphs representing the arrangement of corner features in 2D images of 3D polyhedral objects. Experimental results show that clustering graphs using spectral properties of graphs is practical and effective.
Key wordsGraph Spectra      Graph Clustering      Principal Component Analysis      Independent Component Analysis      Multidimensional Scaling     
Received: 03 March 2005     
ZTFLH: TP391.41  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
KONG Min
CHEN SiBao
ZHAO HaiFeng
LUO Bin
Cite this article:   
KONG Min,CHEN SiBao,ZHAO HaiFeng等. Graph Spectral Decomposition and Clustering[J]. , 2006, 19(5): 674-679.
URL:  
http://manu46.magtech.com.cn/Jweb_prai/EN/      OR     http://manu46.magtech.com.cn/Jweb_prai/EN/Y2006/V19/I5/674
Copyright © 2010 Editorial Office of Pattern Recognition and Artificial Intelligence
Address: No.350 Shushanhu Road, Hefei, Anhui Province, P.R. China Tel: 0551-65591176 Fax:0551-65591176 Email: bjb@iim.ac.cn
Supported by Beijing Magtech  Email:support@magtech.com.cn