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.

Graph clustering has attracted many interests in recent years, with numerous applications ranging from the clustering of computer networks to the detection of social communities. It presents a challenging NP-class problem, and as a result, numerous algorithms have been developed, each tailored to specific objectives and quality metrics for evaluation. This research commences by categorizing existing graph clustering algorithms based on two distinct perspectives: parameter-free algorithms and user-defined or adjustable parametric algorithms. Quality metrics are further categorized into three distinct groups: internal connectivity, external connectivity, and a combination of both. If a task can be represented by a simple undirected and unweighted graph, from a management and deployment of resources perspective, having clusters of some kind of similar density is advantageous as it allows efficient management. This research introduces a partitioning graph clustering algorithm that allows users to specify the desired density of a cluster by means of ’relative density’. Clustering process involves the determination of all triangles (i.e., smallest cliques) and selecting a clique as an initial cluster. The expansion of a cluster is done by adding adjacent cliques while the required relative density is monitored. Existing metrics are found unsuitable for evaluating the proposed method; therefore, a suitable new metric, the Mean Relative Density Deviation Coefficient (MRDDC), is introduced.