On the advantage of overlapping clusters for minimizing conductance

DOI10.1007/S00453-013-9761-8MaRDI QIDQ472486zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

clusteringsocial networksapproximationconductance

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(4)

• Advantage of Overlapping Clusters for Minimizing Conductance
• scientific article; zbMATH DE number 7525512 (Why is no real title available?)
• 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)