The community detection problem requires to cluster the nodes of a network into a small number of well-connected "communities". There has been substantial recent progress in characterizing the fundamental statistical limits of community detection under simple stochastic block models. However, in real-world applications, the network structure is typically dynamic, with nodes that join over time. In this setting, we would like a detection algorithm to perform only a limited number of updates at each node arrival. While standard voting approaches satisfy this constraint, it is unclear whether they exploit the network information optimally. We introduce a simple model for networks growing over time which we refer to as streaming stochastic block model (StSBM). Within this model, we prove that voting algorithms have fundamental limitations. We also develop a streaming belief-propagation (StreamBP) approach, for which we prove optimality in certain regimes. We validate our theoretical findings on synthetic and real data.


翻译:社区检测问题要求将网络的节点分组成少数连接良好的“社区” 。 最近,在简单随机区块模型下社区检测的基本统计限制特征的定性方面取得了显著进展。 但是,在现实世界应用中,网络结构通常是动态的,结点会随着时间推移而相联。 在这种环境下,我们希望检测算法只在每个节点到达时只进行数量有限的更新。虽然标准投票方法满足了这一限制,但不清楚它们是否最佳地利用网络信息。我们为不断增长的网络引入了一个简单的模型,我们称之为流动随机区块模型(StSBM )。在这个模型中,我们证明投票算法具有根本性的局限性。我们还开发了一种流动的信仰-调整(StreamBP)方法,我们证明在某些制度中是最佳的。我们验证了关于合成和真实数据的理论结论。

0
下载
关闭预览

相关内容

在网络中发现社区(称为社区检测/发现)是网络科学中的一个基本问题,在过去的几十年中引起了很多关注。 近年来,随着对大数据的大量研究,另一个相关但又不同的问题(称为社区搜索)旨在寻找包含查询节点的最有可能的社区,这已引起了学术界和工业界的广泛关注,它是社区检测问题的依赖查询的变体。
专知会员服务
50+阅读 · 2020年12月14日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
78+阅读 · 2020年7月26日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
ResNet, AlexNet, VGG, Inception:各种卷积网络架构的理解
全球人工智能
19+阅读 · 2017年12月17日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Arxiv
24+阅读 · 2020年3月11日
Arxiv
14+阅读 · 2019年9月11日
Arxiv
3+阅读 · 2018年3月28日
VIP会员
Top
微信扫码咨询专知VIP会员