On clusterings: good, bad and spectral

DOI10.1145/990308.990313zbMATH Open1192.05160OpenAlexW2034331023WikidataQ29999158 ScholiaQ29999158MaRDI QIDQ3583579FDOQ3583579

Authors: Adrian Vetta, R. Kannan, Santosh S. Vempala 

Publication date: 17 August 2010

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/990308.990313

Recommendations

• Consistency of spectral clustering
• Partitioning well-clustered graphs: spectral clustering works!
• Spectral Clustering by Recursive Partitioning
• Good (K-means) clusterings are unique (up to small perturbations)
• Spectral concentration and greedy \(k\)-clustering

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40)

Cited In (87)

• On the Paley graph of a quadratic character
• Community detection via a triangle and edge combination conductance partitioning
• Mixed-case community detection problem in social networks: algorithms and analysis
• Local flow partitioning for faster edge connectivity
• Group-Level Analysis and Visualization of Social Networks
• Graph ambiguity
• Improving spectral bounds for clustering problems by Lagrangian relaxation
• On a class of nonlocal continuity equations on graphs
• Spatial regression and estimation of disease risks: A clustering‐based approach
• Testing higher-order clusterability on graphs
• Hypergraph clustering using a new Laplacian tensor with applications in image processing
• Good (K-means) clusterings are unique (up to small perturbations)
• Experiments on density-constrained graph clustering
• Good clusterings have large volume
• Incremental methods for community detection in both fully and growing dynamic networks
• Finding large expanders in graphs: from topological minors to induced subgraphs
• Bounded confidence opinion dynamics: a survey
• Networks synchronizability, local dynamics and some graph invariants
• Probabilistic correlation clustering and image partitioning using perturbed multicuts
• The maximum community partition problem in networks
• Mining representative subset based on fuzzy clustering
• Mean curvature, threshold dynamics, and phase field theory on finite graphs
• Clustering with \(r\)-regular graphs
• A spectral clustering-based framework for detecting community structures in complex networks
• Lower bounds on paraclique density
• Improved row-by-row method for binary quadratic optimization problems
• A decentralized algorithm for spectral analysis
• Spectral concentration and greedy \(k\)-clustering
• Spectral clustering based on matrix perturbation theory
• A Cheeger-type inequality on simplicial complexes
• Asymptotic regularity of subdivisions of Euclidean domains by iterated PCA and iterated 2-means
• Structural similarity: spectral methods for relaxed blockmodeling
• Spectral Clustering by Recursive Partitioning
• Consistency of spectral clustering
• Graph partitioning via adaptive spectral techniques
• Tree-based coarsening and partitioning of complex networks
• Nonlocal-interaction equation on graphs: gradient flow structure and continuum limit
• Go with the flow, on Jupiter and snow. Coherence from model-free video data without trajectories
• Density-constrained graph clustering
• Diffusion operator and spectral analysis for directed hypergraph Laplacian
• From graph cuts to isoperimetric inequalities: convergence rates of Cheeger cuts on data clouds
• Convex programming based spectral clustering
• Finding and using expanders in locally sparse graphs
• Grouping objects in multi-band images using an improved eigenvector-based algorithm
• Graph Clustering using Effective Resistance
• Automatically finding clusters in normalized cuts
• The small-community phenomenon in networks
• The Small Community Phenomenon in Networks: Models, Algorithms and Applications
• Mixed Hölder matrix discovery via wavelet shrinkage and Calderón-Zygmund decompositions
• Maximizing edge-ratio is NP-complete
• Cluster forests
• Shared farthest neighbor approach to clustering of high dimensionality, low cardinality data
• Multiway spectral clustering: a margin-based perspective
• Multicuts and perturb \& MAP for probabilistic graph clustering
• Soft memberships for spectral clustering, with application to permeable language distinction
• Partitioning well-clustered graphs: spectral clustering works!
• A survey of kernel and spectral methods for clustering
• Optimality of spectral clustering in the Gaussian mixture model
• Frequency-based views to pattern collections
• Kernel spectral clustering with memory effect
• Computing heat kernel PageRank and a local clustering algorithm
• Solution of Boolean quadratic programming problems by two augmented Lagrangian algorithms based on a continuous relaxation
• Structure- and Physics-Preserving Reductions of Power Grid Models
• Estimating perimeter using graph cuts
• Memetic graph clustering
• Mean shift spectral clustering
• Cortical spatiotemporal dimensionality reduction for visual grouping
• An ideal point based many-objective optimization for community detection of complex networks
• Finding large \(k\)-clubs in undirected graphs
• 3D human posture segmentation by spectral clustering with surface normal constraint
• Fuzzy spectral clustering by PCCA+: application to Markov state models and data classification
• SpectralCAT: categorical spectral clustering of numerical and nominal data
• Improved spectral-norm bounds for clustering
• Well-mixing vertices and almost expanders
• Dynamic Graph Clustering Using Minimum-Cut Trees
• Randomized approximation schemes for cuts and flows in capacitated graphs
• Algorithmic extensions of Cheeger's inequality to higher eigenvalues and partitions
• Spectral clustering and its use in bioinformatics
• Community detection based on network communicability
• Graph clustering
• Spectral clustering revisited: information hidden in the Fiedler vector
• Hierarchical Community Detection by Recursive Partitioning
• Guaranteed clustering and biclustering via semidefinite programming
• Community detection by resistance distance: automation and benchmark testing
• Clustering and outlier detection using isoperimetric number of trees
• Spectral clustering based on local linear approximations
• Generalizing the hypergraph Laplacian via a diffusion process with mediators

This page was built for publication: On clusterings: good, bad and spectral

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3583579)