Compressive sensing for cut improvement and local clustering

DOI10.1137/19M1265971MaRDI QIDQ5027032zbMATH OpenFDO

Authors Ming-Jun Lai, Daniel McKenzie

Publication date 3 February 2022

Published in SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.05780

zbMATH Keywords

cluster extractioncommunity detectioncompressive sensingcut improvementgraph Laplacianlocal clusteringsemisupervised clusteringsparse solution

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Learning and adaptive systems in artificial intelligence (68T05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Recommendations

• Flow-based algorithms for local graph clustering
• A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning
• Improved algorithms for the random cluster graph model
• scientific article; zbMATH DE number 2089226
• Variational perspective on local graph clustering

Cites work

• A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning
• A mathematical introduction to compressive sensing
• A proof of the block model threshold conjecture
• A testing based extraction algorithm for identifying significant communities in networks
• An algorithm for improving graph partitions
• An effective region force for some variational models for learning and clustering
• Auction dynamics: a volume constrained MBO scheme
• Community detection and stochastic block models: recent developments
• Community structure in social and biological networks
• Compressed sensing
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• Flow-based algorithms for local graph clustering
• scientific article; zbMATH DE number 6276186 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• Introduction to Random Graphs
• Mixing local and global information for community detection in large networks
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• On the spectra of general random graphs
• Principal submatrices. IX: Interlacing inequalities for singular values of submatrices
• Quasi‐random graphs with given degree sequences
• Random graphs.
• Random walks and local cuts in graphs
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Subspace Pursuit for Compressive Sensing Signal Reconstruction
• Using PageRank to Locally Partition a Graph
• Vertices of given degree in a random graph

Cited in

(5)

• On Cluster-Aware Supervised Learning: Frameworks, Convergent Algorithms, and Applications
• K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance
• Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance
• A compressed sensing based least squares approach to semi-supervised local cluster extraction
• Compressive Sensing for cut improvement and local clustering

Describes a project that uses

Uses Software

• CoSaMP
• ESSC

This page was built for publication: Compressive sensing for cut improvement and local clustering

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