简单谱聚类算法在稀疏二部网络中实现精确社区恢复，还能搞定度异质性！
Exact Community Recovery in Bipartite Networks
📖 AI 总结
这篇论文研究二分网络中的精确社区恢复问题。与普通单部图不同，二分网络包含两类节点且边仅跨类型连接，因此需要同时估计两类节点上的潜在标签。作者在随机协同块模型框架下，证明了基于对角删除Gram矩阵的简单谱聚类算法，在稀疏性、社区平衡性和聚类数目满足温和条件时，能够以高概率实现精确恢复。研究进一步将该结果推广到度修正随机协同块模型，其中每个节点带有自身的度异质性参数，并证明对同一算法进行行归一化后仍保持精确恢复保证。大量实验验证了理论发现。该工作为二分网络社区检测提供了更广泛的理论支撑，尤其在社区数量增长、社区规模不平衡和度分布异质等此前理论保证有限的场景下具有意义。
🔑 关键词速览
| 二部网络 | 由两种不同类型节点组成的网络，边只存在于不同类型节点之间。 |
| 随机协同块模型 | 一种用于二部网络的概率生成模型，假设节点属于不同社区，边以社区相关的概率跨类型连接。 |
| 精确社区恢复 | 算法能够以高概率完全正确地识别所有节点的社区标签。 |
| 对角删除Gram矩阵 | 一种去除对角线元素的节点相似度矩阵，常用于谱聚类中以减少噪声影响。 |
| 度校正随机协同块模型 | 随机协同块模型的扩展，允许每个节点具有自己的度异质性参数，以更好地拟合实际网络。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅