A Scalable Multilevel Algorithm for Graph Clustering and Community Structure Detection

DOI10.1007/978-3-540-78808-9_11MaRDI QIDQ3520035zbMATH OpenOpenAlexFDO

Authors Hristo N. Djidjev

Publication date 19 August 2008

Published in Algorithms and Models for the Web-Graph (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Abstract: One of the most useful measures of cluster quality is the modularity of a partition, which measures the difference between the number of the edges joining vertices from the same cluster and the expected number of such edges in a random (unstructured) graph. In this paper we show that the problem of finding a partition maximizing the modularity of a given graph G can be reduced to a minimum weighted cut problem on a complete graph with the same vertices as G. We then show that the resulted minimum cut problem can be efficiently solved with existing software for graph partitioning and that our algorithm finds clusterings of a better quality and much faster than the existing clustering algorithms.

Recommendations

• Clustering With Multi-Layer Graphs: A Spectral Perspective
• A spectral clustering-based framework for detecting community structures in complex networks
• Assessing the quality of multilevel graph clustering

Cited in

(21)

• Multilevel local search algorithms for modularity clustering
• A partitioning-based divisive clustering technique for maximizing the modularity
• Significance-Driven Graph Clustering
• Axioms for graph clustering quality functions
• Using graph partitioning for efficient network modularity optimization
• Improving heuristics for network modularity maximization using an exact algorithm
• Ascent-descent variable neighborhood decomposition search for community detection by modularity maximization
• Multilevel local optimization of modularity
• On Finding Graph Clusterings with Maximum Modularity
• A DC Programming Approach for Finding Communities in Networks
• Clustering, community partition and disjoint spanning trees
• A dimensionality reduction framework for detection of multiscale structure in heterogeneous networks
• Hierarchies of predominantly connected communities
• Assessing the quality of multilevel graph clustering
• Community detection by modularity maximization using GRASP with path relinking
• Post-processing hierarchical community structures: quality improvements and multi-scale view
• Memetic graph clustering
• Complete hierarchical cut-clustering: a case study on expansion and modularity
• Social network community detection using agglomerative spectral clustering
• Using Mathematical Programming to Refine Heuristic Solutions for Network Clustering
• Graph clustering based on modularity variation estimations

This page was built for publication: A Scalable Multilevel Algorithm for Graph Clustering and Community Structure Detection

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