1. Convergence of spectral clustering with a general similarity function
- Author
-
Zhou Dingxuan and Gao Wei
- Subjects
Combinatorics ,Discrete mathematics ,Similarity (network science) ,Rate of convergence ,General Mathematics ,Convergence (routing) ,Graph (abstract data type) ,Covering number ,Function (mathematics) ,Lipschitz continuity ,Spectral clustering ,Mathematics - Abstract
Spectral clustering algorithms are generated by eigenfunctions of graph Laplacians associated with similarity functions.In this paper,we prove the convergence of the spectral clustering associated with a general similarity function,and give quantitative estimates for the convergence based on a covering number argument.When the similarity function is Lipschitz s 0 on a subset of a Euclidean space,a convergence rate of O((log(n+1))～(1/2)/n～(1/2)) is verified.We also show that the covering numbers of an involved function set may behave as badly as possible.
- Published
- 2012