On the advantage of overlapping clusters for minimizing conductance

DOI10.1007/S00453-013-9761-8zbMATH Open1303.05196OpenAlexW2026511931MaRDI QIDQ472486FDOQ472486

Authors: Rohit Khandekar, Guy Kortsarz, Vahab S. Mirrokni 

Publication date: 19 November 2014

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-013-9761-8

Recommendations

• Advantage of Overlapping Clusters for Minimizing Conductance
• Graph-Based Data Clustering with Overlaps
• Graph-based data clustering with overlaps
• Overlapping Clustering in a Graph Using k-Means and Application to Protein Interactions Networks
• Top-\(k\) overlapping densest subgraphs

zbMATH Keywords

clusteringsocial networksapproximationconductance

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Social networks; opinion dynamics (91D30) Approximation algorithms (68W25)

Cites Work

• The dense \(k\)-subgraph problem
• Engineering graph clustering: models and experimental evaluation
• Title not available (Why is that?)
• Euclidean distortion and the sparsest cut (extended abstract)
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Min-max Graph Partitioning and Small Set Expansion
• Expander flows, geometric embeddings and graph partitioning
• Hearing the clusters of a graph: A distributed algorithm
• Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut
• Finding k Cuts within Twice the Optimal
• Primal-dual approximation algorithms for integral flow and multicut in trees
• On distance scales, embeddings, and efficient relaxations of the cut cone
• Fast Approximate Graph Partitioning Algorithms
• The importance of being biased
• An improved approximation algorithm of MULTIWAY CUT.
• \(O(\sqrt{\log n})\) approximation to sparsest cut in \(\tilde{O}(n^2)\) time
• Approximating directed multicuts
• Hardness of cut problems in directed graphs
• Polynomial flow-cut gaps and hardness of directed cut problems
• Improved approximation for directed cut problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Multi-assignment clustering for Boolean data
• Clustering Social Networks
• Greedy approximation algorithms for directed multicuts
• Graph partitioning using single commodity flows

Cited In (4)

• Advantage of Overlapping Clusters for Minimizing Conductance
• Title not available (Why is that?)
• Model selection strategies for determining the optimal number of overlapping clusters in additive overlapping partitional clustering
• Highly efficient stepped wedge designs for clusters of unequal size

This page was built for publication: On the advantage of overlapping clusters for minimizing conductance

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