In order to evaluate the performance of our proposed algorithm, we compare it with other algorithms named GAME117GAME224GAME325SLPA22OSLOM26CPM27CME28 and LFM29. GAME1 is based on non-cooperative game theory with the time complexity of (O(m^2)). GAME 2 and GAME3 are based on cooperative game theory with the time complexity of (O(n^2)) and (O(n.log(n) )+O(n.k_{max}))respectively ((k_{max}) is the maximum degree of the graph). The results of our algorithm in this section are obtained by set (epsilon) value at 0.01. The results of other algorithms are taken from the original articles of these algorithms or from comparative studies30. In these articles for algorithms with adjustable parameters, it is stated that the results with the best setting are reported.

Evaluation criteria

There are different metrics to evaluate the results obtained from the algorithms, and it is often difficult because no canonical solution is available.31. Extensive discussion of the relationship between topological properties of community structure and alternative evaluation measures and the reliability of different evaluation criteria has been addressed in many studies.32. First, the choice of appropriate evaluation criteria depends on whether or not there is a known ground truth for the network being examined. In cases where the ground truth is known, various assessment measures, including the average F1 score (AvgF1)33Adjusted Rand Index (ARI), which ensures that the value of random clustering is close to zero, Omega Index34which is the overlay version of ARI30 and adopts the number of clusters that each node pair shares, to compare detected communities against ground truth communities, and normalized mutual information (NMI)35, derived from information theory, are widely used. In the current work, we used AvgF1 and an extended version of NMI, which is suitable for the comparison of two overlapping community structures.29. The closer the value of NMI or AvgF1 is to 1, the more the community structure detected is similar to the ground truth; and the value 0 indicates the least similarity.

When it comes to testing the performance of overlapping community detection algorithms, especially when the ground truth of the communities is unknown, the (Q_{ov}) is a well-known and frequently used measure36. It is an extension of classic modularity, and the highest value of it means the best detected communities. For directed networks, this metric is defined as follows:

$$begin{aligned} Q_{ov}=frac{1}{m} sum _{c in C} ; sum _{i,j in V} left[ beta _{l(i,j),c}A_{j,j}-frac{beta _{l(i,j)}^{out}k_{i}^{out}beta _{l(i,j)}^{in}k_{j}^{in}}{m} right] end{aligned}$$

(8)

By applying minor modifications as follows, it can be used for unoriented networks:

$$begin{aligned} Q_{ov}=frac{1}{2m} sum _{c in C} ; sum _{i,j in V} left[ beta _{l(i,j),c}A_{j,j}-frac{beta _{l(i,j)}^{‘}k_{i}beta _{l(i,j)}^{‘}k_{j}}{2m} right] end{aligned}$$

(9)

The components of this equation are given by:

$$begin{aligned} beta _{l(i,j)}^{‘}=beta _{l(i,j)}^{out}= & {} beta _{l(i, j)}^{in}= frac{sum _{i in V}F(alpha _{i,c},alpha _{j,c})}{|V|} end{aligned }$$

(ten)

$$begin{aligned} beta _{l(i,j)}= & {} F(alpha _{i,c},alpha _{j,c}) end{aligned}$$

(11)

$$begin{aligned} k_{i}^{out}=k_{i}^{in}= & {} k_{i} end{aligned}$$

(12)

$$begin{aligned} F(alpha _{i,c},alpha _{j,c})= & {} frac{1}{(1+e^{f(alpha _{i ,c})})(1+e^{f(alpha _{j,c})})} end{aligned}$$

(13)

$$begin{aligned} f(x)=2px-p, p in {mathbb {R}} end{aligned}$$

(14)

where (alpha _{(i,c)}) is the membership coefficient of the node I to the community vs and p in F(X) is an arbitrary value, which in the current study is set to 30.

Synthetic networks

Figure 5

Synthetic LFR networks used for performance testing.

Figure 6
number 6

Comparative NMI value for proposed and other algorithms on synthetic LFR networks listed in Fig. 5.

One of the best known reference networks is the synthetic networks called LFR which can be generated by the method proposed by Lancichinetti and Fortunato37. While in real-world networks the degree correlation between nodes is clearly non-zero and the transitivity is relatively high, the networks generated by the LFR method have a degree correlation close to zero and low transitivity38,39,40. Despite this disadvantage and some other limitations of the LFR method, these networks still exhibit relatively very high realistic properties, and considering a large amount of experimental data available from testing other algorithms on them, LFR networks are among the most appropriate choices for community detection. performance testing of algorithms. In networks made by this method, 10 parameters are adjustable. By setting these parameters, we generated 6 groups of LFR networks for performance testing as shown in Fig. 5. The mixing parameter (mu) refers to the fraction of links through which a node connects to other nodes in other communities; (k_i^{in}=(1-mu )k_i). (tau _1) and (tau _2) are exponents of the power-law distribution of node degrees and community sizes, respectively. In addition, the overlapping characteristics of the LFR network are controlled by Om (the number of communities each overlapping node belongs to) and On (the fraction of nodes that belongs to more than one community). It should be noted that for our algorithm performance test on LFR networks, we reported average results of runs on at least 10 instantiations of these networks for each set of parameters.

NMI values ​​for results obtained using our and other proposed algorithms are shown in Fig. 6. As expected, increasing Om, NMI values ​​gradually decrease. However, it is observed that in most cases our algorithm outperforms others, especially in synthetic networks with smaller community sizes and more overlapping nodes.

Picture 7
number 7

Fraction of overlapping nodes detected by the proposed algorithms and others in LFR3 and LFR4.

Picture 8
figure 8

Histogram of community sizes detected for LFR3 (average over all Om). In each graph, the height of the peaks is written next to them if they fall outside the frame.

When dealing with networks with overlapping communities, evaluating the performance of a community detection algorithm should include checking the number of identified overlapping nodes, which is one of the important parameters determining the accuracy of the algorithm. Overlapping nodes play a crucial role in real-world social networks considering that they usually act as bridges or messengers between communities30. Identified On detected by the proposed algorithms and others for two groups of LFRs with ground truth On of 0.1 and 0.5 are shown in Fig. 7. Overlapping nodes identified by our algorithm increase incrementally by increasing Om. This trend contrasts with other algorithms except SLPA in the LFR3 network.

In an effort to find a more comprehensive insight into the performance of the algorithms, it would be beneficial to study the distribution of detected community sizes (CS). For this, we used results of algorithms on LFR3 by averaging over all values Om and 10 instantiations of these networks. In the community size histogram shown in Figure 8, small fluctuations have been omitted by representing fitted curves instead of raw data. For comparison, the ground truth power law distribution is visible in each histogram. Except for ours and the SLPA algorithms, other algorithms have remarkable weaknesses in detecting larger communities. Also, some algorithms tend to split communities into smaller parts, causing the distribution to become concentrated in the range of small communities that don’t exist in the actual distribution. Although such missed clustering occurs to some extent by our algorithm, it is not as much as some other algorithms such as GAME1, LFM, and especially CPM and OSLOM. In particular, the results demonstrate the relatively better performance of our algorithm in detecting larger communities.

real networks

Picture 9
number 9
Picture 10
number 10

(a) Ground truth and detected community structure of the karate network. (b) The (Q_{ov}) value obtained by the proposed algorithms and others on the first six real-world networks.

Picture 11
figure 11

The value of the AvgF1 score obtained by the proposed algorithms and others on the last two real-world networks with a known community structure (ground truth).

In order to further evaluate the proposed algorithm, we tested its performance on some real-world networks. Eight real networks were chosen for this test, and their description can be seen in Fig. 9 (data for the last three larger networks are available at http://snap.stanford.edu). As an evaluation measure, for the first six networks and for the last two, the superimposed modularity and the AvgF1 score were used, respectively.

Stack bar chart (Q_{ov}) for the community structure obtained from the first six networks by ours and other algorithms are shown in Fig. 10. Such an illustration allows us to compare the overall performance of the algorithms on the six networks. Our algorithm gets (Q_{ov}) value for Dolphins, Football, Polbooks and PGP, which is slightly higher than other algorithms. Moreover, the sum of (Q_{ov}) obtained by our algorithm is higher than the others. As an example, the community structure of the karate network, which is obtained by our algorithm, is shown in Fig. 10. This network is of traditional importance and was studied by Wayne W. Zachary for three years, from 1970 to 1972.41. The ground truth of this network that was observed by Zachary contains two communities shown in Fig. 10. As can be seen, the detected community structure is exactly matched to the ground truth if we exclude node 10. However, the location of node 10 in the overlap of two communities is reasonable, considering its equal link with both.

For the last two larger networks, which have known community structure, the bar chart of AvgF1 scores for community structure obtained by ours and other algorithms is shown in Fig. 11. For these networks, in addition to the previously used algorithms, the result of BigClam33 and GLOW5 algorithms are shown for comparison. Data relating to the performance of other algorithms on these two networks is taken from the original GLEAM algorithm article5. Based on the results shown in 11, it can be seen that the proposed algorithm, together with the GLEMAo algorithm, has the best performance in detecting the community structure of these two networks.