Nonreconstruction of high-dimensional stochastic block model with bounded degree

被引：0

作者：

Zhang, Yue ^{[1
]}

Yuan, Mingao ^{[2
]}

机构：

[1] IUPUI, Dept Math, Indianapolis, IN 46204 USA

[2] North Dakota State Univ, Dept Stat, Fargo, ND 58102 USA

来源：

STATISTICS & PROBABILITY LETTERS | 2020年 / 158卷

关键词：

Community detection; Random graph; Networks; Stochastic block model; COMMUNITY DETECTION; RECONSTRUCTION;

D O I：

10.1016/j.spl.2019.108675

中图分类号：

O21 [概率论与数理统计]; C8 [统计学];

学科分类号：

020208 ; 070103 ; 0714 ;

摘要：

In this paper, we study the stochastic block model (SBM) with growing number of clusters and bounded degree. Specifically, for SBM g(sn) (n, a/n, b/n) with diverging s n blocks and fixed a and b(a > b > 0), we prove that if (a - b)(2) < b, then it is impossible to distinguish g(sn)(n, a/n, b/n) from the corresponding Erdos-Renyi model g( )(n, a+(S-n-1)(b)/nS(n)). (C) 2019 Elsevier B.V. A l rights reserved.

引用

页数：6

共 15 条

[1] Community detection and stochastic block models: Recent developments
[J]. Abbe, Emmanuel (eabbe@princeton.edu), 2018, Microtome Publishing (18)
[2] PSEUDO-LIKELIHOOD METHODS FOR COMMUNITY DETECTION IN LARGE SPARSE NETWORKS
Amini, Arash A.
Chen, Aiyou
Bickel, Peter J.
Levina, Elizaveta
[J]. ANNALS OF STATISTICS, 2013, 41 (04) : 2097 - 2122
[3] Angelini MC, 2015, ANN ALLERTON CONF, P66, DOI 10.1109/ALLERTON.2015.7446987
[4] Hypothesis testing for automated community detection in networks
Bickel, Peter J.
Sarkar, Purnamrita
[J]. JOURNAL OF THE ROYAL STATISTICAL SOCIETY SERIES B-STATISTICAL METHODOLOGY, 2016, 78 (01) : 253 - 273
[5] Detecting functional modules in the yeast protein-protein interaction network
Chen, Jingchun
Yuan, Bo
[J]. BIOINFORMATICS, 2006, 22 (18) : 2283 - 2290
[6] Knockdown of SALL4 inhibits the proliferation and reverses the resistance of MCF-7/ADR cells to doxorubicin hydrochloride
Chen, Yuan-Yuan
Li, Zhi-Zhen
Ye, Yuan-Yuan
Xu, Feng
Niu, Rui-Jie
Zhang, Hong-Chen
Zhang, Yi-Jian
Liu, Ying-Bin
Han, Bao-San
[J]. BMC MOLECULAR BIOLOGY, 2016, 17
[7] Stochastic blockmodels with a growing number of classes
Choi, D. S.
Wolfe, P. J.
Airoldi, E. M.
[J]. BIOMETRIKA, 2012, 99 (02) : 273 - 284
[8] AN IMPOSSIBILITY RESULT FOR RECONSTRUCTION IN THE DEGREE-CORRECTED STOCHASTIC BLOCK MODEL
Gulikers, Lennart
Lelarge, Marc
Massoulie, Laurent
[J]. ANNALS OF APPLIED PROBABILITY, 2018, 28 (05) : 3002 - 3027
[9] Janson S., 1995, COMBINAT PROB COMPUT, V4, P369, DOI 10.1017/S0963548300001735
[10] Reconstruction and estimation in the planted partition model
Mossel, Elchanan
Neeman, Joe
Sly, Allan
[J]. PROBABILITY THEORY AND RELATED FIELDS, 2015, 162 (3-4) : 431 - 461

← 1 2 →