# An Edge-Based Approach to Partitioning and Overlapping Graph Clustering with User-Specified Density
## 4 Proposed Partitioning and Overlapping Clustering Method
### Overlapping Clustering  
Overlapping clustering, also referred to as'soft clustering', introduces the concept that a node can be assigned to either a single cluster or multiple clusters. In this framework, the processes of clustering initiation and cluster expansion steps are similar to those of partitioning clustering. However, a distinctive feature of overlapping clustering is the allowance for all nodes to belong to one or more clusters. This implies that the overlapping region must exhibit shared edges with nodes belonging to more than one cluster. Consequently, the common edges among nodes facilitate the inclusion of a single node in multiple clusters. It is important to emphasize that the initial edge for each (or a new) cluster is considered only once to avoid repetition of the same process. 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 in this study. In Algorithm 1, careful consideration of edges is pivotal to ensure a unique starting edge for each cluster. The algorithm meticulously marks the starting edge as considered, preventing its further use and averting potential indefinite states. Once an edge is considered, it is removed from the set of edges (\(E\)), maintaining the integrity of the clustering process. Furthermore, during the expansion phase, adherence to partitioning clustering principles prevents the repetition of edges and nodes within or outside a cluster. Any added edge is marked as considered, updating the edge set (\(E\)). In scenarios of overlapping clustering, the flexibility to reconsider edges for expansion is maintained. The clustering process concludes when the edges list becomes empty, offering a nuanced approach that balances the rigidity of partitioning clustering with the adaptability needed for overlapping clustering scenarios. As both types of clustering in this study assume that the network is static, an assumption is made that the computation time is not a constraint. This assumption may not be possible if the network is dynamic, for example, communication among moving vehicles in a mobile ad hoc network. The worst case of clustering is when the network is fully connected as there exists an edge between every pair of nodes in the network (i.e., there are \(\frac{n(n-1)}{2}\) edges, where \(n\) is the number of nodes) and it has a density of \(1\) (i.e., the entire graph is a large cluster). Clustering of any kind in a fully connected network is meaningless as the network is just one big cluster. However, it provides a quick computation analysis for this work. The computation time is then dominated by the expansion of clusters. In this worst-case scenario, the network comprises \(E\) edges, and a determination of a cluster has a time complexity of \(O(E)\). Therefore, to consider every node in the network, the time complexity is \(O(E^{2})\). While this magnitude seems quite high, it seldom happens in practice for the reasons stated above. The application of a clustering approach in this work to most real-world networks demands much less computation time. ``` Input :Graph Type -> Undirected, Unweighted and Connected Graph Output :A set of Partitioning / Overlapping Clusters (Cls) -> {\(c_{1},c_{2},c_{3},\ldots,c_{k}\)}, either equals or closely approximates to \(U(\delta_{r})\).