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)

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

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)