Results of application to unweighted graphs of real datasets: IndianVillage, Yeast and FreeAssoc.

In the column of ‘Type’ in the table, ‘Ori’ denotes the original graph while ‘Inv’ the inverted graph. Further, ‘Ori.w’ denotes the weighted original graph while ‘Inv.w’ denotes the weighted inverted graph. For each cell in the table, computation time and a corresponding statistic to detect community structure are displayed. A star marker in digits denotes that the result supports the existence of community structure. These statistics and critical values are given as follows. For our method, the maximum magnitude of eigenvalues λ is used. The critical value is given by the Tracy-Widom distribution in Eq (7). For Newman and Louvain methods, modularity Q is used with the critical value 0.45, 0.48, and 0.29 for IndianVillage, Yeast and FreeAssoc, respectively, based on the analytical approximation of modularity for an Erdős-Rényi random graph. For Split method, a positive largest eigenvalue of modularity matrix λ′ suggests community structure while a negative largest eigenvalue λ′ non-community structure. For Bayesian method, the difference of marginal log-likelihood for K = 1 and K = 2 (‘Dif’; subtraction of K = 1 case from K = 2 case) is used. A positive difference suggests community structure while a negative difference non-community structure. For Bootstrap method, we evaluate stability of community structure by means of Adjusted Rand Index (ARI) between the targeted graph and bootstrapped graphs (the number of replicates is set to 100). We compare the median of ARI (mARI) with the distribution of ARI when the targeted graph is randomized. If mARI falls within the 95% confidence interval, it suggests that there is no community structure. Seemingly, this method is not computationally efficient. We were not able to obtain the results for FreeAssoc within 72 hours.