社区发现问题的目的是将网络中的节点划分为连接紧密的社区。最近，有许多工作针对随机块模型中的社区发现问题展开研究。然而，在实际应用中，网络数据通常不是静态的：随着时间推移，节点可能不断的加入网络。比如，在社交网络中不断的有新用户加入；在蛋白质交互网络中，不断有新的蛋白质被发现。为了解决这个问题，我们引入了基于随机块模型的流动随机块模型来模拟这类问题。在算法方面，我们设计了流动置信度传播算法。我们从理论方面证明了流动置信度传播算法的最优性。该算法在多个数据集上均取得了优秀的表现。

本期AI TIME PhD直播间，我们邀请到斯坦福大学在读博士生——吴雨晨，为我们带来报告分享《动态图上的置信度传播算法》。

吴雨晨：斯坦福大学在读博士生。本科毕业于清华大学数学科学系。她的研究方向包括高维统计，MCMC抽样，社区发现，迁移学习。相关研究成果发表在Neurips, COLT 国际会议。

Community detection社区发现

Data: G = (V, E).

上图中的社区对应的是节点的划分，通常来说处在同一社区的两个节点有着更大概率相连。给定一个graph G，我们的目标是估计每个节点所处的社区（community）。

社区发现在现实生活中也有着很多应用，比如在社交网络中有着相同兴趣或者好友的两人更有可能来自同一社区。生物蛋白质网络中，被聚合到同一社区的蛋白质往往具有相似的生物学功能。

然而，在过去研究社区发现时通常都是是基于静态的，而非动态的网络。

Dynamic networks

在很多应用问题中，图结构是会随着时间的变化而发生改变。

比如在社交网络中，不时会有新用户加入社交网络；而蛋白质网络中也总会有新的蛋白质被发现。我们感兴趣的是网络节点数据比较大的情况。希望为其设计一些有效且高速的算法来解决。

社区发现问题。我们针对这个问题提出下面的流动置信度传播算法（streaming local algorithm）每当图发生变化，算法只调查发生变化部位的一个常数半径的邻域。我们对如下问题感兴趣：

Understand the fundamental statistical limitsDesign efficient streaming local algorithms

本次研究的目的是探索在什么情况下，streaming local algorithm可以求解社区发现问题并且同时设计一些比较好的算法来达到最优准确度。

我们首先提出一个模型：

Local streaming algorithm

举个例子，假如我们要研究的是one Local streaming algorithm。

在时刻1揭露的点a所能接触到的子图为其本身.

在时刻2我们揭露点b，b和a相连，我们所以更新a和b能够接触到的子图。

在时刻3我们揭露点c，c只与b相连，我们只更新c和b能够接触到的子图。

在时刻4我们揭露点d，d只与a相连，did们只更新a和d能够接触到的子图。

Fundamental limit of local streaming algorithm

Belief propagation

我们接下来考虑side information存在的情况, 即要求α<k (k-1)。在此假设下，我们设计了一个Streaming belief propagation算法。

首先我们介绍一下Belief propagation置信度传播算法。

该算法的一个基本形式就是信息的传播，如上图所示。从节点A的方向传来一个信息m1，从节点B的方向传来一个信息m2，从节点C的方向传来一个信息m3，节点D会通过Belief propagation算法综合输入的信息计算得到一个output message并传播到下一个节点。我们来看下面这个例子帮助理解。

比如说，我们的任务是要计算上图中小人的数量，然后某个小人说在自己方向上有7个人，另一个小人说在自己方向上有3个人，另外一个小人综合7和3这两个数字并加上自己得出11这个数字传递给下个人。该算法也会跟随问题变化而变化。

Streaming belief propagation

假设在某个时刻t，第一个节点被揭露，那么我们算法的第一步是向所有和新被揭露的节点相连的节点进行信息传递。

之后，这个新被揭露的节点会综合所有它所接收到的信息，然后反过来和所有与该节点直接相连的点进行信息传递。

随之是这些接收到信息传递的节点向其他与之直接相连的节点发出信息传递，不过不会反向再次传递。

如此重复R轮，这就是R local 的Streaming belief propagation在这个时刻t会做的事情。

我们随后提出一个定理，即Streaming belief propagation在某些条件下可以达到最优的estimation accuracy，C是一个absolute constant，我们假设community的个数是2。如果以下三个条件中任何一个成立，那么对于足够大的R（即算法半径），Streaming belief propagation是可以达到最优estimation accuracy的。

Simulation

提醒

论文题目：

Streaming Belief Propagation for Community Detection

论文链接：