On a connection between small set expansions and modularity clustering

DOI10.1016/J.IPL.2014.02.004MaRDI QIDQ2446591zbMATH OpenOpenAlexFDO

Authors Devendra Desai, Bhaskar Dasgupta

Publication date 17 April 2014

Published in Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

social networktheory of computationmodularity clusteringsmall-set expansion

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Social networks; opinion dynamics (91D30) Random walks on graphs (05C81) Network design and communication in computer systems (68M10)

Abstract: In this paper we explore a connection between two seemingly different problems from two different domains: the small-set expansion problem studied in unique games conjecture, and a popular community finding approach for social networks known as the modularity clustering approach. We show that a sub-exponential time algorithm for the small-set expansion problem leads to a sub-exponential time constant factor approximation for some hard input instances of the modularity clustering problem.

Recommendations

• Graph expansion and the unique games conjecture
• Subexponential algorithms for unique games and related problems
• Min-Max Graph Partitioning and Small Set Expansion
• Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis
• Approximation algorithms for hypergraph small set expansion and small set vertex expansion

Cites work

• Complexity of approximating bounded variants of optimization problems
• On the complexity of Newman's community finding approach for biological and social networks

Cited in

(2)

• Density-based modularity for evaluating community structure in bipartite networks
• Additive approximation algorithms for modularity maximization

This page was built for publication: On a connection between small set expansions and modularity clustering

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