An Edge-Based Approach to Partitioning and Overlapping Graph Clustering with User-Specified Density

Abstract

Graph clustering has received considerable attention recently, and its applications are numerous, ranging from the detection of social communities to the clustering of computer networks. It is classified as an NP-class problem, and several algorithms have been proposed with specific objectives. There also exist various quality metrics for evaluating them. Having clusters with the required density can be beneficial because it permits the effective deployment of resources. This study proposes an approach to partitioning and overlapping clustering of undirected unweighted graphs, allowing users to specify the required density of resultant clusters. This required density is achieved by means of ‘Relative Density’. The proposed algorithm adopts an edge-based approach, commencing with the determination of the edge degree for each edge. The main clustering process is then initiated by an edge with an average degree. A cluster is expanded by considering adjacent edges that can be included while monitoring the relative density of the cluster. Eight empirical networks with diverse characteristics are used to validate the proposed algorithm for both partitioning and overlapping clustering. Their results are assessed using an appropriate metric known as the mean relative density deviation coefficient (MRDDC). This is the first work that attempts to carry out partitioning and overlapping graph clustering, which allows user-specified density.

Keywords

• edge degree
• graph clustering
• mean relative density deviation coefficient (MRDDC)
• overlapping clustering
• partitioning clustering
• relative density