# An Edge-Based Approach to Partitioning and Overlapping Graph Clustering with User-Specified Density
## 4 Proposed Partitioning and Overlapping Clustering Method
### Overlapping Clustering
1 The clustering process starts by assigning the average degree edge to a cluster ( 2 Set (Cls) \(\leftarrow\varnothing\)// Empty Clusters List
3 while not all edges are considereddo // Empty Cluster
4 cluster (\(c_{i}\)) \(\leftarrow\varnothing\)  Starting_Edge \(\leftarrow\)\(Avg_{deg}(\mathcal{G},e_{i})\) (Using Equation (1) and (2))
5 ifthe process is 'Partitioning Clustering' or 'Overlapping Clustering'then
6 Mark this edge as considered edge (\(e_{i}\))
7
8 cluster (\(c_{i}\)) \(\leftarrow\)\(Avg_{deg}(\mathcal{G},e_{i})\)// Clustering process is initiated with \(Avg_{deg}(\mathcal{G},e_{i})\) as a cluster \(c_{i}\) for Expansion
9 Determine (\(\delta_{r}\)) of cluster (\(c_{i}\)) whilethere exist edges(s) adjacent to the clusterdo
10 Find all adjacent edges(s) to cluster (\(c_{i}\))
11 Compute edges degrees of adjacent edges
12 Determine an average degree edge(\(e_{i}\)) of adjacent edges
13 foreach edge in adjacent edgesdo
14 Calculate: \(\delta_{r}(c_{i})\leftarrow\delta_{r}\) of cluster (\(c_{i}\))
15 temp_cluster \(\leftarrow\) cluster
16 Add: temp_cluster, edge (\(e_{i}\))
17
18\(\delta_{r}(\texttt{temp}_{c_{i}})\leftarrow\delta_{r}\) of temp_cluster // Relative Density updated
19 if\(\delta_{r}(\texttt{temp}_{c_{i}})=U(\delta_{r})\)then
20 cluster \(\leftarrow\)temp_cluster // Found Identical Density
21 ifthe process is ''Partitioning Clustering'then
22 Mark this edge as considered edge (\(e_{i}\))
23 Output :(\(c_{i}\)) is determined -> Add (\(c_{i}\)) to CIs: Navigate to next \(c_{i}\)
24
25 elseif\(\delta_{r}(\texttt{temp}_{c_{i}})<U(\delta_{r})\)then
26 cluster (\(c_{i}\)) \(\leftarrow\)temp_cluster // \(c_{i}\) is Expanded
27 ifthe process is 'Partitioning Clustering'then
28
29 Mark this edge as considered edge (\(e_{i}\))
30
31 cluster (\(c_{i}\)) \(\leftarrow\) temp_cluster // (\(c_{i}\) is Expanded) - Higher Density but closer to \(U(\delta_{r}\))
32 ifthe process is 'Partitioning Clustering'then
33 Mark this edge as considered edge (\(e_{i}\))
34
35
36
37
38
39
40
41
42
430
44
45
46
47
48
49
50
510
521
532
54
556
57
58
59
60
611
62
634
64
65
666
67
68
690
691
702
7103
721
734
745
756
767
778
792
80
810
82
83
846
85
86
87
888
893
947
95
961
972
984
996
973
985
997
1001
1025
1036
1047
1058
1069
1070
1087
1098
1109
110
1111
120
130
1411
1521
1631
1741
182
1920
1735
1936
10637
1074
1848
1949
1950
1088
1096
1097
1098
10999
2099
3000
3110
321

### Illustration of Partitioning Clustering Method on a Random Graph

A detailed step-by-step procedure using an arbitrary random graph is presented as an example in the next section after illustrating the methodology. Algorithm 1 describes the pseudocode for both partitioning and overlapping clustering based on edge degree. This is followed by an illustration as displayed in Figure 4. It is assumed that the edge degrees of all edges have been determined, with the parameter \(U(\delta_{r})\) set to 0.4. The clustering process initiates, as demonstrated in Figure 4a, with the identification and selection of an edge \((0,7)\), which is characterized by an average degree. This edge is then designated as the initial cluster. Subsequently, the cluster expands by adding the most suitable adjacent edges, identified based on their respective average degrees. This sequential expansion is marked as 'exp_i'. The process follows Algorithm 1. Initially, the first cluster denoted as \((c_{1})\) is formed and composed of nodes [0, 2, 3, 6, 7, 11, 13] (highlighted in yellow lines). It possesses a \((\delta_{r})\) value of 0.42, representing the closest approximation to the desired \(U(\delta_{r})\) value of 0.4. Subsequently, the same procedure is repeated to form a new cluster in the remaining edges, commencing with the edge \((5,10)\). In a manner similar to the determination of \((c_{1})\), the second cluster \((c_{2})\) is identified, consisting of 7 nodes [4, 5, 8, 9,10, 12, 14] (highlighted in red lines). This cluster exhibits a precise \(\delta_{r}\) density value of 0.4, meeting the specified criterion of 0.4.