TY - JOUR AU - Filippone, M. AU - Camastra, F. AU - Masulli, F. AU - Rovetta, S. T1 - A survey of kernel and spectral methods for clustering JO - Pattern recognition PY - 2008/ VL - 41 IS - 1 SP - 176 EP - 190 UR - DO - KW - community KW - detection KW - graph KW - kernel KW - spectral KW - survey KW - theory L1 - SN - N1 - N1 - AB - ER - TY - CONF AU - Symeonidis, Panagiotis AU - Nanopoulos, Alexandros AU - Manolopoulos, Yannis A2 - T1 - Tag recommendations based on tensor dimensionality reduction T2 - RecSys '08: Proceedings of the 2008 ACM conference on Recommender systems PB - ACM C1 - New York, NY, USA PY - 2008/ CY - VL - IS - SP - 43 EP - 50 UR - http://portal.acm.org/citation.cfm?id=1454017 DO - http://doi.acm.org/10.1145/1454008.1454017 KW - community KW - detection KW - graph KW - recommender KW - spectral KW - tag KW - theory L1 - SN - 978-1-60558-093-7 N1 - N1 - AB - ER - TY - JOUR AU - Luxburg, Ulrike T1 - A tutorial on spectral clustering JO - Statistics and Computing PY - 2007/ VL - 17 IS - 4 SP - 395 EP - 416 UR - http://portal.acm.org/citation.cfm?id=1288832 DO - http://dx.doi.org/10.1007/s11222-007-9033-z KW - community KW - detection KW - graph KW - spectral KW - theory L1 - SN - N1 - N1 - AB - ER - TY - JOUR AU - Newman, MEJ T1 - Finding community structure in networks using the eigenvectors of matrices JO - Physical Review E PY - 2006/ VL - 74 IS - 3 SP - EP - UR - DO - KW - community KW - detection KW - graph KW - modularity KW - spectral KW - theory L1 - SN - N1 - N1 - AB - ER - TY - JOUR AU - Newman, MEJ T1 - Modularity and community structure in networks JO - Proceedings of the National Academy of Sciences PY - 2006/ VL - 103 IS - 23 SP - 8577 EP - 8582 UR - DO - KW - community KW - detection KW - graph KW - modularity KW - spectral KW - theory L1 - SN - N1 - N1 - AB - ER - TY - RPRT AU - Dhillon, Inderjit S. AU - Guan, Yuqiang AU - Kulis, Brian A2 - T1 - A Unified View of Kernel k-means, Spectral Clustering and Graph Cuts PB - University of Texas Dept. of Computer Science AD - PY - 2005/ VL - IS - TR-04-25 SP - EP - UR - http://www.cs.utexas.edu/ftp/pub/techreports/tr04-25.pdf DO - KW - community KW - detection KW - graph KW - k-means KW - spectral KW - theory L1 - N1 - N1 - N1 - AB - Recently, a variety of clustering algorithms have been proposed to handle data that is not linearly separable. Spectral clustering and kernel k-means are two such methods that are seemingly quite different. In this paper, we show that a general weighted kernel k-means objective is mathematically equivalent to a weighted graph partitioning objective. Special cases of this graph partitioning objective include ratio cut, normalized cut and ratio association. Our equivalence has important consequences: the weighted kernel k-means algorithm may be used to directly optimize the graph partitioning objectives, and conversely, spectral methods may be used to optimize the weighted kernel k-means objective. Hence, in cases where eigenvector computation is prohibitive, we eliminate the need for any eigenvector computation for graph partitioning. Moreover, we show that the Kernighan-Lin objective can also be incorporated into our framework, leading to an incremental weighted kernel k-means algorithm for local optim ization of the objective. We further discuss the issue of convergence of weighted kernel k-means for an arbitrary graph affinity matrix and provide a number of experimental results. These results show that non-spectral methods for graph partitioning are as effective as spectral methods and can be used for problems such as image segmentation in addition to data clustering. ER - TY - JOUR AU - White, S. AU - Smyth, P. T1 - A spectral clustering approach to finding communities in graph JO - PY - 2005/ VL - IS - SP - EP - UR - DO - KW - community KW - detection KW - graph KW - spectral KW - theory L1 - SN - N1 - N1 - AB - ER - TY - JOUR AU - Estrada, E. AU - Rodriguez-Velázquez, J.A. T1 - Spectral measures of bipartivity in complex networks JO - SIAM Rev Phys Rev E PY - 2003/ VL - 72 IS - SP - EP - UR - DO - KW - bipartite KW - community KW - detection KW - graph KW - modularity KW - spectral KW - theory L1 - SN - N1 - N1 - AB - ER - TY - JOUR AU - Verma, D. AU - Meila, M. T1 - A comparison of spectral clustering algorithms JO - University of Washington, Tech. Rep. UW-CSE-03-05-01 PY - 2003/ VL - IS - SP - EP - UR - DO - KW - community KW - detection KW - graph KW - spectral KW - theory L1 - SN - N1 - N1 - AB - ER - TY - CONF AU - Dhillon, Inderjit S. A2 - T1 - Co-clustering documents and words using bipartite spectral graph partitioning T2 - KDD '01: Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining PB - ACM Press C1 - New York, NY, USA PY - 2001/ CY - VL - IS - SP - 269 EP - 274 UR - http://portal.acm.org/citation.cfm?id=502512.502550 DO - 10.1145/502512.502550 KW - community KW - detection KW - graph KW - spectral KW - theory L1 - SN - 158113391X N1 - N1 - AB - ER - TY - CONF AU - Ng, Andrew Y. AU - Jordan, Michael I. AU - Weiss, Yair A2 - T1 - On spectral clustering: Analysis and an algorithm T2 - Advances in Neural Information Processing Systems 14 PB - MIT Press C1 - PY - 2001/ CY - VL - IS - SP - 849 EP - 856 UR - DO - KW - clustering KW - community KW - detection KW - graph KW - spectral KW - theory L1 - SN - N1 - N1 - AB - Despite many empirical successes of spectral clustering methods| algorithms that cluster points using eigenvectors of matrices derived from the data|there are several unresolved issues. First, there are a wide variety of algorithms that use the eigenvectors in slightly dierent ways. Second, many of these algorithms have no proof that they will actually compute a reasonable clustering. In this paper, we present a simple spectral clustering algorithm that can be implemented using a few lines of Matlab. Using tools from matrix perturbation theory, we analyze the algorithm, and give conditions under which it can be expected to do well. We also show surprisingly good experimental results on a number of challenging clustering problems. 1 ER - TY - RPRT AU - Spielman, Daniel A. AU - Teng, Shang A2 - T1 - Spectral Partitioning Works: Planar Graphs and Finite Element Meshes PB - AD - Berkeley, CA, USA PY - 1996/ VL - IS - SP - EP - UR - DO - KW - clustering KW - community KW - detection KW - graph KW - spectral KW - survey KW - theory L1 - N1 - N1 - N1 - AB - ER - TY - CONF AU - Alpert, Charles J. AU - Kahng, Andrew B. AU - zen Yao, So A2 - T1 - Spectral partitioning: The more eigenvectors, the better T2 - Proc. ACM/IEEE Design Automation Conf PB - C1 - PY - 1995/ CY - VL - IS - SP - 195 EP - 200 UR - DO - KW - community KW - detection KW - graph KW - spectral KW - theory L1 - SN - N1 - N1 - AB - ER - TY - JOUR AU - Chan, Pak K. AU - Schlag, Martine D. F. AU - Zien, Jason Y. T1 - Spectral K-way ratio-cut partitioning and clustering. JO - IEEE Trans. on CAD of Integrated Circuits and Systems PY - 1994/ VL - 13 IS - 9 SP - 1088 EP - 1096 UR - http://dblp.uni-trier.de/db/journals/tcad/tcad13.html#ChanSZ94 DO - KW - community KW - detection KW - graph KW - partitioning KW - spectral KW - theory L1 - SN - N1 - N1 - AB - ER - TY - JOUR AU - Pothen, A. AU - Simon, H.D. AU - Liou, K.P. T1 - Partitioning Sparse Matrices with Eigenvectors of Graphs JO - SIAM J. MATRIX ANAL. APPLIC. PY - 1990/ VL - 11 IS - 3 SP - 430 EP - 452 UR - http://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19970011963_1997016998.pdf DO - KW - clustering KW - community KW - graph KW - partitioning KW - spectral KW - theory L1 - SN - N1 - N1 - AB - ER - TY - JOUR AU - Donath, W.E. AU - Hoffman, A.J. T1 - Lower bounds for the partitioning of graphs JO - IBM Journal of Research and Development PY - 1973/ VL - 17 IS - 5 SP - 420 EP - 425 UR - DO - KW - clustering KW - community KW - detection KW - graph KW - spectral KW - theory L1 - SN - N1 - N1 - AB - ER -