A hierarchical overlapping community detection method based on closed trail distance and maximal cliques

Information Sciences 662 (2024) 120271 Available online 5 February 2024 0020-0255/© 2024 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/). Contents lists available at ScienceDirect Information Sciences journal homepage: www.elsevier.com/locate/ins A hierarchical overlapping community detection method based on closed trail distance and maximal cliques Pavla Dráždilová∗, Petr Prokop, Jan Platoš, Václav Snášel Department of Computer Science, VSB -Technical University of Ostrava, 708 00 Ostrava-Poruba, Czech Republic A R T I C L E I N F O A B S T R A C T Dataset link: http:// www -personal .umich .edu /%7Emejn /netdata/ Dataset link: https://anonymous .4open . science /r /graph _hierarchical _agglomerative _ clustering -C946 /README .md Keywords: Overlapping community detection Clique percolation Closed trail distance And hierarchical agglomerative clustering An important feature of real networks is their hierarchy and the existence of overlapping communities. Hierarchical agglomerative clustering is one way to determine the hierarchy of a network. To ensure the existence of overlapping communities, it is appropriate to choose the base elements for clustering – edges, cliques, etc. These base elements can then have common vertices and naturally provide the possibility of overlap. The proposed community detection method uses hierarchical agglomerative clustering on the 2-edge-connected component of the graph. Communities are constructed from maximal cliques as base elements. Novel dissimilarities for hierarchical agglomerative clustering were introduced for the merging of cliques. The dissimilarities use the size of the overlapped cliques and closed trail distance to express dissimilarity between communities in networks. The single linkage approach contains and extends the results of 𝑘-CPM. The proposed algorithm utilizing deterministic dissimilarity achieves comparable or superior outcomes compared to standard algorithms used for hierarchical or overlapping community detection. 1. Introduction Using graph representation and network analysis tools can be beneficial for studying relationships between objects. A general description of community is a set of different objects connected more frequently among themselves in comparison to the rest of the network. In case of the possible belonging of objects to multiple communities, we are focusing here on overlapping communities [1]. Yang and Leskovec [2,3] noticed that the community overlaps are dense. In some real-world datasets, while most clustering algorithms cannot handle such dense overlapping structures, one vertex may belong to tens of communities simultaneously [4]. The representative method of overlapping clustering is the clique percolation method (CPM or 𝑘-CPM) by Palla et al. [5,6]. The detection of communities is realized via finding maximal cliques, construction of a clique graph with maximal cliques as vertices, and weighted edges representing the size of cliques’ overlap that are bigger than or equal to a specified 𝑘 −1. Communities are connected components in the clique graph where detected communities may not form a network cover. Some algorithms for overlapping community detection are based on clustering of more complex base elements than vertices – edges [7], cliques [8], weak-cliques [9], etc. The second point of view on algorithms for community detection can be focused on the hierarchy of communities [1]: “Communities are nested within each other as many times as there are hierarchical levels.” Algorithms for hierarchical community detection * Corresponding author. E-mail addresses: [email protected] (P. Dráždilová), [email protected] (P. Prokop), [email protected] (J. Platoš), [email protected] (V. Snášel). https://doi.org/10.1016/j.ins.2024.120271 Received 31 July 2023; Received in revised form 30 January 2024; Accepted 30 January 2024 Information Sciences 662 (2024) 120271 2 P. Dráždilová, P. Prokop, J. Platoš et al. Table 1 Notation used in the paper. Symbol Description 𝑉(𝐺)Set of vertices of graph 𝐺 𝐸(𝐺)Set of edges of graph 𝐺 𝑛,𝑚Number of vertices and edges of graph 𝑑𝑒𝑔(𝑢)Degree of vertex 𝑢 ⟨𝑑𝑒𝑔⟩Average degree of vertices 𝐻𝐴𝐶 Hierarchical agglomerative clustering 𝐺𝐻𝐴𝐶 Graph hierarchical agglomerative clustering 𝑆𝐿,𝐶𝐿,𝐴𝐿 Single, complete and average linkage approach 𝐴,𝐴𝑖𝑗 Adjacency matrix; one element from adjacency matrix 𝑄,𝑄𝑘Clique and clique with 𝑘vertices 𝑆𝑃(𝑥𝑖,𝑥 𝑗)The shortest path between vertices 𝑥𝑖, 𝑥𝑗 𝐶𝑇(𝑥𝑖,𝑥 𝑗),𝐶𝑇(𝑢, 𝑣, 𝑤, 𝑢)The shortest closed trail containing vertices 𝑥𝑖, 𝑥𝑗; closed trail from 𝑢 via 𝑣and 𝑤to 𝑢 𝐶𝑖𝑖-th community |𝐶𝑖|Size of 𝑖-th community 𝑑𝑆𝑃 ,𝑑𝐶𝑇 Shortest path and closed trail distance 𝑑𝑆𝐿 𝐺𝐻𝐴𝐶 ,𝑑𝐶𝐿 𝐺𝐻𝐴𝐶 ,𝑑𝐴𝐿 𝐺𝐻𝐴𝐶 Graph hierarchical agglomerative clustering dissimilarity with single, complete, and average linkage approach 𝑁(𝑢),𝑁+(𝑢)𝑁(𝑢) ={𝑣 ∈𝑉(𝐺); 𝑑𝑆𝑃 (𝑢, 𝑣) =1}, 𝑁+(𝑢) ={𝑣 ∈𝑉(𝐺); 𝑑𝑆𝑃 (𝑢, 𝑣) ≤1} 𝜆Level of cut in dendrogram are often based on hierarchical agglomerative clustering (HAC). Ahn et al. [7]used a single linkage approach with Jaccard similarity, Shen et al. [10] agglomerate communities with the maximum similarity, and Blondel et al. [11]used the hierarchical approach based on modularity optimization. Another agglomerative method uses node influence and the similarity of nodes to detect non-overlapping communities [12]. Alternatively, divisive clustering is used in [13]in the form of a recursive partitioning algorithm, starting with a single community and separating the nodes into two communities by spectral clustering repeatedly. The main motivation for developing a new community detection method was to combine the search for overlapped communities and the creation of their hierarchical structure. HAC is a commonly used procedure for detecting overlapping communities when the cliques are used as bases, e.g. EAGLE [10]. In this current work, we are introducing a novel dissimilarity for the HAC based on the structural closeness of cliques and their neighborhood in a graph. We designed new dissimilarities between communities that are deterministic and we used the closed trail distance between graph nodes and the size of communities that overlap. Closed trail distance (𝐶𝑇-distance) between vertices 𝑢, 𝑣in the unweighted, undirected, connected graph without bridges (2-edge-connected) is defined in the article [14]as the length of the shortest closed trail that contains vertices 𝑢, 𝑣(Table 1). The extension of 𝐶𝑇-distance for undirected and weighted graphs was also listed in article [14]. The processing steps in the proposed community detection method are indicated in the graphical abstract. The 𝐶𝑇-distance matrix among pairs of vertices is calculated for the use in dissimilarities in the proposed algorithm. All maximal cliques are detected in the source network and are used as bases in the HAC. The proposed dissimilarities serve for the agglomeration of bases and the creation of a hierarchy (dendrogram). The value of modularity for each possible level is monitored. The best value of modularity indicates the level of cut in the hierarchy. This result represents the network cover. We would like to highlight the main contribution of this paper as follows: •A hierarchical overlapping community detection method was proposed. The proposed method uses the HAC and maximal cliques as base elements for clustering. •The relation between the well-known 𝑘-CPM and the proposed method was discussed. Due to the extended hierarchy, the proposed method allows the detection of better communities than the 𝑘-CPM. •The proposed method is not focused on efficient computation for large graphs. Instead, it uses maximal cliques as building blocks. The dissimilarities are based on 𝐶𝑇-distance and the size of cliques in the overlap which allows the study of the hierarchical structure of communities in the network. •Resulting overlapping community structure depends on the sequential (greedy) merging of all maximal cliques and the alreadyfound communities. This article is organized as follows. Section 2introduces the related work to community detection from hierarchical and agglomerative perspectives. Section 3is focused on the relation between the CPM and HAC used for community detection with a single linkage approach. The section describes our motivation behind the proposed method. Section 4presents the algorithm for community Information Sciences 662 (2024) 120271 3 P. Dráždilová, P. Prokop, J. Platoš et al. detection and dissimilarities between clusters of vertices based on the 𝐶𝑇-distance between vertices that are not in the intersection of clusters and takes into account the size of this intersection. The applied idea of clustering of more complex base elements than vertices – maximal cliques – enables the overlap between communities. Section 5contains the experiments demonstrating the selection of cuts in the dendrogram where the hierarchy of communities for the proposed method is shown in a real-world network. The empirical evaluation of the method is also included and the results are compared with the selected well-known methods. The advantages of the proposed methods and future work are discussed in the conclusion in section 6. 2. Related work There are currently many methods that perform hierarchical community detection. Some methods are algorithmically hierarchical [10,11]and create a hierarchy as a result of the applied algorithm. Another class of methods involves fitting a hierarchical model to the analyzed network. Schaub et al. [15] introduced a definition of hierarchy based on the concept of stochastic externally equitable partitions and their relation to probabilistic models, such as the stochastic block model. They focused on an agglomerative procedure that relies on accurately detecting the finest level in the hierarchy. The result of HAC is represented by the proximity dendrogram [16] which is a tree-like structure where each node represents a cluster or a data point, and the branches show the merging of clusters during the clustering process. The natural overlap can be constructed by partitioning links [7]instead of nodes. A node in the original graph is called overlapping if the links connected to it are put in more than one cluster. The authors use HAC with the SL approach and the similarity between links to build a dendrogram where each leaf is a link from the original network and the branches represent clusters of the links. A different approach to community detection is applied in [17,5]. The authors developed the 𝑘-clique percolation method (𝑘CPM) for community detection. The community is created from 𝑘-cliques (𝑄𝑘) that are reached only from the 𝑘-cliques of the same community through a series of adjacent 𝑘-cliques. Two 𝑘-cliques are adjacent if they share 𝑘 −1vertices. The extension of the CPM to the weighted network was proposed in [8]as CPMw. The authors introduced a module identification technique for weighted networks based on 𝑘-cliques having a subgraph intensity higher than a certain threshold and allowing shared nodes (overlaps) between modules. A Sequential Clique Percolation (SCP) algorithm [18]was proposed for fast clique percolation detecting 𝑘-clique communities in a network by sequentially inserting its edges and keeping track of the emerging community structure. This algorithm has specifically been designed for (dense) weighted networks, where weight-based thresholding of either the links or the cliques formed by them is necessary for obtaining meaningful information on the structure. Reid et al. [19] analyzed SCP and stated: “However, these improved methods often perform poorly on networks with the kind of pervasively overlapping community structure we see in many real worlds social networks – an area of increasing interest in the applied study of community structure – and particularly poorly when performing percolation with high values of 𝑘.” The authors in [20] proposed the clique-based Louvain algorithm that classifies the non-classified node obtained after finding cliques in one of the communities by applying the Louvain algorithm. One of the first algorithms for the detection of the overlapping and hierarchical community structure in complex networks is described in [21]. The method is based on the local optimization of a fitness function (ratio of the internal degree to the total degree of a module). The method corresponds to a sort of greedy optimization of the fitness function. It creates natural communities around vertices and the result is vertices’ cover, i.e., it depends on the resolution parameter for scale. Algorithm EAGLE [10] detects overlapping and hierarchical community structures in networks with a hierarchical agglomerative method. The similarity between communities is based on modularity and the maximal cliques are its base elements. This approach confirms that HAC is applicable for the hierarchy detection among communities, and maximal cliques (as base elements) ensure the overlap of communities. Maximal cliques are used in [22]. This paper proposes a Maximal Clique-based Multiobjective Evolutionary Algorithm (MCMOEA) for overlapping community detection. The representation scheme is based on the maximal clique and the algorithm can provide hierarchical partitions of the given network. A DOCNA [23]is an algorithm for detecting overlapping communities in networks based on maximal cliques where an improved version of the Bron-Kerbosch Algorithm is adopted. The request for maximal cliques is quite restrictive. Therefore, in [9]they used weak cliques as the base elements. The authors proposed a weak-CPM for overlapping community detection in a large-scale network. The greedy coupled-seeds expansion method [24]for the overlapping community detection used a fitness function that is based on the size of a common neighbor of two vertices – similar to a weak clique percolation. The authors in [25] propose an algorithm MOKP that uses 𝑘-plexes to generate community seeds from the whole network and assigns the remaining nodes by modularity optimization. This algorithm does not detect overlapping communities. To identify the overlapping community structure, the authors in [26] constructed a maximal clique network from the original network, and proved that the optimization of their metric on the original network is equivalent to the optimization of Newman’s modularity on the maximal clique network. A useful approach for overlapping community detection is based on Nonnegative Matrix Factorization (NMF). Yang and Leskovec [27]used the NMF approach to find the overlapping communities in large-scale networks, Wang et al. [28] proposed the Modularized Nonnegative Matrix Factorization (MNMF) model to incorporate the community structure into network embedding, and Ye et al. [29] proposed a model called Deep Autoencoder-like NMF (DANMF) for community detection, inspired by the unique feature representation learning capability of the deep autoencoder. Information Sciences 662 (2024) 120271 4 P. Dráždilová, P. Prokop, J. Platoš et al. The overview of community detection methods with hierarchical agglomerative clustering or overlapping community detection can be found in [21,30,31,1,32]. The survey of community detection using nonnegative matrix factorization (NMF) is in [33]. The comprehensive survey of community detection focused on deep learning is mentioned in [34]. The evaluation of the appropriateness of the detected community structure is a very important part of community analysis. Metrics related to all the classes of community structures (disjoint, overlapping, local, hierarchical, etc.) are presented in a survey [35]of the state-of-the-art metrics used for the detection and evaluation of community structure in networks. The article [36]focuses on the quality of community structure and contains a broad overview and classification of methods for the evaluation of detected communities. The result of HAC is a dendrogram that represents the hierarchical structure of communities. The determination of the dendrogram’s cut level is a crucial aspect that plays a pivotal role in uncovering an optimal community structure. To assess the efficacy of the community structure derived through HAC, the modularity metric serves as a valuable tool for evaluation. One of the modularities for overlapped communities can be found in [10]. This work introduces a belonging coefficient. The belonging coefficient of a node 𝑖for a given community is redefined as the number of communities 𝑂𝑖to which it belongs. 3. Relation between HAC and clique percolation We would like to discuss a generalization of CPM to HAC. This generalization leads us to the theoretical grounding for the proposed dissimilarities. The idea about the clique’s hierarchy detected by hierarchical clustering was stated in [37]. The authors used a co-clique matrix as an input for hierarchical clustering. This co-clique matrix corresponds to the adjacency matrix of the weighted graph of overlapped maximal cliques. As far as complexity is concerned, the CPM was designed for selected 𝑘, very often 𝑘 =3[17]. Derenyi et al. in [17]and Yuan et al. in [38]use for 𝑘-clique graph a different terminology and they named it as, “𝑘-clique adjacency graph.” The standard 𝑘-CPM [17] can be described via a 𝑘-clique graph as follows: 1. Detect 𝑘-cliques in the source network and create a 𝑘-clique graph, where vertices are 𝑘-cliques and the edges exist between 𝑘-cliques which have (𝑘 −1)vertices in the overlap in the source network. 2. Find the connected components in the clique graph. These connected components in the clique graph correspond to communities in the source network. An effective algorithm based on maximal cliques in 𝑘-CPM [19]builds a minimal spanning forest over the maximal cliques, using a simple data structure to reduce unnecessary clique intersection tests. The Yuan et al. aim in [38]to find the densest clique percolation community which contains a given set of query nodes. They use a maximal clique adjacency graph and a maximal clique adjacency spanning tree with the maximum total weight of edges where the weight of the edge in the maximal clique adjacency graph is equal to the size of overlap between maximal cliques in the source graph. Generalized CPM inspired by the article [38] introduces a connection between CPM and graph hierarchical clustering with a single linkage approach: 1. Detect maximal cliques in the source network and create a weighted maximal clique graph. The weights of edges in the maximal clique graph correspond to the size of the overlap between maximal cliques in the source network. 2. Use the HAC with the SL approach on the maximal cliques for the creation of a dendrogram. The weight of an edge is the similarity between vertices in the maximal clique graph. 3. For a specified 𝑘, obtain a level of cut in the dendrogram that represents the same result as in the standard 𝑘-CPM. Clusters from the dendrogram are the connected components in the maximal clique graph with the edge’s weight bigger or equal to 𝑘 −1. These represent overlapped communities in the source network. The minimal weight in the maximal clique graph equals 1for 𝑘 =2and in this situation, all vertices of the connected source graph are in one community. 3.1. From 𝑘-CPM to a novel dissimilarity for GHAC The formation of communities in the CPM can be naturally described with the SL approach (minimal distance or maximal similarity between two elements which are in different clusters) in a hierarchical agglomerative clustering on the graph (GHAC). The size of the overlap of the maximal cliques determines the degree of similarity and thus allows the hierarchization of the obtained communities with an overlap greater or equal to two. The other condition is merging the adjacent cliques, therefore the 𝐶𝑇-distance between a pair of nodes (the length of the shortest closed trail containing a pair of nodes) is the smallest. Further extension of this hierarchy can be achieved by introducing a new dissimilarity based on a 𝐶𝑇-distance. At first, we define the dissimilarity between the subgraphs 𝐶𝑖and 𝐶𝑗based on the 𝐶𝑇-distance and the SL approach in the GHAC: 𝑑𝑆𝐿 𝐶𝑇 (𝐶𝑖,𝐶 𝑗)=𝑚𝑖𝑛(𝑣𝑖∈𝐶𝑖⧵𝐶𝑗),(𝑣𝑗∈𝐶𝑗⧵𝐶𝑖)𝑑𝐶𝑇 (𝑣𝑖,𝑣 𝑗). The next theorem shows the connection between the proposed dissimilarity and the percolation of the two adjacent cliques in the CPM. Information Sciences 662 (2024) 120271 5 P. Dráždilová, P. Prokop, J. Platoš et al. Fig. 1. Dissimilarity SL GHAC between communities depends directly proportional to 𝐶𝑇-distance of vertices out of overlap (in different communities) and is inversely proportional to the size of overlap. Theorem 1. The dissimilarity 𝑑𝑆𝐿 𝐶𝑇 (𝑄, 𝑄′)between the two adjacent 𝑘-cliques in graph 𝐺with 𝑘 ≥3based on the CT-distance and the SL approach equal to 3or 4. Proof. Let 𝑄, 𝑄′be two adjacent 𝑘-cliques and 𝑁(𝑢) ={𝑣 ∈𝑉(𝐺); 𝑑𝑆𝑃 (𝑢, 𝑣) =1}is a neighborhood of a vertex 𝑢. Two 𝑘-cliques are adjacent if they share 𝑘 −1vertices [5]. The amalgamation (gluing) of the two cliques that share 𝑘 −1vertices for 𝑘 ≥3create a 4 −𝐶𝑇 component [39] because for all 𝑢 ∈𝑄and for all 𝑢′∈𝑄′, the following situations may occur: •𝑢, 𝑢′∈𝑄 ∩𝑄′and (𝑢 =𝑢′) ⇒𝑑𝐶𝑇 (𝑢, 𝑢′) =0, •𝑢, 𝑢′∈𝑄 ∩𝑄′and 𝑢 ≠𝑢′⇒∃𝑣 ∈𝑄 ∩𝑄′such that 𝑣 ∈𝑁(𝑢)and 𝑣 ∈𝑁(𝑢′)⇒|𝐶𝑇(𝑢, 𝑣, 𝑢′, 𝑢)| =3 =𝑑𝐶𝑇 (𝑢, 𝑢′), •𝑢, 𝑢′∉𝑄 ∩𝑄′and 𝑢′∉𝑁(𝑢)⇒∃𝑣, 𝑤 ∈𝑄 ∩𝑄′such that 𝑣, 𝑤 ∈𝑁(𝑢)and 𝑣, 𝑤 ∈𝑁(𝑢′)⇒|𝐶𝑇(𝑢, 𝑣, 𝑢′, 𝑤, 𝑢)| =4 =𝑑𝐶𝑇 (𝑢, 𝑢′), •𝑢, 𝑢′∉𝑄 ∩𝑄′and 𝑢′∈𝑁(𝑢)⇒∃𝑣 ∈𝑄 ∩𝑄′such that 𝑣 ∈𝑁(𝑢)and 𝑣 ∈𝑁(𝑢′)⇒|𝐶𝑇(𝑢, 𝑣, 𝑢′, 𝑢)| =3 =𝑑𝐶𝑇 (𝑢, 𝑢′).□ The above description of dissimilarity (𝑑𝑆𝐿 𝐶𝑇 ) does not distinguish between the smaller and the bigger overlap of cliques. The modification of the dissimilarity that incorporates the size of overlap better describes the relation between the overlapping cliques and the formation of hierarchical structure detected communities. The size of overlap between communities 𝐶𝑖and 𝐶𝑗is defined as the number of vertices in the maximal shared clique of communities 𝐶𝑖, 𝐶𝑗. It is a different definition than that in [6], where the size of overlap is defined as the number of shared nodes in 𝐶𝑖and 𝐶𝑗. The newly proposed dissimilarity 𝑑𝑆𝐿 𝐺𝐻𝐴𝐶 (𝐶𝑖, 𝐶𝑗)between communities 𝐶𝑖and 𝐶𝑗is directly proportional to the node distance (𝐶𝑇-distance) outside of the overlap of 𝐶𝑖and 𝐶𝑗, inversely proportional to overlap size, uses the SL approach, and then captures the hierarchy of the detected communities as well as the hierarchy of the percolated cliques: 𝑑𝑆𝐿 𝐺𝐻𝐴𝐶 (𝐶𝑖,𝐶 𝑗)= 𝑚𝑖𝑛(𝑣𝑖∈𝐶𝑖⧵𝐶𝑗),(𝑣𝑗∈𝐶𝑗⧵𝐶𝑖)𝑑𝐶𝑇 (𝑣𝑖,𝑣 𝑗) 1+𝑎𝑟𝑔𝑚𝑎𝑥𝑄∈𝐶𝑖∩𝐶𝑗|𝑄|. The SL approach for GHAC and the incorporation of the size of the overlap on base elements (cliques) ensures that the cliques with the biggest overlap are amalgamated at first – they have the smallest dissimilarity. Fig. 1shows the different situations for two communities (cliques 𝐶𝑖, 𝐶𝑗) that differ in the size of the overlap. The maximal overlapping cliques in Fig. 1a are edges (𝑣𝑖, 𝑤), (𝑣𝑗, 𝑤)with a common vertex 𝑤. Fig. 1b represents the situation out of the clique percolation but with two 4-cliques with an overlap. Figs. 1c and 1d correspond to the 3-clique percolation (the size of overlap equal to 2) and the 4-clique percolation (the size of overlap equal to 3). Fig. 1e corresponds to the 6-cliques amalgamation with a size of the overlap equal to 3and the denser neighborhood (𝑑𝐶𝑇 (𝑣𝑖, 𝑣𝑗) =3). The 𝑘-CPM uses only the information about the size of the overlap of the two adjacent 𝑘-cliques. This size is equal to (𝑘 −1). The 𝐶𝑇-distance between vertices in the adjacent clique (that are not in overlap) is mostly equal to 4. These two aspects of the suggested dissimilarity, yield identical outcomes to the clique percolation. However, in denser network regions (refer to Fig. 1e), the 𝐶𝑇-distance can be reduced to 3(Theorem 1). In such cases, the proposed dissimilarity employing the SL approach captures additional information regarding the network’s density at the intersection of the two cliques. This dissimilarity shows to be more accurate in extremely dense parts of the network than the CPM does. The HAC with the proposed dissimilarity finds a hierarchical structure over the communities detected by CPM with an arbitrary 𝑘. The usage of 𝐶𝑇-distance in the proposed dissimilarity reflects the relation, not only among cliques, but also for the not-so-dense communities. 4. Hierarchical clustering based on 𝑪𝑻-distance In this article, we propose new 𝐶𝑇-distance based dissimilarities for hierarchical agglomerative clustering on graphs. We have formalized the basic idea for our method as an extension of generalized CPM from the previous section. The idea of the use of novel dissimilarity 𝑑𝑆𝐿 𝐺𝐻𝐴𝐶 with GHAC (therefore SL GHAC) and the specification of the level of cut in the dendrogram can be summarized as a sequence of processing steps: 1. Detect the maximal cliques as base elements in the source network. 2. Calculate the 𝐶𝑇-distance among vertices in the source network. 3. Use the SL GHAC for cluster construction. Information Sciences 662 (2024) 120271 6 P. Dráždilová, P. Prokop, J. Platoš et al. 4. The lower part of a resulting dendrogram mostly corresponds to the dendrogram in generalized CPM. Then, the hierarchy continues and connects the communities with the size of the overlap (the size of the biggest common clique) equal to one. 5. Use evaluation for quality of community detection to determine the best level of cut in the dendrogram or specify the number of communities from the dendrogram. The SL GHAC at the cut level with a value equal to 4∕𝑘corresponds to the result of the 𝑘-CPM. It is a consequent of the Theorem 1 where 𝑑𝑆𝐿 𝐶𝑇 (𝑄, 𝑄′)for adjacent cliques is mostly equal to four and, in an extremely dense part of the network, can be equal to three. The situation with 𝑑𝑆𝐿 𝐶𝑇 (𝑄, 𝑄′) =3is incorporated into the level of the cut with the value 𝑑𝑆𝐿 𝐺𝐻𝐴𝐶 (𝑄, 𝑄′) =4∕(1 +(𝑘 −1)), where (𝑘 −1)is the size of the overlap between the two cliques. The SL GHAC framework will be further extended in the following subsection. The introduction of other dissimilarities will modify the idea of the percolation of adjacent cliques when the single linkage approach is used. 4.1. Additional dissimilarities for the GHAC based on the 𝐶𝑇-distance The standard linkage methods of the HAC [40]have different properties. The SL HAC tends to produce unbalanced and straggly clusters (chaining), especially in large data sets. It does not take into account the cluster structure. The CL HAC tends to find compact clusters with equal diameters (maximum distance between objects). It does not take into account the cluster structure. The AL HAC tends to join clusters with small variances and takes into account the cluster structure. The evaluation of the other HAC methods [41]shows that more successful methods than the SL are CL, AL, or Ward’s methods. Our experiments empower the GHAC with multiple dissimilarities based on the 𝐶𝑇-distance, and the size of overlap. Apart from the SL, we have defined the approaches based on the CL and the AL as: 𝑑𝐶𝐿 𝐺𝐻𝐴𝐶 (𝐶𝑖,𝐶 𝑗)= 𝑚𝑎𝑥(𝑣𝑖∈𝐶𝑖⧵𝐶𝑗),(𝑣𝑗∈𝐶𝑗⧵𝐶𝑖)𝑑𝐶𝑇 (𝑣𝑖,𝑣 𝑗) 1+𝑎𝑟𝑔𝑚𝑎𝑥𝑄∈𝐶𝑖∩𝐶𝑗|𝑄|, and 𝑑𝐴𝐿 𝐺𝐻𝐴𝐶 (𝐶𝑖,𝐶 𝑗)= ∑(𝑣𝑖∈𝐶𝑖⧵𝐶𝑗),(𝑣𝑗∈𝐶𝑗⧵𝐶𝑖)𝑑𝐶𝑇 (𝑣𝑖,𝑣 𝑗) |(𝐶𝑖∪𝐶𝑗)⧵(𝐶𝑗∩𝐶𝑖)|(1 + 𝑎𝑟𝑔𝑚𝑎𝑥𝑄∈𝐶𝑖∩𝐶𝑗|𝑄|). For the current work, we have denoted the use of the GHAC method with dissimilarity 𝑑𝑆𝐿 𝐺𝐻𝐴𝐶 as SL GHAC. The other markings of AL GHAC and CL GHAC are applied as well. 4.2. Community detection computation procedure The proposed community detection methods as GHAC framework are summarized in computation steps in Algorithm 1. The proposed methods differ in the used dissimilarities. Algorithm 1: Proposed community detection method based on the GHAC and dissimilarity leveraging 𝐶𝑇-distance. Input :The biggest connected component of a network without bridges Output :Network cover Step 1: Calculate 𝐶𝑇-distance matrix among vertices in a input graph. Step 2: Find maximal cliques (Bron-Kerbosch alg.). Step 3: Graph hierarchical agglomerative clustering: Step 3.1: Agglomerate communities according to proposed dissimilarity with maximal cliques as base elements. Step 3.2: Map merged clusters of base elements to source graph vertices. Step 3.3: Evaluate the structural quality of network cover by modularity. Step 3.4: Repeat the algorithm from Step 3.1 until all the clusters are merged. Step 4: Choose the best level of a cut of a dendrogram. Suurballe’s algorithm [42]is used to calculate the 𝐶𝑇-distances among vertices. The 𝐶𝑇-distances are one part of used dissimilarities in the GHAC. Another part of dissimilarities takes the size of the overlap into account. The Maximal cliques are used as bases in the GHAC and the merged clusters of maximal cliques are mapped to vertices with a few post-processing steps. Firstly, the non-agglomerated bases of size 2 (edges) are not considered in the final communities and they are filtered out. The vertices, that are not part of any community, are added as separate communities. These post-processing steps allow us to compare the network cover of the different community detection methods with respect to the need for some modularity measure to contain all vertices. The modularities of the overlapping network covers are used as quality evaluation criteria for the selection of the level of the cut in a dendrogram. Information Sciences 662 (2024) 120271 7 P. Dráždilová, P. Prokop, J. Platoš et al. Table 2 Characteristics of the giant connected component of network used in experiments. Number of nodes (𝑛), number of edges (𝑚), density (𝑑𝑒𝑛𝑠), clustering coefficient (𝐶𝐶), average degree (⟨𝑑𝑒𝑔⟩), maximal degree (𝑑𝑒𝑔𝑚𝑎𝑥), shortest path distance diameter (𝑑𝑖𝑎𝑚𝑆𝑃 ), closed trail distance diameter (𝑑𝑖𝑎𝑚𝐶𝑇 ), and number of maximal cliques (#𝑐𝑙𝑖𝑞𝑢𝑒𝑠). Network 𝑛𝑚 𝑑𝑒𝑛𝑠𝐶𝐶⟨𝑑𝑒𝑔⟩𝑑𝑒𝑔𝑚𝑎𝑥 𝑑𝑖𝑎𝑚𝑆𝑃 𝑑𝑖𝑎𝑚𝐶𝑇 #𝑐𝑙𝑖𝑞𝑢𝑒𝑠 Zachary’s karate club 33 77 0.15 0.26 4.7 17 5 11 35 American college football 115 613 0.09 0.41 10.7 12 4 8 281 Coauthorships in network science 340 865 0.015 0.45 5.1 32 16 39 169 High-energy theory collaborations 4557 12399 0.001 0.30 5.4 50 16 41 3976 The implementation of the GHAC method is written in Python 3.11. The agglomeration method is re-implemented for the proposed dissimilarities calculation. The commonly used libraries are used for the graph-related operations.1 5. Experiments The suggested community detection methods are compared to other known methods over the selection of real-world networks. According to the 𝐶𝑇-distance definition requirement, only the giant connected component of each network after bridge removal was used in the experiments. A summary of the pre-processed networks is given in Table 2. The proposed community detection methods based on the SL (CL, AL) GHAC offer several different levels of dendrogram cut to provide community detection results. There is a need to evaluate the quality of the detected communities in agglomerative structures to select the best cut in the dendrogram. Modularity can be used for that, which explains the reason for the EAGLE algorithm to employ it [10]. To ensure the corresponding modularity evaluation of the detected components for various community detection methods and the modularity measures used in this paper, every node has to be assigned to at least one community; hence, a node not assigned to any community is treated as a community of a single node. 5.1. Quality evaluation of overlapping communities Three different definitions of modularity [10,43,44]for overlapping communities are applied in the agglomerative process of the GHAC method to determine the best network cover when using the proposed community detection method. The extensions of modularity to overlapping communities are based on the traditional Newman approach in [45]. Shen’s modularity extension [10]for overlapping communities considers vertex membership in multiple communities. It is directly equivalent to Newman’s modularity when vertices belong to just one community. This is defined as follows: 𝑀𝑒=1 2𝑚 𝑐 ∑ 𝑘=1 ∑ 𝑖,𝑗∈𝐶𝑘 1 𝑂𝑖𝑂𝑗[𝐴𝑖𝑗 −𝑑𝑒𝑔(𝑖)𝑑𝑒𝑔(𝑗) 2𝑚], where 𝑂𝑣is the number of communities to which vertex 𝑣belongs, 𝑐is the number of communities. The other measure for quantifying cluster structures in graphs was introduced by Lazar in [43]. It is based on two assumptions: one, the edges of a node should be primarily inside the community, and two, the clusters (communities) should be dense. The measure is defined as: 𝑀𝑜𝑣 =1 𝑐 𝑐 ∑ 𝑘=1 ⎛⎜⎜⎝∑ 𝑖∈𝐶𝑘 ∑𝑗∈𝐶𝑘,𝑖≠𝑗𝑎𝑖𝑗 −∑𝑗∉𝐶𝑘𝑎𝑖𝑗 𝑑𝑒𝑔(𝑖)𝑂𝑖 𝑛𝑒 𝐶𝑘 |𝐶𝑘|(|𝐶𝑘| 2)⎞⎟⎟⎠ , where 𝑐is the number of clusters, 𝑂𝑖is number of clusters the 𝑖belongs to, where |𝐶𝑘|is the number of nodes and 𝑛𝑒 𝐶𝑘is the number of edges that the 𝑘th cluster 𝐶𝑘contains. The third modularity for the overlapping communities is defined by Cao in [44]and leverages the weighted edges by cosine similarity of the node’s neighborhood to tackle the problem of resolution limit. Resolution limit means favoring large communities by a modularity measure. This disadvantage can be limited by properly weighted edges [44]. The modularity is defined as follows: 𝑀𝑤=1 2𝑊 𝑐 ∑ 𝑘=1 ∑ 𝑖,𝑗∈𝑉 (𝑤𝑖𝑗 −𝑠𝑖𝑠𝑗 2𝑊)𝑢𝑘𝑖𝑢𝑘𝑗 , where 𝑈=[𝑢𝑘𝑖]and the value represents the degree to which node 𝑣𝑖is in the 𝑘th community, the edge weight is 𝑤𝑖𝑗 =|𝑁(𝑖)∩𝑁(𝑗)| √|𝑁(𝑖)||𝑁(𝑗)|, the strength of node 𝑣𝑖is 𝑠𝑖=∑𝑗∈𝑁(𝑖)𝑤𝑖𝑗 and 𝑊is the total weight of the edges. 1The code for the method is available online https://anonymous .4open .science /r /graph _hierarchical _agglomerative _clustering -C946 /README .md. Information Sciences 662 (2024) 120271 8 P. Dráždilová, P. Prokop, J. Platoš et al. Fig. 2. Dendrograms of GHAC method with the proposed dissimilarities 𝑑𝑆𝐿 𝐺𝐻𝐴𝐶 and 𝑑𝐶𝐿 𝐺𝐻𝐴𝐶 for Zachary’s karate club network, where all maximal cliques are the input bases for the GHAC. The network cover in each agglomerative step is evaluated and the values are given in line plots. The bottom axis illustrates the agglomerative steps in the GHAC method, and the top axis portrays the respective dissimilarities. 5.2. Indication of the cut level in dendrogram by modularity Zachary’s karate club network is used in this section to demonstrate the process of choosing the best level of a cut in a dendrogram. Fig. 2presents a dendrogram that visually represents the agglomerative process of the proposed method, revealing the agglomeration of maximal cliques and clusters, and providing insights into the underlying structure. The bottom axis of the dendrogram demonstrates the agglomerative steps of the algorithm, while the top axis corresponds to the level of cuts based on dissimilarity value. Throughout the agglomeration process, the quality of network cover is assessed using modularities as a structural quality measure. The progress of the modularities values during the agglomerative stage of the GHAC method can be observed in Fig. 2through the three line plots displayed on the top. The highest modularity value for each line plot is selected and depicted as a dotted line, indicating a cut in the dendrogram. In our proposed community detection algorithm, this dotted line represents the cut in the dendrogram, where the bases are merged and mapped to nodes of the network. It is noteworthy that the 𝑀𝑒and 𝑀𝑤exhibit the same cut level in the dendrogram, while 𝑀𝑜𝑣 indicates a different cut level. By comparing the corresponding dendrograms (illustrated in Fig. 2) obtained for methods SL GHAC and CL GHAC, we observe significant differences in the hierarchical structure. The higher overall modularity values 𝑀𝑒and 𝑀𝑤are achieved as seen in Fig. 2b, while Fig. 2a shows a higher modularity value for 𝑀𝑜𝑣. Each highlighted cut within the dendrogram corresponds to a network cover that is further visualized in Fig. 3in the original network. During the analysis of the SL GHAC method, we can observe the equivalent result to the 𝑘-CPM method (with 𝑘 =3) as the cut in the dendrogram occurred at step 27, represented by a grey dotted line with a dissimilarity value of a cut 𝑑𝑆𝐿 𝐻𝐴𝐶 =4∕3 on the top axis. SL GHAC continues with the detection of larger clusters -over and above the clusters detected via clique percolation. The modularity measures 𝑀𝑒and 𝑀𝑤indicated the best cut for the agglomerative step 11. Different optimal cut at level 32 was identified by modularity 𝑀𝑜𝑣. The network covers obtained from the SL GHAC method can be observed in Fig. 3b and Fig. 3e. It is worth mentioning that none of these network covers exhibit intuitively meaningful communities for the main actors of the social network. The author in [46] discussed the difficulties with the 𝑘-CPM in Zachary’s karate network, where the community detection method is not able to distinguish between communities associated with two key individuals (node 0and 33) who played pivotal roles in the division of the karate club. The obtained communities for the 𝑘-CPM method can be observed in Fig. 3a and Fig. 3d. Information Sciences 662 (2024) 120271 9 P. Dráždilová, P. Prokop, J. Platoš et al. Fig. 3. Illustration of the network covers detected by different methods for Zachary’s karate club network. The grey color is used for communities with single nodes. The dendrogram in Fig. 2b shows a different hierarchical structure for the CL GHAC method. The corresponding network cover, as displayed in Fig. 3c, reveals the presence of separate communities specifically formed for nodes 0and 33 within the karate club. These communities are visually represented by the colors blue and orange, respectively. Additionally, there is a purple community that exhibits overlaps and shared vertices between both main actors in the karate club. 5.3. Hierarchical aspects of the proposed methods The hierarchical aspects of the proposed methods are studied for Coauthorships in network science. The different hierarchical structures for the proposed methods are visualized by dendrograms. The relation between the hierarchy and the detected overlapping communities is discussed for SL GHAC and CL GHAC. One of the primary advantages of the proposed method is its ability to reveal the hierarchical structure of maximal cliques within a network. A single cut in a dendrogram yields communities but offers a limited perspective of the community structure. Nevertheless, the sequence of the network covers displayed in Figs. 5b, 5d, and 5f demonstrate the agglomerative process of the CL GHAC across various steps and reveal a hierarchy of some communities. For instance, focusing on the node representing M. Newman in the network (denoted in the top right corner), we observe the node’s assignment to five communities in Fig. 5b. His two communities in step 141 of Fig. 4b are colored in light khaki and light purple in Fig. 5d, which are subsequently merged into a single purple community as portrayed in Fig. 5f. The cut level indicated by modularities 𝑀𝑒and 𝑀𝑤for the SL GHAC equates to 𝑘-CPM, due to the dissimilarity value 𝑑𝑆𝐿 𝐺𝐻𝐴𝐶 = 4∕3. The complete hierarchical structure created by SL GHAC is visualized as a dendrogram in Fig. 4a. This dendrogram allows us to examine the outcomes of the method beyond the percolation of the 𝑘-CPM method for 𝑘 =3. This dendrogram also provides a visual representation of the hierarchical structure, enabling manual inspection. The formation of long and connected structures is evident in the SL GHAC dendrogram in Fig. 4a. At level 136, approximately 50% of the bases are incorporated into a single cluster during agglomeration which is the effect of chaining characteristic for the SL approach. This cut’s outcome is visualized in Fig. 5c, where the community highlighted by blue color corresponds to the agglomeration in the bottom half of the dendrogram. In contrast, the hierarchical community structure for CL GHAC is more balanced, merging similar numbers of bases to form clusters at different hierarchical levels. The network covers for CL GHAC contain more locally-centered communities compared to SL GHAC. Figs. 5c and 5d illustrate similar numbers of detected communities, but with markedly distinct community structures. 5.4. Empirical evaluation of the proposed community detection methods for selected real-world networks We have examined the outcomes of our proposed methods by applying them to a selection of real-world networks. The subsequent sections will provide a detailed analysis of the results obtained for selected networks.