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

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.