Finding a dense subgraph with sparse cut

Atsushi Miyauchi, Naonori Kakimura

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Citations (Scopus)


Community detection is one of the fundamental tasks in graph mining, which has many real-world applications in diverse domains. In this study, we propose an optimization model for finding a community that is densely connected internally but sparsely connected to the rest of the graph. The model extends the densest subgraph problem, in which we maximize the density while minimizing the average cut size. We first show that our proposed model can be solved efficiently. Then we design two polynomial-time exact algorithms based on linear programming and a maximum flow algorithm, respectively. Moreover, to deal with larger-sized graphs in practice, we present a scalable greedy algorithm that runs in almost linear time with theoretical performance guarantee of the output. In addition, as our model is closely related to a quality function called the modularity density, we show that our algorithms can also be used to find global community structure in a graph. With thorough experiments using well-known real-world graphs, we demonstrate that our algorithms are highly effective in finding a suitable community in a graph. For example, for web-Google, our algorithm finds a solution with more than 99.1% density and less than 3.1% cut size, compared with a solution obtained by a baseline algorithm for the densest subgraph problem.

Original languageEnglish
Title of host publicationCIKM 2018 - Proceedings of the 27th ACM International Conference on Information and Knowledge Management
EditorsNorman Paton, Selcuk Candan, Haixun Wang, James Allan, Rakesh Agrawal, Alexandros Labrinidis, Alfredo Cuzzocrea, Mohammed Zaki, Divesh Srivastava, Andrei Broder, Assaf Schuster
PublisherAssociation for Computing Machinery
Number of pages10
ISBN (Electronic)9781450360142
Publication statusPublished - 2018 Oct 17
Event27th ACM International Conference on Information and Knowledge Management, CIKM 2018 - Torino, Italy
Duration: 2018 Oct 222018 Oct 26

Publication series

NameInternational Conference on Information and Knowledge Management, Proceedings


Other27th ACM International Conference on Information and Knowledge Management, CIKM 2018


  • Approximation algorithms
  • Community detection
  • Densest subgraph
  • Exact algorithms
  • Graphs
  • Modularity density
  • Sparsest cut

ASJC Scopus subject areas

  • General Decision Sciences
  • General Business,Management and Accounting


Dive into the research topics of 'Finding a dense subgraph with sparse cut'. Together they form a unique fingerprint.

Cite this