Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing. (English) Zbl 07368217
Summary: This paper surveys some recent developments in fundamental limits and optimal algorithms for network analysis. We focus on minimax optimal rates in three fundamental problems of network analysis: graphon estimation, community detection and hypothesis testing. For each problem, we review state-of-the-art results in the literature followed by general principles behind the optimal procedures that lead to minimax estimation and testing. This allows us to connect problems in network analysis to other statistical inference problems from a general perspective.
MSC:
| 62-XX | Statistics |
References:
| [1] | Abbe, E. (2017). Community detection and stochastic block models: Recent developments. J. Mach. Learn. Res. 18 Paper No. 177, 86. · Zbl 1403.62110 |
| [2] | Abbe, E., Bandeira, A. S. and Hall, G. (2016). Exact recovery in the stochastic block model. IEEE Trans. Inf. Theory 62 471-487. · Zbl 1359.94047 · doi:10.1109/TIT.2015.2490670 |
| [3] | Abbe, E. and Sandon, C. (2015). Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science—FOCS 2015 670-688. IEEE Computer Soc., Los Alamitos, CA. |
| [4] | Airoldi, E. M., Costa, T. B. and Chan, S. H. (2013). Stochastic blockmodel approximation of a graphon: Theory and consistent estimation. In Advances in Neural Information Processing Systems 692-700. |
| [5] | Aldous, D. J. (1981). Representations for partially exchangeable arrays of random variables. J. Multivariate Anal. 11 581-598. · Zbl 0474.60044 · doi:10.1016/0047-259X(81)90099-3 |
| [6] | Amini, A. A. and Levina, E. (2018). On semidefinite relaxations for the block model. Ann. Statist. 46 149-179. · Zbl 1393.62021 · doi:10.1214/17-AOS1545 |
| [7] | Amini, A. A., Chen, A., Bickel, P. J. and Levina, E. (2013). Pseudo-likelihood methods for community detection in large sparse networks. Ann. Statist. 41 2097-2122. · Zbl 1277.62166 · doi:10.1214/13-AOS1138 |
| [8] | Banerjee, D. (2018). Contiguity and non-reconstruction results for planted partition models: The dense case. Electron. J. Probab. 23 Paper No. 18, 28. · Zbl 1387.05230 |
| [9] | Banerjee, D. and Ma, Z. (2017). Optimal hypothesis testing for stochastic block models with growing degrees. Preprint. Available at arXiv:1705.05305. |
| [10] | Banerjee, D. and Ma, Z. (2018). Non-backtracking matrices and optimal hypothesis testing for stochastic block models with growing degrees. |
| [11] | Berthet, Q. and Rigollet, P. (2013). Complexity theoretic lower bounds for sparse principal component detection. In Conference on Learning Theory 1046-1066. |
| [12] | Bickel, P. J. and Chen, A. (2009). A nonparametric view of network models and Newman-Girvan and other modularities. Proc. Natl. Acad. Sci. USA 106 21068-21073. · Zbl 1359.62411 · doi:10.1073/pnas.0907096106 |
| [13] | Bickel, P. J. and Sarkar, P. (2016). Hypothesis testing for automated community detection in networks. J. R. Stat. Soc. Ser. B. Stat. Methodol. 78 253-273. · Zbl 1411.62162 · doi:10.1111/rssb.12117 |
| [14] | Borgs, C., Chayes, J. and Smith, A. (2015). Private graphon estimation for sparse graphs. In Advances in Neural Information Processing Systems 1369-1377. |
| [15] | Borgs, C., Chayes, J. T., Cohn, H. and Zhao, Y. (2014). An \(L^p\) theory of sparse graph convergence I: Limits, sparse random graph models, and power law distributions. Preprint. Available at arXiv:1401.2906. · Zbl 1417.05186 · doi:10.1090/tran/7543 |
| [16] | Borgs, C., Chayes, J. T., Cohn, H. and Ganguly, S. (2015). Consistent nonparametric estimation for heavy-tailed sparse graphs. Preprint. Available at arXiv:1508.06675. |
| [17] | Borgs, C., Chayes, J. T., Cohn, H. and Holden, N. (2017). Sparse exchangeable graphs and their limits via graphon processes. J. Mach. Learn. Res. 18 Paper No. 210, 71. · Zbl 1469.60158 |
| [18] | Borgs, C., Chayes, J. T., Cohn, H. and Zhao, Y. (2018). An \(L^p\) theory of sparse graph convergence II: LD convergence, quotients and right convergence. Ann. Probab. 46 337-396. · Zbl 1386.05099 · doi:10.1214/17-AOP1187 |
| [19] | Butucea, C., Ndaoud, M., Stepanova, N. A. and Tsybakov, A. B. (2018). Variable selection with Hamming loss. Ann. Statist. 46 1837-1875. · Zbl 1414.62126 · doi:10.1214/17-AOS1572 |
| [20] | Cai, T. T. and Li, X. (2015). Robust and computationally feasible community detection in the presence of arbitrary outlier nodes. Ann. Statist. 43 1027-1059. · Zbl 1328.62381 · doi:10.1214/14-AOS1290 |
| [21] | Cai, T. T., Ma, Z. and Wu, Y. (2013). Sparse PCA: Optimal rates and adaptive estimation. Ann. Statist. 41 3074-3110. · Zbl 1288.62099 · doi:10.1214/13-AOS1178 |
| [22] | Caron, F. and Fox, E. B. (2017). Sparse graphs using exchangeable random measures. J. R. Stat. Soc. Ser. B. Stat. Methodol. 79 1295-1366. · Zbl 1381.62072 · doi:10.1111/rssb.12233 |
| [23] | Carpentier, A. and Verzelen, N. (2019). Adaptive estimation of the sparsity in the Gaussian vector model. Ann. Statist. 47 93-126. · Zbl 1417.62113 · doi:10.1214/17-AOS1680 |
| [24] | Chan, S. and Airoldi, E. (2014). A consistent histogram estimator for exchangeable graph models. In International Conference on Machine Learning 208-216. |
| [25] | Chatterjee, S. (2015). Matrix estimation by universal singular value thresholding. Ann. Statist. 43 177-214. · Zbl 1308.62038 · doi:10.1214/14-AOS1272 |
| [26] | Chaudhuri, K., Chung, F. and Tsiatas, A. (2012). Spectral clustering of graphs with general degrees in the extended planted partition model. In Conference on Learning Theory 35-1. |
| [27] | Chen, P. and Gao, C. (2018). Minimax estimation of permutations. |
| [28] | Chen, K. and Lei, J. (2018). Network cross-validation for determining the number of communities in network data. J. Amer. Statist. Assoc. 113 241-251. · Zbl 1398.62159 · doi:10.1080/01621459.2016.1246365 |
| [29] | Chen, Y., Li, X. and Xu, J. (2018). Convexified modularity maximization for degree-corrected stochastic block models. Ann. Statist. 46 1573-1602. · Zbl 1410.62105 · doi:10.1214/17-AOS1595 |
| [30] | Cheng, Y. and Church, G. M. (2000). Biclustering of expression data. In Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology 93-103. AAAI Press, Menlo Park, CA. |
| [31] | Chin, P., Rao, A. and Vu, V. (2015). Stochastic block model and community detection in sparse graphs: A spectral algorithm with optimal rate of recovery. In Conference on Learning Theory 391-423. |
| [32] | Chung, F. and Lu, L. (2002). The average distances in random graphs with given expected degrees. Proc. Natl. Acad. Sci. USA 99 15879-15882. · Zbl 1064.05137 · doi:10.1073/pnas.252631999 |
| [33] | Coja-Oghlan, A. (2010). Graph partitioning via adaptive spectral techniques. Combin. Probab. Comput. 19 227-284. · Zbl 1209.05178 · doi:10.1017/S0963548309990514 |
| [34] | Cover, T. M. and Thomas, J. A. (2006). Elements of Information Theory, 2nd ed. Wiley Interscience, Hoboken, NJ. · Zbl 1140.94001 |
| [35] | Crane, H. (2018). Probabilistic Foundations of Statistical Network Analysis. Monographs on Statistics and Applied Probability 157. CRC Press, Boca Raton, FL. · Zbl 1490.62001 |
| [36] | Crane, H. and Dempsey, W. (2018). Edge exchangeable models for interaction networks. J. Amer. Statist. Assoc. 113 1311-1326. · Zbl 1402.90027 · doi:10.1080/01621459.2017.1341413 |
| [37] | Dasgupta, A., Hopcroft, J. E. and McSherry, F. (2004). Spectral analysis of random graphs with skewed degree distributions. In 45th Annual IEEE Symposium on Foundations of Computer Science, 2004. Proceedings 602-610. IEEE, Los Alamitos, CA. |
| [38] | Dawid, A. P. and Skene, A. M. (1979). Maximum likelihood estimation of observer error-rates using the em algorithm. Appl. Stat. 28 20-28. |
| [39] | Diaconis, P. and Graham, R. L. (1977). Spearman’s footrule as a measure of disarray. J. Roy. Statist. Soc. Ser. B 39 262-268. · Zbl 0375.62045 · doi:10.1111/j.2517-6161.1977.tb01624.x |
| [40] | Diaconis, P. and Janson, S. (2008). Graph limits and exchangeable random graphs. Rend. Mat. Appl. (7) 28 33-61. · Zbl 1162.60009 |
| [41] | Donoho, D. L. and Johnstone, I. M. (1994). Minimax risk over \(l_p\)-balls for \(l_q\)-error. Probab. Theory Related Fields 99 277-303. · Zbl 0802.62006 · doi:10.1007/BF01199026 |
| [42] | Fan, Z. and Montanari, A. (2017). How well do local algorithms solve semidefinite programs? In STOC’17—Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing 604-614. ACM, New York. · Zbl 1369.90118 |
| [43] | Fei, Y. and Chen, Y. (2019). Exponential error rates of SDP for block models: Beyond Grothendieck’s inequality. IEEE Trans. Inf. Theory 65 551-571. · Zbl 1432.90102 · doi:10.1109/TIT.2018.2839677 |
| [44] | Gao, C. (2017). Phase transitions in approximate ranking. Preprint. Available at arXiv:1711.11189. |
| [45] | Gao, C. and Lafferty, J. (2017). Testing for global network structure using small subgraph statistics. Preprint. Available at arXiv:1710.00862. |
| [46] | Gao, C., Lu, Y. and Zhou, H. H. (2015). Rate-optimal graphon estimation. Ann. Statist. 43 2624-2652. · Zbl 1332.60050 · doi:10.1214/15-AOS1354 |
| [47] | Gao, C., Lu, Y. and Zhou, D. (2016). Exact exponent in optimal rates for crowdsourcing. In International Conference on Machine Learning 603-611. |
| [48] | Gao, C., Ma, Z. and Zhou, H. H. (2017). Sparse CCA: Adaptive estimation and computational barriers. Ann. Statist. 45 2074-2101. · Zbl 1421.62073 · doi:10.1214/16-AOS1519 |
| [49] | Gao, C., van der Vaart, A. W. and Zhou, H. H. (2020). A general framework for Bayes structured linear models. Ann. Statist. 48 2848-2878. · Zbl 1471.62241 · doi:10.1214/19-AOS1909 |
| [50] | Gao, C., Ma, Z., Ren, Z. and Zhou, H. H. (2015). Minimax estimation in sparse canonical correlation analysis. Ann. Statist. 43 2168-2197. · Zbl 1327.62340 · doi:10.1214/15-AOS1332 |
| [51] | Gao, C., Lu, Y., Ma, Z. and Zhou, H. H. (2016). Optimal estimation and completion of matrices with biclustering structures. J. Mach. Learn. Res. 17 Paper No. 161, 29. · Zbl 1392.62151 |
| [52] | Gao, C., Ma, Z., Zhang, A. Y. and Zhou, H. H. (2017). Achieving optimal misclassification proportion in stochastic block models. J. Mach. Learn. Res. 18 Paper No. 60, 45. · Zbl 1440.62244 |
| [53] | Gao, C., Ma, Z., Zhang, A. Y. and Zhou, H. H. (2018). Community detection in degree-corrected block models. Ann. Statist. 46 2153-2185. · Zbl 1408.62116 · doi:10.1214/17-AOS1615 |
| [54] | Girvan, M. and Newman, M. E. J. (2002). Community structure in social and biological networks. Proc. Natl. Acad. Sci. USA 99 7821-7826. · Zbl 1032.91716 · doi:10.1073/pnas.122653799 |
| [55] | Goldenberg, A., Zheng, A. X., Fienberg, S. E. and Airoldi, E. M. (2010). A survey of statistical network models. Found. Trends Mach. Learn. 2 129-233. · Zbl 1184.68030 · doi:10.1561/2200000005 |
| [56] | Gulikers, L., Lelarge, M. and Massoulié, L. (2017). A spectral method for community detection in moderately sparse degree-corrected stochastic block models. Adv. in Appl. Probab. 49 686-721. · Zbl 1429.91261 · doi:10.1017/apr.2017.18 |
| [57] | Gulikers, L., Lelarge, M. and Massoulié, L. (2018). An impossibility result for reconstruction in the degree-corrected stochastic block model. Ann. Appl. Probab. 28 3002-3027. · Zbl 1417.91409 · doi:10.1214/18-AAP1381 |
| [58] | Hajek, B., Wu, Y. and Xu, J. (2016a). Achieving exact cluster recovery threshold via semidefinite programming. IEEE Trans. Inf. Theory 62 2788-2797. · Zbl 1359.94222 · doi:10.1109/TIT.2016.2546280 |
| [59] | Hajek, B., Wu, Y. and Xu, J. (2016b). Achieving exact cluster recovery threshold via semidefinite programming: Extensions. IEEE Trans. Inf. Theory 62 5918-5937. · Zbl 1359.94951 · doi:10.1109/TIT.2016.2594812 |
| [60] | Hartigan, J. A. (1972). Direct clustering of a data matrix. J. Amer. Statist. Assoc. 67 123-129. |
| [61] | Herlau, T., Schmidt, M. N. and Mørup, M. (2016). Completely random measures for modelling block-structured sparse networks. In Advances in Neural Information Processing Systems 4260-4268. |
| [62] | Hoff, P. D., Raftery, A. E. and Handcock, M. S. (2002). Latent space approaches to social network analysis. J. Amer. Statist. Assoc. 97 1090-1098. · Zbl 1041.62098 · doi:10.1198/016214502388618906 |
| [63] | Holland, P. W., Laskey, K. B. and Leinhardt, S. (1983). Stochastic blockmodels: First steps. Soc. Netw. 5 109-137. · doi:10.1016/0378-8733(83)90021-7 |
| [64] | Hoover, D. N. (1979). Relations on probability spaces and arrays of random variables 2. Institute for Advanced Study, Princeton, NJ. Preprint. |
| [65] | Janson, S. (1995). Random regular graphs: Asymptotic distributions and contiguity. Combin. Probab. Comput. 4 369-405. · Zbl 0846.05076 · doi:10.1017/S0963548300001735 |
| [66] | Jin, J. (2015). Fast community detection by SCORE. Ann. Statist. 43 57-89. · Zbl 1310.62076 · doi:10.1214/14-AOS1265 |
| [67] | Jin, J., Ke, Z. T. and Luo, S. (2018). Network global testing by counting graphlets. In International Conference on Machine Learning 2338-2346. |
| [68] | Joseph, A. and Yu, B. (2016). Impact of regularization on spectral clustering. Ann. Statist. 44 1765-1791. · Zbl 1357.62229 · doi:10.1214/16-AOS1447 |
| [69] | Kallenberg, O. (1989). On the representation theorem for exchangeable arrays. J. Multivariate Anal. 30 137-154. · Zbl 0676.60046 · doi:10.1016/0047-259X(89)90092-4 |
| [70] | Karrer, B. and Newman, M. E. J. (2011). Stochastic blockmodels and community structure in networks. Phys. Rev. E (3) 83 016107, 10. |
| [71] | Klopp, O., Tsybakov, A. B. and Verzelen, N. (2017). Oracle inequalities for network models and sparse graphon estimation. Ann. Statist. 45 316-354. · Zbl 1367.62090 · doi:10.1214/16-AOS1454 |
| [72] | Klopp, O., Lu, Y., Tsybakov, A. B. and Zhou, H. H. (2019). Structured matrix estimation and completion. Bernoulli 25 3883-3911. · Zbl 1428.62281 · doi:10.3150/19-BEJ1114 |
| [73] | Le, C. M., Levina, E. and Vershynin, R. (2015). Sparse random graphs: regularization and concentration of the laplacian. Random Structures Algorithms Preprint. Available at arXiv:1502.03049. · Zbl 1373.05179 · doi:10.1002/rsa.20713 |
| [74] | Le, C. M., Levina, E. and Vershynin, R. (2017). Concentration and regularization of random graphs. Random Structures Algorithms 51 538-561. · Zbl 1373.05179 · doi:10.1002/rsa.20713 |
| [75] | Lei, J. and Rinaldo, A. (2015). Consistency of spectral clustering in stochastic block models. Ann. Statist. 43 215-237. · Zbl 1308.62041 · doi:10.1214/14-AOS1274 |
| [76] | Lloyd, J., Orbanz, P., Ghahramani, Z. and Roy, D. M. (2012). Random function priors for exchangeable arrays with applications to graphs and relational data. In Advances in Neural Information Processing Systems 998-1006. |
| [77] | Lovász, L. (2012). Large Networks and Graph Limits. American Mathematical Society Colloquium Publications 60. Amer. Math. Soc., Providence, RI. · Zbl 1292.05001 |
| [78] | Ma, Z., Ma, Z. and Yuan, H. (2020). Universal latent space model fitting for large networks with edge covariates. J. Mach. Learn. Res. 21 1-67. · Zbl 1497.68432 |
| [79] | Ma, Z. and Wu, Y. (2015a). Computational barriers in minimax submatrix detection. Ann. Statist. 43 1089-1116. · Zbl 1328.62354 · doi:10.1214/14-AOS1300 |
| [80] | Ma, Z. and Wu, Y. (2015b). Volume ratio, sparsity, and minimaxity under unitarily invariant norms. IEEE Trans. Inf. Theory 61 6939-6956. · Zbl 1359.94135 · doi:10.1109/TIT.2015.2487541 |
| [81] | Madeira, S. C. and Oliveira, A. L. (2004). Biclustering algorithms for biological data analysis: A survey. IEEE/ACM Trans. Comput. Biol. Bioinform. 1 24-45. |
| [82] | Massoulié, L. (2014). Community detection thresholds and the weak Ramanujan property. In STOC’14—Proceedings of the 2014 ACM Symposium on Theory of Computing 694-703. ACM, New York. · Zbl 1315.68210 |
| [83] | McCullagh, P. (2002). What is a statistical model? Ann. Statist. 30 1225-1310. · Zbl 1039.62003 · doi:10.1214/aos/1035844977 |
| [84] | McSherry, F. (2001). Spectral partitioning of random graphs. In 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, NV, 2001) 529-537. IEEE Computer Soc., Los Alamitos, CA. |
| [85] | Montanari, A. and Sen, S. (2016). Semidefinite programs on sparse random graphs and their application to community detection. In STOC’16—Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing 814-827. ACM, New York. · Zbl 1376.90043 |
| [86] | Mossel, E., Neeman, J. and Sly, A. (2014). Consistency thresholds for binary symmetric block models. Preprint. Available at arXiv:1407.1591. · Zbl 1321.05242 |
| [87] | Mossel, E., Neeman, J. and Sly, A. (2015). Reconstruction and estimation in the planted partition model. Probab. Theory Related Fields 162 431-461. · Zbl 1320.05113 · doi:10.1007/s00440-014-0576-6 |
| [88] | Mossel, E., Neeman, J. and Sly, A. (2018). A proof of the block model threshold conjecture. Combinatorica 38 665-708. · Zbl 1424.05272 · doi:10.1007/s00493-016-3238-8 |
| [89] | Newman, M. E. J. (2010). Networks: An Introduction. Oxford Univ. Press, Oxford. · Zbl 1195.94003 |
| [90] | Newman, M. E., Watts, D. J. and Strogatz, S. H. (2002). Random graph models of social networks. Proc. Natl. Acad. Sci. USA 99 2566-2572. · Zbl 1114.91362 · doi:10.1073/pnas.012582999 |
| [91] | Nowicki, K. and Snijders, T. A. B. (2001). Estimation and prediction for stochastic blockstructures. J. Amer. Statist. Assoc. 96 1077-1087. · Zbl 1072.62542 · doi:10.1198/016214501753208735 |
| [92] | Olhede, S. C. and Wolfe, P. J. (2014). Network histograms and universality of blockmodel approximation. Proc. Natl. Acad. Sci. USA 111 14722-14727. |
| [93] | Qin, T. and Rohe, K. (2013). Regularized spectral clustering under the degree-corrected stochastic blockmodel. In Advances in Neural Information Processing Systems 3120-3128. |
| [94] | Raskutti, G., Wainwright, M. J. and Yu, B. (2011). Minimax rates of estimation for high-dimensional linear regression over \(\ell_q\)-balls. IEEE Trans. Inf. Theory 57 6976-6994. · Zbl 1365.62276 · doi:10.1109/TIT.2011.2165799 |
| [95] | Rohe, K., Chatterjee, S. and Yu, B. (2011). Spectral clustering and the high-dimensional stochastic blockmodel. Ann. Statist. 39 1878-1915. · Zbl 1227.62042 · doi:10.1214/11-AOS887 |
| [96] | Sarkar, P. and Bickel, P. J. (2015). Role of normalization in spectral clustering for stochastic blockmodels. Ann. Statist. 43 962-990. · Zbl 1320.62150 · doi:10.1214/14-AOS1285 |
| [97] | Shi, J. and Malik, J. (2000). Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 22 888-905. |
| [98] | Todeschini, A., Miscouridou, X. and Caron, F. (2020). Exchangeable random measures for sparse and modular graphs with overlapping communities. J. R. Stat. Soc. Ser. B. Stat. Methodol. 82 487-520. · Zbl 07554763 |
| [99] | van der Hofstad, R. (2017). Random Graphs and Complex Networks. Vol. 1. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge Univ. Press, Cambridge. · Zbl 1361.05002 |
| [100] | Veitch, V. (2015). The class of random graphs arising from exchangeable random measures. Preprint. Available at arXiv:1512.03099. |
| [101] | von Luxburg, U. (2007). A tutorial on spectral clustering. Stat. Comput. 17 395-416. · doi:10.1007/s11222-007-9033-z |
| [102] | von Luxburg, U., Belkin, M. and Bousquet, O. (2008). Consistency of spectral clustering. Ann. Statist. 36 555-586. · Zbl 1133.62045 · doi:10.1214/009053607000000640 |
| [103] | Wasserman, S. and Faust, K. (1994). Social Network Analysis: Methods and Applications 8. Cambridge University Press, Cambridge. · Zbl 0926.91066 |
| [104] | Wolfe, P. J. and Olhede, S. C. (2013). Nonparametric graphon estimation. Preprint. Available at arXiv:1309.5936. |
| [105] | Xu, J. (2018). Rates of convergence of spectral methods for graphon estimation. In International Conference on Machine Learning 5433-5442. PMLR. |
| [106] | Ye, F. and Zhang, C.-H. (2010). Rate minimaxity of the Lasso and Dantzig selector for the \(\ell_q\) loss in \(\ell_r\) balls. J. Mach. Learn. Res. 11 3519-3540. · Zbl 1242.62074 |
| [107] | Yun, S.-Y. and Proutiere, A. (2014). Accurate community detection in the stochastic block model via spectral algorithms. Preprint. Available at arXiv:1412.7335. |
| [108] | Yun, S.-Y. and Proutiere, A. (2016). Optimal cluster recovery in the labeled stochastic block model. In Advances in Neural Information Processing Systems 965-973. |
| [109] | Zhang, A. Y. and Zhou, H. H. (2016). Minimax rates of community detection in stochastic block models. Ann. Statist. 44 2252-2280. · Zbl 1355.60125 · doi:10.1214/15-AOS1428 |
| [110] | Zhang, A. Y. and Zhou, H. H. (2020). Theoretical and computational guarantees of mean field variational inference for community detection. Ann. Statist. 48 2575-2598. · Zbl 1462.62221 · doi:10.1214/19-AOS1898 |
| [111] | Zhao, Y., Levina, E. and Zhu, J. (2012). Consistency of community detection in networks under degree-corrected stochastic block models. Ann. Statist. 40 2266-2292. · Zbl 1257.62095 · doi:10.1214/12-AOS1036 |
| [112] | Zhou, Z. and Amini, A. A. (2019). Analysis of spectral clustering algorithms for community detection: The general bipartite setting. J. Mach. Learn. Res. 20 Paper No. 47, 47. · Zbl 1484.62088 |
| [113] | Zhou, Z. and Li, P. (2018). Non-asymptotic chernoff lower bound and its application to community detection in stochastic block model. Preprint. Available at arXiv:1812.11269. |
| [114] | Amazon Mechanical Turk (2010). Available at https://www.mturk.com/mturk/welcome |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
