We study the community detection problem on a Gaussian mixture model, in which (1) vertices are divided into $k\geq 2$ distinct communities that are not necessarily equally-sized; (2) the Gaussian perturbations for different entries in the observation matrix are not necessarily independent or identically distributed. We prove necessary and sufficient conditions for the exact recovery of the maximum likelihood estimation (MLE), and discuss the cases when these necessary and sufficient conditions give sharp threshold. Applications include the community detection on a graph where the Gaussian perturbations of observations on each edge is the sum of i.i.d.~Gaussian random variables on its end vertices, in which we explicitly obtain the threshold for the exact recovery of the MLE.


翻译:我们研究高斯混合模型中的社区探测问题,其中(1) 脊椎被分为不一定同等大小的2美元或2美元的独特社区;(2) 观测矩阵中不同条目的戈西亚扰动不一定独立或分布相同;我们证明准确恢复最大可能性估计(MLE)是必要和充分的条件,并讨论这些必要和充分条件能提供尖锐临界值的情况;应用包括在图表中的社区探测,其中每个边缘的观测结果的高西亚扰动是其末端脊椎上i.i.d.-Gausian随机变量的总和,我们在该图中明确获得准确恢复最低限值的临界值。

0
下载
关闭预览

相关内容

在网络中发现社区(称为社区检测/发现)是网络科学中的一个基本问题,在过去的几十年中引起了很多关注。 近年来,随着对大数据的大量研究,另一个相关但又不同的问题(称为社区搜索)旨在寻找包含查询节点的最有可能的社区,这已引起了学术界和工业界的广泛关注,它是社区检测问题的依赖查询的变体。
不可错过!《机器学习100讲》课程,UBC Mark Schmidt讲授
专知会员服务
73+阅读 · 2022年6月28日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
IEEE TII Call For Papers
CCF多媒体专委会
3+阅读 · 2022年3月24日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Latest News & Announcements of the Tutorial
中国图象图形学学会CSIG
3+阅读 · 2021年12月20日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium8
中国图象图形学学会CSIG
0+阅读 · 2021年11月16日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium7
中国图象图形学学会CSIG
0+阅读 · 2021年11月15日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium5
中国图象图形学学会CSIG
1+阅读 · 2021年11月11日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium4
中国图象图形学学会CSIG
0+阅读 · 2021年11月10日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
中国图象图形学学会CSIG
0+阅读 · 2021年11月3日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
国家自然科学基金
3+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
3+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
0+阅读 · 2022年11月4日
Arxiv
0+阅读 · 2022年11月3日
Arxiv
12+阅读 · 2019年4月9日
VIP会员
相关资讯
IEEE TII Call For Papers
CCF多媒体专委会
3+阅读 · 2022年3月24日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Latest News & Announcements of the Tutorial
中国图象图形学学会CSIG
3+阅读 · 2021年12月20日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium8
中国图象图形学学会CSIG
0+阅读 · 2021年11月16日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium7
中国图象图形学学会CSIG
0+阅读 · 2021年11月15日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium5
中国图象图形学学会CSIG
1+阅读 · 2021年11月11日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium4
中国图象图形学学会CSIG
0+阅读 · 2021年11月10日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
中国图象图形学学会CSIG
0+阅读 · 2021年11月3日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
相关基金
国家自然科学基金
3+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
3+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员