Clustering Large Graphs via the Singular Value Decomposition

Petros Drineas; Alan Frieze; Ravi Kannan; S. Vempala; Vishwa Vinay

doi:10.1023/b:mach.0000033113.59016.96

Keywords

Singular value decompositionMathematicsCluster analysisSingular valueRelaxation (psychology)CombinatoricsMatrix (chemical analysis)Subspace topologyEuclidean spaceAlgorithmDiscrete mathematicsEigenvalues and eigenvectorsMathematical analysis

Affiliated Institutions

Related Publications

On coresets for k-means and k-median clustering

Sariel Har-Peled , Soham Mazumdar

In this paper, we show the existence of small coresets for the problems of computing k-median and k-means clustering for points in low dimension. In other words, we show that gi...

2004 486 citations

A Direct Formulation for Sparse PCA Using Semidefinite Programming

Alexandre d’Aspremont , Laurent El Ghaoui , Michael I. Jordan +1 more

Given a covariance matrix, we consider the problem of maximizing the variance explained by a particular linear combination of the input variables while constraining the number o...

2007 SIAM Review 666 citations

Cross-Validatory Choice of the Number of Components From a Principal Component Analysis

Henry T. Eastment , W. J. Krzanowski

A method is described for choosing the number of components to retain in a principal component analysis when the aim is dimensionality reduction. The correspondence between prin...

1982 Technometrics 359 citations

Some distance properties of latent root and vector methods used in multivariate analysis

J. C. Gower

This paper is concerned with the representation of a multivariate sample of size n as points P1, P2, …, Pn in a Euclidean space. The interpretation of the distance Δ(Pi, Pj) bet...

1966 Biometrika 3981 citations

A Singular Value Thresholding Algorithm for Matrix Completion

Jian‐Feng Cai , Emmanuel J. Candès , Zuowei Shen

This paper introduces a novel algorithm to approximate the matrix with minimum nuclear norm among all matrices obeying a set of convex constraints. This problem may be understoo...

2010 SIAM Journal on Optimization 5710 citations

Publication Info

Year: 2004
Type: article
Volume: 56
Issue: 1-3
Pages: 9-33
Citations: 472
Access: Closed

External Links

View on DOI.org

Social Impact

Altmetric

Clustering Large Graphs via the Singular Value Decomposition

PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

472

OpenAlex

Cite This

APA Style

                            
                                
                                    Petros Drineas, 
                                
                                    Alan Frieze, 
                                
                                    Ravi Kannan
                                
                                et al.
                            
                            (2004). 
                            Clustering Large Graphs via the Singular Value Decomposition. 
                            Machine Learning
                            , 56
                            (1-3)
                            , 9-33.
                            https://doi.org/10.1023/b:mach.0000033113.59016.96
                        

Identifiers

DOI: 10.1023/b:mach.0000033113.59016.96