Enhancing Community Detection in Networks: A Comparative Analysis of Local Metrics and Hierarchical Algorithms

Hierarchical clustering is an unsupervised technique of machine learning that iteratively runs until the formation of a dendrogram, where each leaf represents individual instances and the root encompasses the entire dataset [1].
Hierarchical algorithms operate from two perspectives: agglomerative and divisive. Agglomerative algorithms traverse the information from the leaves to the root, generating clusters. Conversely, divisive algorithms start from the root and progress through the tree to its leaves, forming groups by dividing them based on their differences. Due to the characteristics and size of the data, it is more common to begin with a large dataset and progressively divide it until a small number of clusters are formed; therefore, divisive methods are usually preferred.

Girvan and Newman proposed a hierarchical divisive algorithm for the detection of communities in networks, using ”edge betweenness” as the key metric to identify links that separate communities. Edge betweenness is a fundamental concept in network analysis, defined as the count of the shortest paths that pass through each edge.

The greater the number of these paths, the higher the likelihood that an edge connects different communities. This metric is instrumental in determining the sequence of divisions in a traditional hierarchical divisive algorithm, guiding the process of delineating community boundaries effectively.

Formally, the ”Edge betweenness” for each edge is denoted as $e\in E$.

$$C_{B}(e)=\sum_{u,v\in V}\frac{g_{e}(u,v)}{g(u,v)}$$

where $g(u,v)$ is the minimum number of edges between the nodes $u$ and $v$, is the minimum number of edges between and but passing through the node $e$ . Wherefore the betweenness coefficient for the node $e$ is denoted as $C_{B}(e)$. Small values of $C_{B}(e)$ indicate that the edges belong to the same community, while those edges that connect different communities as ”bridges” will have higher values. [8].
To execute a complete division process, Girvan and Newman’s algorithm computes the betweenness coefficient for each node in the network. Then, iteratively, as long as an edge’s betweenness remains above a predefined threshold, the edge with the highest value is removed, and the coefficient is recalculated for the remaining network.
One of the principal drawbacks of Girvan and Newman’s algorithm is its algorithmic complexity. In each iteration, the betweenness coefficient of every edge must be recalculated, resulting in a worst-case complexity of $O(n3)$ in highly dense networks, where $m\propto n$ indicates the number of edges m is proportional to the number of nodes n. [8] Despite yielding favorable results, this complexity constrains its practical application in large networks.

Radicchi’s algorithm [4], similar to that of Girvan and Newman, aims to identify communities within a network. However, unlike the latter which relies on calculating an edge betweenness coefficient, Radicchi’s method is based on the concepts of connectivity and clustering.

A community is characterized by highly connected nodes, leading to frequent cycles among nodes within the same community. Conversely, links that connect different communities tend to participate in fewer cycles, thus having a lower probability of being part of a cycle [9].

Radicchi’s algorithm employs an edge clustering coefficient to determine an edge’s likelihood of belonging to a community, which is formally defined as:

$$c_{ij}=\frac{z_{ij}+1}{\min(k_{i}-1,k_{j}-1)}$$

Where $z_{ij}$ is the number of triangles formed with that edge, involving nodes $i$ and $j$, $k_{i}$ is the degree of node $i$, and $k_{j}$ the degree of node $j$. The numerator +1 added to $z_{ij}$ prevents excessively penalizing edges that do not belong to any triangles. In instances where $k_{i}$ or $k_{j}$ is 1, the equation would diverge; hence, such edges are excluded from consideration. In the Radicchi algorithm, smaller coefficients $c_{ij}$ indicate membership within a community. The algorithm involves removing edges with low coefficients and then recalculating the coefficient for the remaining edges [9].

Radicchi’s algorithm specifically targets small cycles of length 3, recognizing that edges facilitating inter-community connections typically exhibit a low clustering coefficient. This highlights the clustering-coefficient as a reliable indicator for identifying bridges between communities [4].

Link prediction in network structures is a supervised learning approach that can improve the efficiency of the Girvan and Newman algorithm and address the limitations of the Radicchi algorithm. This technique aims to leverage the intrinsic properties of nodes and edges, as well as their behaviors within the network, to enhance community detection [8].

Employing a hierarchical approach, the process iteratively decides which edges should be eliminated or retained to construct subgraphs [12]. Girvan and Newman’s algorithm uses the modularity criterion to evaluate the strength of each edge in relation to the overall graph. Similarly, Radicchi’s algorithm, based on the same principle, aims to establish connectivity between nodes through the connectivity principle.

Over the years, a few techniques have been proposed for the prediction of links in complex networks. These include local medical, quasi-local, classification-based, metaheuristic, and factor-based techniques [5].

Research conducted by Liben-Nowell and Kleinberg [13] , Zhou et al. [14], and others have demonstrated that local link prediction methods produce favorable outcomes with significantly less computational complexity compared to global clustering-based techniques [15]. Similarly, studies by Wu [16] and Kumar [17] have explored link prediction strategies that rely on the clustering coefficient.

It is important to note that local link prediction methods inherently cannot predict the existence of links between remotely located nodes. Nonetheless, because most links tend to form within a specific neighborhood, and considering the computational advantages they provide, local link prediction techniques are ideally suited to enhance the performance of existing hierarchical community detection methods.

Among the most common measures for link prediction are:

Common Neighbors (CN): For a node $x$, $\Gamma_{x}$ denotes the set of communities to which $x$ belongs. This measure is grounded in identifying the number of neighbors common between a pair of nodes $(x,y)$. The greater the number of common neighbors, the higher the probability of an edge existing between them. The similarity function is defined as [18]:

$$s(x,y)=|\Gamma_{x}\cap\Gamma_{y}|$$

Values close to zero suggest that the two nodes have no neighbors in common and are therefore ”farther away” from each other. Conversely, a value close to one indicates that the nodes are ”close” to each other. Due to its simplicity, this measure forms the foundation for other link prediction and evaluation metrics. Its computational complexity is estimated to be $O(vk^{3})$ where v represents the number of nodes and k the maximum degree of nodes [5].

The Adamic-Adar Index (AA): This metric evaluates the connection strength between a pair of nodes based on the number of common edges they share, similar to the Common Neighbors approach. However, the Adamic-Adar Index enhances this basic measure by weighting the shared edges according to the inverse of their frequency of occurrence. This approach recognizes that not all shared connections contribute equally to the likelihood of a link, with less frequent connections often indicating stronger mutual relevance[19]:

$$s(x,y)=\sum_{z\in\Gamma_{x}\cap\Gamma_{y}}\frac{1}{\log|\Gamma_{z}|}$$

The Resource Allocation Index (RA):This metric is based on the process of allocating resources from one community to another through a common path that includes two shared nodes $(x,y)$ [14]:

$$s(x,y)=\sum_{z\in\Gamma_{x}\cap\Gamma_{y}}\frac{1}{|\Gamma_{z}|}$$

The Preferential Attachment Index (PA):This index considers that the existence of a link between two nodes is determined simply by the number of links each node has. In this way, the presence of an edge between a pair of nodes is determined by the number of connected nodes, without considering any additional information [20]:

$$s(x,y)=|\Gamma_{x}|\cdot|\Gamma_{y}|$$

The Jaccard Index (JA):Proposed by Paul Jaccard, this index is primarily used to compare the similarity and difference between two sets by analyzing the relationship between a pair of nodes $(x,y)$[21]:

$$s(x,y)=\frac{|\Gamma_{x}\cap\Gamma_{y}|}{|\Gamma_{x}\cup\Gamma_{y}|}$$

Sørensen Index (JA):is a proposal by Sørensen to assess the similarity between ecological data samples [22]. It’s also very similar to Jaccard’s measurement.

$$+s(x,y)=\frac{2|\Gamma_{x}\cap\Gamma_{y}|}{|\Gamma_{x}|+|\Gamma_{y}|}$$

Salton Index:Also known as the Salton Cosine Index [23], it is used to determine the similarity between two datasets based on the cosine similarity between the rows of the adjacency matrix corresponding to nodes x and y [24].

$$s(x,y)=\frac{|\Gamma_{x}\cap\Gamma_{y}|}{\sqrt{|\Gamma_{x}|\cdot|\Gamma_{y}|}}$$

Hub Depressed index:the depressed hub is the result of the modularity study in metabolic networks conducted by Ravasz et al. [25] it is defined as the proportion of common neighbors between x and y with the highest degree between them.

$$s(x,y)=\frac{|\Gamma_{x}\cap\Gamma_{y}|}{\max(|\Gamma_{x}|,|\Gamma_{y}|)}$$

Hub promoted index:Reciprocally, the Hub Promoted Index is defined as the proportion of common neighbors between X and Y with the minimum degree between them. [25]

$$s(x,y)=\frac{|\Gamma_{x}\cap\Gamma_{y}|}{\min(|\Gamma_{x}|,|\Gamma_{y}|)}\\ \\$$

Local Leicht-Holme-Newman Index:Similar to the Jaccard and Salton indices but more sensitive to differences [26], it is defined as the ratio of the common neighbors of nodes x and y to the product of the degrees of nodes x and y.

$$s(x,y)=\frac{|\Gamma_{x}\cap\Gamma_{y}|}{|\Gamma_{x}|\cdot|\Gamma_{y}|}$$

It is evident that most local prediction measures are based on the measure of common neighbors, except for the measure of preferential attachment [15]. For more information on these measures, see the works by Lü and Zhou [18] or Martinez et al. [5], which provide an extensive overview of different link prediction measures.

Determining the exact division of a graph to separate it into two or more communities is not trivial. Various methods have been developed to quantify the quality of the partitioning depending on the characteristics of the graph. Among the most relevant are the Modularity Index and the Normalized Mutual Information Index.

The Modularity Index [8] is one of the most commonly used metrics for community detection, and it is the basis for Girvan-Newman’s algorithm. This index compares the set of links within a cluster to what would be expected if the links were distributed randomly. Densities inside and outside each cluster are calculated and compared to the overall density that the network would have if it were random [27]. It is defined as:

$$Q=\sum_{r}(e_{rr}-a_{r}^{2})$$

Where are set of edges within a cluster represents the set of nodes that are part of the cluster [27]. The value of this metric tends to 1; values close to 1 indicate that the cluster is highly connected. In practice, it has been observed that communities typically present a modularity value between 0.3 and 0 [27].

Another metric is based on information theory, where two partitions are similar if little information is needed to infer that one partition is equal to another. This amount of information can be measured as entropy [19].

$$H(C)=-\sum_{i=1}^{k}\left[P(i)\log_{2}P(i)\right],\quad P(i)=\frac{|C_{i}|}{n},\quad C_{i}\in C$$

where for each cluster the probability is calculated. The lower the entropy, the more stable the clustering [1].

The mutual information index assesses how much the uncertainty of a random node about a cluster can be reduced if the state of the original node and its true cluster membership are known in advance [28]. It is defined as follows:

$$J(X,Y)=\sum_{i=1}^{n_{x}}\sum_{j=1}^{n_{y}}\left[P(i,j)\log_{2}\left(\frac{P(i,j)}{P(i)P(j)}\right)\right]$$

$$\quad P(i,j)=\frac{|X_{i}\cap Y_{j}|}{n}$$

The probability that a node belongs to a cluster and also belongs to another cluster is considered. To limit the value that this measurement can take, normalization is implemented [28].

$$\text{"NMI"}_{2}(X,Y)=\frac{2J(X,Y)}{H(X)+H(Y)}$$

The important aspect of this measure is its ability to analyze clusters without needing to know the clustering method or the original characteristics of the network directly. The measurement ranges between 0 and 1, where 1 indicates that the partitions are identical, and 0 indicates that the partitions are completely independent [29].

The following network data sets were obtained from networkrepository.com [30], SNAP [31], and Pajek datasets [32]:

• •

  Zachary’s karate club [33]

• •

  Word adjacencies [8]

• •

  Dolphin [34]

• •

  Les Misérables [35]

• •

  U.S. politics [36]

• •

  American football [4]

We used a total of 12 different criteria to build the hierarchical community detection algorithm, evaluating its performance in terms of modularity. In optimization-based community detection algorithms, modularity is any numerical measure that helps identify communities in networks. However, in this case, we are specifically referring to the original Q modularity defined by Newman [37].

Calculating modularity doesn’t depend on knowing the number of communities beforehand. We conducted an exploratory analysis ranging from 2 to 10 communities to see how the metric behaves in comparison to the Girvan-Newman reference algorithm.

Table 1 provides a comprehensive summary of the fundamental characteristics of various networks analyzed in our study. It details crucial aspects such as the number of nodes and edges, which offer an overview of the scale and complexity of each network. Additionally, key centrality metrics such as average degree, betweenness centrality, closeness centrality, along with the clustering coefficient and the average path length are included. These indicators are essential for understanding the internal structure and dynamics of the networks, thus allowing a deeper assessment of their behavior and effectiveness in community detection. Each network, from ”adjnoun” to ”Polbooks”, displays variations in these metrics, reflecting their unique structures and providing valuable insights for future research and applications in computer science and network analysis.

To examine the modularity obtained by the algorithms, we operate on the principle of ignoring the ”correct” answer. Instead, we aim to select the community structure that maximizes the basic Girvan algorithm’s modularity coefficient. Both Newman and the Radicchi adaptation were tested with 10 communities. Furthermore, the elbow method, which calculates variations in modularity using a sliding window, was employed to determine the optimal number of communities (see Table 2).

The behavior of modularity and elbow selection can be observed in the context of varying modularity, with comparable outcomes observed between the communities identified through Girvan Newman and those identified through Radicchi.

Table 4 emphasizes the stability and accuracy differences between the Girvan-Newman and Radicchi algorithms by evaluating community structures at 2, 3, and 5 community increments. The analysis identifies the three-term window elbow method as the most stable and effective, particularly when integrated with local metrics to enhance the precision and robustness of community detection.

The Radicchi algorithm is employed to determine the local evaluation of links, serving as a heuristic to establish their importance within the network and to identify the critical links for partitioning the network. Modularity is evaluated for each configuration, with up to 10 communities detected for each network.

In Figure 1 can be observed that in certain groups, the process of detecting communities based on local metrics exhibits modularity behavior comparable to that detected by the methods of Girvan-Newman and Radicchi. This is exemplified by the football, karate, and polbooks networks. Conversely, the adjnoun, dolphins, and lesmis networks, which employ local metrics, do not effectively build communities that maximize the modularity index in a manner similar to the base methods.

The effectiveness of local analysis techniques varies considerably depending on the characteristics of the analyzed network. Groups where local metrics exhibit some degree of success tend to be better-connected networks, as evidenced by a higher degree and eigenvector centrality average. Conversely, networks where local measures fail to identify communities based on modularity have a lower average clustering coefficient, indicating a less dense network structure.

The karate network demonstrated the greatest efficacy in identifying communities through the application of local metrics to evaluate modularity, as evidenced by the graph above. To assess the degree of concordance between the outcomes yielded by the algorithms of Girvan and Newman, Radicchi, and those derived from local measurements, modularity, and the coefficient of normalized mutual information, a detailed analysis will be conducted.

Girvan Newman’s basic method is the one that offers a high degree of modularity from the outset of the detection process, reaching a maximum of 5 communities and with the optimal number of communities analysis falling between 2 and 5 communities. Radicchi’s method also exhibits a similar behavior, achieving its maximum in 4 communities and with an elbow over 3 and 4 communities, the value of maximum modularity being somewhat lower.

Some metrics that are similar to the results obtained by Girvan Newman are JA (Jaccard), SO (Salton), and SA (Sorensen), which focus on highlighting the similarity between a set of neighboring nodes and achieving modularity results similar to those found by Radicchi. Similarly, methods such as HD (Hub Depressed) and HP (Hub Promoted) focus on the analysis of nodes with a high degree of node connectivity.

In the final stage of the analysis, the most suitable metrics for approximating the behavior of Girvan Newman’s base method will be identified for the four community configurations previously identified.

For the analyzed network, the NMI (Normalized Mutual Information) was high in the local metrics when they exceeded three communities, achieving a rate of approximately 70% or more in the allocation of nodes to the same communities detected by the Girvan-Newman base method, even surpassing Radicchi’s method by a small margin.

Regarding the metrics that yielded unsatisfactory results, it should be noted that they are not entirely without merit. In most cases, they yielded indicators above 24%, indicating a tendency to detect communities in a manner similar to the original method.