کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
379163 | 659271 | 2009 | 24 صفحه PDF | دانلود رایگان |
This work addresses the problem of detecting clusters in a weighted, undirected, graph by using kernel-based clustering methods, directly partitioning the graph according to a well-defined similarity measure between the nodes (a kernel on a graph). The proposed algorithms are based on a two-step procedure. First, a kernel or similarity matrix, providing a meaningful similarity measure between any couple of nodes, is computed from the adjacency matrix of the graph. Then, the nodes of the graph are clustered by performing a kernel clustering on this similarity matrix. Besides the introduction of a prototype-based kernel version of the gaussian mixtures model and Ward’s hierarchical clustering, in addition to the already known kernel k-means and fuzzy k -means, a new kernel, called the sigmoid commute-time kernel (KCTS) is presented. The joint use of the KCTS kernel matrix and kernel clustering appears to be quite effective. Indeed, this methodology provides the best results on a systematic comparison with a selection of graph clustering and communities detection algorithms on three real-world databases. Finally, some links between the proposed hierarchical kernel clustering and spectral clustering are examined.
Journal: Data & Knowledge Engineering - Volume 68, Issue 3, March 2009, Pages 338–361