On clusterings

DOI10.1145/990308.990313zbMath1192.05160WikidataQ29999158 ScholiaQ29999158MaRDI QIDQ3583579

Adrian Vetta, Ravindran Kannan, Santosh 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

Mathematics Subject Classification ID

68W40: Analysis of algorithms

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Finding and Using Expanders in Locally Sparse Graphs, Structure- and Physics-Preserving Reductions of Power Grid Models, Spatial regression and estimation of disease risks: A clustering‐based approach, Well-mixing vertices and almost expanders, Graph Clustering using Effective Resistance, Hypergraph Clustering Using a New Laplacian Tensor with Applications in Image Processing, Local Flow Partitioning for Faster Edge Connectivity, Estimating perimeter using graph cuts, Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs, Tree-Based Coarsening and Partitioning of Complex Networks, Memetic Graph Clustering, Cortical Spatiotemporal Dimensionality Reduction for Visual Grouping, Partitioning Well-Clustered Graphs: Spectral Clustering Works!, Generalizing the hypergraph Laplacian via a diffusion process with mediators, Dynamic Graph Clustering Using Minimum-Cut Trees, A decentralized algorithm for spectral analysis, Community detection via a triangle and edge combination conductance partitioning, Hierarchical Community Detection by Recursive Partitioning, Structural similarity: spectral methods for relaxed blockmodeling, Multicuts and perturb \& MAP for probabilistic graph clustering, Fuzzy spectral clustering by PCCA+: application to Markov state models and data classification, A Cheeger-type inequality on simplicial complexes, Graph clustering, Guaranteed clustering and biclustering via semidefinite programming, Finding large \(k\)-clubs in undirected graphs, Grouping objects in multi-band images using an improved eigenvector-based algorithm, 3D human posture segmentation by spectral clustering with surface normal constraint, SpectralCAT: categorical spectral clustering of numerical and nominal data, Automatically finding clusters in normalized cuts, Asymptotic regularity of subdivisions of Euclidean domains by iterated PCA and iterated 2-means, Maximizing edge-ratio is NP-complete, Shared farthest neighbor approach to clustering of high dimensionality, low cardinality data, Spectral clustering and its use in bioinformatics, Clustering and outlier detection using isoperimetric number of trees, Multiway spectral clustering: a margin-based perspective, Soft memberships for spectral clustering, with application to permeable language distinction, A spectral clustering-based framework for detecting community structures in complex networks, Spectral concentration and greedy \(k\)-clustering, Mixed Hölder matrix discovery via wavelet shrinkage and Calderón-Zygmund decompositions, Kernel spectral clustering with memory effect, Computing heat kernel PageRank and a local clustering algorithm, Cluster forests, 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, Convex programming based spectral clustering, Optimality of spectral clustering in the Gaussian mixture model, Spectral clustering revisited: information hidden in the Fiedler vector, Community detection by resistance distance: automation and benchmark testing, From graph cuts to isoperimetric inequalities: convergence rates of Cheeger cuts on data clouds, Mixed-case community detection problem in social networks: algorithms and analysis, An ideal point based many-objective optimization for community detection of complex networks, Mean curvature, threshold dynamics, and phase field theory on finite graphs, Clustering with \(r\)-regular graphs, Solution of Boolean quadratic programming problems by two augmented Lagrangian algorithms based on a continuous relaxation, Diffusion operator and spectral analysis for directed hypergraph Laplacian, Improved row-by-row method for binary quadratic optimization problems, A survey of kernel and spectral methods for clustering, Consistency of spectral clustering, Graph ambiguity, Mean shift spectral clustering, Frequency-based views to pattern collections, Spectral clustering based on matrix perturbation theory, Finding large expanders in graphs: from topological minors to induced subgraphs, Community detection based on network communicability, Experiments on Density-Constrained Graph Clustering, THE MAXIMUM COMMUNITY PARTITION PROBLEM IN NETWORKS, The small-community phenomenon in networks, The Small Community Phenomenon in Networks: Models, Algorithms and Applications, Networks Synchronizability, Local Dynamics and Some Graph Invariants, Algorithmic Extensions of Cheeger’s Inequality to Higher Eigenvalues and Partitions, Probabilistic Correlation Clustering and Image Partitioning Using Perturbed Multicuts, Graph Partitioning via Adaptive Spectral Techniques, Mining representative subset based on fuzzy clustering, Group-Level Analysis and Visualization of Social Networks