Streaming Belief Propagation for Community Detection-猫眼课题宝

DOI：

发表时间：

2021-06

期刊：

ArXiv

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

Yuchen Wu;M. Bateni;André Linhares;Filipe Almeida;A. Montanari;A. Norouzi-Fard;Jakab Tardos

社区检测问题需要将网络中的节点聚类成少量连接良好的“社区”。最近在描述简单随机块模型下社区检测的基本统计限制方面取得了实质性进展。然而，在实际应用程序中，网络结构通常是动态的，节点随着时间的推移而加入。在这种设置中，我们希望检测算法在每个节点到达时只执行有限数量的更新。虽然标准投票方法满足这一约束，但尚不清楚它们是否最优地利用了网络信息。我们引入了一个简单的网络随时间增长的模型，我们称之为流随机块模型（StSBM）。在这个模型中，我们证明了投票算法具有基本的局限性。我们还开发了一种流信念传播（StreamBP）方法，我们证明了在某些情况下的最优性。我们用合成数据和实际数据验证了我们的理论发现。

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.

Streaming Belief Propagation for Community Detection

文献摘要

相似文献