Significant worsening of NMI and C /C in Figs 1 and 2. Among all the algorithms, Label propagation and Multilevel algorithms are much faster than the others (Panel (d,e), Fig. 3), while Spinglass and Edge betweenness are the slowest ones (Panel (g,h), Fig. 3).The observed mixing parameter. Unlike the number of nodes in a network, the exact value of the mixing parameter of a graph is unobservable if ground truth is unavailable for the community assignment of nodes. In this section, we study the mixing parameter delivered by the community detection algorithms ?as a function of the mixing parameter (see Eq. 1). The results of the different algorithms are shown in the different panels of Fig. 4. Each panel is subdivided in two plots: the lower has the average computed value of ? while the upper sub-panel contains the standard deviation of the measures when repeated over 100 different network realisations. All algorithms have a linear (identity) relationship between ?and except for the Leading eigenvector algorithm, which overshoots the results (Panel (c), Fig. 4). Most of the algorithms display a turning point where the estimation of ?breaks down. For the Fastgreedy, Multilevel, Walktrap, Spinglass, and Edge betweenness algorithms, ?changes in a smooth fashion (Panel (a,e ), Fig. 4). For the Infomap and Label propagation algorithms, the Stattic web estimated mixing parameter ?has a steep change at around ? 0.55 and ? 0.5, separately (Panel (b,d), Fig. 4). Overall, the mixing parameter obtained by the algorithms ?fits well with the real mixing parameter at small value of , but it differs from the real value with increasing . For certain algorithms, the estimation fails completely for larger values of (Infomap, Label propagation), and for the others it is either overestimated (Edge betweenness) or slightly underestimated (Fastgreedy, Walktrap, Spinglass). Remarkably, in the Multilevel algorithm, the estimation is very accurate for values as large as = 0.75 for all network sizes analysed.Scientific RepoRts | 6:30750 | DOI: 10.1038/srepwww.nature.com/scientificreports/Figure 2. The mean value of the estimated number of AZD3759 chemical information communities delivered by different algorithms over the real number of communities given by the LFR benchmark, i.e., C /C , dependent on the mixing parameter on a log-linear scale. Different colours refer to different number of nodes: red (N = 233), green (N = 482), blue (N = 1000), black (N = 3583), cyan (N = 8916), and purple (N = 22186). Please notice that the vertical axis might have different scale ranges. The vertical red line corresponds to the strong definition of community where = 0.5 and the horizontal green line represents the case that C = C . The other parameters are described in Table 1.The role of network size. So far we have only discussed the role of the mixing parameter to the accuracy and the computing time of community detection algorithms. Now, as an important ingredient, we consider the effect of network size. In our definition of the benchmark graphs, with a fixed average degree, network size can be represented as the number of nodes in the network. The results are shown in Fig. 5 on a linear-log scale. Each ofScientific RepoRts | 6:30750 | DOI: 10.1038/srepwww.nature.com/scientificreports/Figure 3. (Lower row) The mean value of the computing time of the community detection algorithms (in seconds) dependent on the mixing parameter on a log-linear scale. (upper row) The standard deviation of the measures on a log.Significant worsening of NMI and C /C in Figs 1 and 2. Among all the algorithms, Label propagation and Multilevel algorithms are much faster than the others (Panel (d,e), Fig. 3), while Spinglass and Edge betweenness are the slowest ones (Panel (g,h), Fig. 3).The observed mixing parameter. Unlike the number of nodes in a network, the exact value of the mixing parameter of a graph is unobservable if ground truth is unavailable for the community assignment of nodes. In this section, we study the mixing parameter delivered by the community detection algorithms ?as a function of the mixing parameter (see Eq. 1). The results of the different algorithms are shown in the different panels of Fig. 4. Each panel is subdivided in two plots: the lower has the average computed value of ? while the upper sub-panel contains the standard deviation of the measures when repeated over 100 different network realisations. All algorithms have a linear (identity) relationship between ?and except for the Leading eigenvector algorithm, which overshoots the results (Panel (c), Fig. 4). Most of the algorithms display a turning point where the estimation of ?breaks down. For the Fastgreedy, Multilevel, Walktrap, Spinglass, and Edge betweenness algorithms, ?changes in a smooth fashion (Panel (a,e ), Fig. 4). For the Infomap and Label propagation algorithms, the estimated mixing parameter ?has a steep change at around ? 0.55 and ? 0.5, separately (Panel (b,d), Fig. 4). Overall, the mixing parameter obtained by the algorithms ?fits well with the real mixing parameter at small value of , but it differs from the real value with increasing . For certain algorithms, the estimation fails completely for larger values of (Infomap, Label propagation), and for the others it is either overestimated (Edge betweenness) or slightly underestimated (Fastgreedy, Walktrap, Spinglass). Remarkably, in the Multilevel algorithm, the estimation is very accurate for values as large as = 0.75 for all network sizes analysed.Scientific RepoRts | 6:30750 | DOI: 10.1038/srepwww.nature.com/scientificreports/Figure 2. The mean value of the estimated number of communities delivered by different algorithms over the real number of communities given by the LFR benchmark, i.e., C /C , dependent on the mixing parameter on a log-linear scale. Different colours refer to different number of nodes: red (N = 233), green (N = 482), blue (N = 1000), black (N = 3583), cyan (N = 8916), and purple (N = 22186). Please notice that the vertical axis might have different scale ranges. The vertical red line corresponds to the strong definition of community where = 0.5 and the horizontal green line represents the case that C = C . The other parameters are described in Table 1.The role of network size. So far we have only discussed the role of the mixing parameter to the accuracy and the computing time of community detection algorithms. Now, as an important ingredient, we consider the effect of network size. In our definition of the benchmark graphs, with a fixed average degree, network size can be represented as the number of nodes in the network. The results are shown in Fig. 5 on a linear-log scale. Each ofScientific RepoRts | 6:30750 | DOI: 10.1038/srepwww.nature.com/scientificreports/Figure 3. (Lower row) The mean value of the computing time of the community detection algorithms (in seconds) dependent on the mixing parameter on a log-linear scale. (upper row) The standard deviation of the measures on a log.
