图 书 馆
随机图上社区检测的计算下界Computational Lower Bounds for Community Detection on Random Graphs |
|
| 课程网址: | https://videolectures.net/videos/colt2015_hajek_random_graphs |
| 主讲教师: | Bruce Hajek |
| 开课单位: | 信息不详。欢迎您在右侧留言补充。 |
| 开课时间: | 2015-08-20 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | This paper studies the problem of detecting the presence of a small dense community planted in a large Erd\H{o}s-R\'enyi random graph $\calG(N,q)$, where the edge probability within the community exceeds $q$ by a constant factor. Assuming the hardness of the planted clique detection problem, we show that the computational complexity of detecting the community exhibits the following phase transition phenomenon: As the graph size $N$ grows and the graph becomes sparser according to $q=N^{-\alpha}$,there exists a critical value of $\alpha = \frac{2}{3}$, below which there exists a computationally intensive procedure that can detect far smaller communities than any computationally efficient procedure, and above which a linear-time procedure is statistically optimal. The results also lead to the average-case hardness results for recovering the dense community and approximating the densest $K$-subgraph. |
| 关 键 词: | 密集群落：检测问题; 复杂度 |
| 课程来源: | 视频讲座网 |
| 数据采集: | 2025-04-07：zsp |
| 最后编审: | 2025-04-07：zsp |
| 阅读次数: | 7 |