# An Edge-Based Approach to Partitioning and Overlapping Graph Clustering with User-Specified Density
## 4 Proposed Partitioning and Overlapping Clustering Method
### Overlapping Clustering
The selection of this particular graph serves the purpose of illustrating that, within such clustering scenarios, there exists the potential for certain edges or nodes to remain unclustered. In this specific example, node '\(1\)' is not incorporated into either \(c_{1}\) as including the edge \((0,10)\) or \((0,13)\) would result in a deviation of \(\delta_{r}(c_{1})\) from the desired value of 0.4. ### Illustration of Overlapping Clustering on a Random Graph

In the context of overlapping clustering, the clustering process adopts a strategy similar to that of partitioning clustering. The initial cluster in both clustering types consistently yields the same cluster (i.e., \(c_{1}\) represented by yellow lines) as shown in Figures 4a and 5a. In subsequent clusters, variations may arise, allowing for the inclusion of overlapping nodes. Following the methodology described in Algorithm 1, the second cluster \((c_{2}\) indicated by red lines) is identified with \((\delta_{r})\) closest to the desired value of \(U(\delta_{r})\) (i.e., 0.39). The noteworthy observation is that four nodes [2, 6, 7, 13] of \(c_{2}\) (i.e., overlapping nodes) also belong to \(c_{1}\). These overlapping nodes are visually represented by encircling them with double lines (orange and red circles), indicating their presence in two clusters \((c_{1}\) and \(c_{2})\). After completing the determination of \(c_{2}\), the process proceeds to identify a new cluster. In Figure 5c, the third cluster \((c_{3})\) (represented by green lines) emerges, initiated from an edge \((4,9)\), and expands similarly to previous examples. Cluster \((c_{3})\) exhibits a precise \((\delta_{r})\) density value of 0.4. During the formation of the third cluster, node '0' overlaps in two clusters, \(c_{1}\) and \(c_{3}\), respectively. It is worth emphasizing that, in overlapping clustering, the resulting clusters tend to be larger in size. Unlike partitioning clustering, there may be potential for a smaller number of unclustered nodes. Figure 4: (**a**) First partitioning cluster \(\delta_{r}(c_{1})\) of 0.42. (**b**) Second partitioning cluster \(\delta_{r}(c_{2})\) of 0.4. ## 5 Clustering Results

This section presents the results of the proposed graph clustering algorithms across a range of real-world networks. The selection of the networks for experimentation is guided by the objective of evaluating the algorithm across diverse network characteristics. The aim is to encompass a range of scenarios to enhance the generalizability of the algorithm's performance. The chosen networks represent a variety of characteristics, such as varying sizes (number of nodes and edges), structures, and complexities encountered in real-world scenarios. Table 1 provides an overview of these characteristics, including pertinent metrics such as the graph's maximum edge degree (\(max_{deg}(E)\)), minimum edge degree (\(min_{deg}(E)\)), average edge degree (\(Avg_{deg}(\mathcal{G},E)\)), and the standard deviation of the edge degree (\(\sigma(E)\)). ### Experimental Configuration

The user-specified density, denoted as \(U(\delta_{r})\), can be configured within the range of 0 and 1, as outlined in Section 3. Various densities have been applied to explore their impact on clustering outcomes. As a means of validating the proposed methodology, two distinct user-specified densities were selected for results demonstration: 0.4 and 0.6. These values exemplify scenarios that are marginally below and above the mid-value of 0.5 thresholds as representative values of diverse density levels. The rationale for selecting these specific values for illustration lies in the understanding of the relationship between multiple characteristics (as presented in Table 1) of the networks with the \(U(\delta_{r})\).