Local Algorithms for Block Models with Side Information
作者： Elchanan Mossel , Jiaming Xu
DOI:
关键词: Block (permutation group theory) 、 Discrete mathematics 、 Combinatorics 、 Mathematics 、 Vertex (geometry) 、 Algorithm 、 Partition problem 、 Stochastic block model 、 Local algorithm 、 Random graph 、 Degree (graph theory) 、 Belief propagation
摘要: There has been a recent interest in understanding the power of local algorithms for optimization and inference problems on sparse graphs. Gamarnik and Sudan (2014) …
arxiv.org
acm.org参考文章(42)
Alexandre Proutière, Se-Young Yun, Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms. arXiv: Social and Information Networks. ,(2014)
Mustazee Rahman, Bálint Virág, Local algorithms for independent sets are half-optimal arXiv: Probability. ,(2014) , 10.1214/16-AOP1094
Tom Richardson, Ruediger Urbanke, Modern Coding Theory Cambridge University Press. ,(2008) , 10.1017/CBO9780511791338
Afonso S. Bandeira, Emmanuel Abbe, Georgina Hall, Exact Recovery in the Stochastic Block Model arXiv: Social and Information Networks. ,(2014)
Afonso S. Bandeira, Random Laplacian matrices and convex relaxations arXiv: Probability. ,(2015)
F. McSherry, Spectral partitioning of random graphs international conference on cluster computing. pp. 529- 537 ,(2001) , 10.1109/SFCS.2001.959929
T. Tony Cai, Xiaodong Li, Robust and computationally feasible community detection in the presence of arbitrary outlier nodes arXiv: Statistics Theory. ,(2014) , 10.1214/14-AOS1290
Emmanuel Abbe, Colin Sandon, Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms arXiv: Probability. ,(2015)
Yihong Wu, Jiaming Xu, Bruce Hajek, Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions arXiv: Machine Learning. ,(2015)
Aurelien Decelle, Florent Krzakala, Cristopher Moore, Lenka Zdeborová, Inference and phase transitions in the detection of modules in sparse networks. Physical Review Letters. ,vol. 107, pp. 065701- 065701 ,(2011) , 10.1103/PHYSREVLETT.107.065701