动态网络中的实时分布式社区结构检测（2012）

参考论文Real Time Distributed Community Structure Detection in Dynamic Networks
关于动态网络监测以前的方法：
（1）最初的尝试是跟踪社区，而不是在网络中检测它们。
（2）将已知的静态社区检测算法应用于从动态网络快照生成的静态图中。但是，这需要在一系列静态快照中捕获动态网络，这是很有挑战性的。例如：
这篇论文提出的算法
G:动态图
G=G0，G1，G2…GT
Gt（V,Et）
h:i记得接触过的最大数量
Hi：节点i最近接触到的h个节点
d：设d是一个参数，使得Hi中最近的联系人具有h的重要性，而最近的一个参数的重要性为max(h−d，1)，而kth最近的接触在hii中的重要性为m。AX(h−dk，1)
设p>h，使得1/p是节点通过更改社区随机重新命名更改为自己的id的概率。
tr：让TR是将通知重新标记的联系人的数量。
（1）如果在集合EI节点I主要与社区L的成员交互(共享边)，那么在这段时间内它可能是社区L的成员。
（2）如果节点i很少改变社区，那么这个人当前的社区关联很可能是未来社区联系的预测。
利用（1），（2），我们可以使用该算法只使用本地信息实时地单独估算社区成员数，算法如下：

结果：
使用了四个网络进行测试。所有网络由100个节点组成。在所有方法中，通过选择网络中的随机节点并将其连接到社区中的另一个随机节点来生成边。选择稳定参数n大于算法的预期最大收敛时间。在实验之间，在使用不同的参数时，n的值可以改变以适应更长的或更短的期望最大收敛时间。
加入这个网络说明了两个社区的加入。最初，网络被划分为两个社区，每个社区有50个节点。在每次迭代中都会产生随机接触。后n次已使这两个网络联合起来进行联系。在这个网络中，所有节点都在同一个社区中进行n次接触，然后该社区分成两个社区，每个社区有50个节点每个节点n次接触。连接此网络包含两个大小相同的社区，由一些中间节点连接。该网络对n个联系人进行了仿真。
B收敛和h
在图3中，在d=0的连接网络上运行了实验，没有重新标记，以显示h的变化对收敛时间(错误数目稳定的时间)的影响。这个图中h值越大，收敛时间越长。这种增长背后的直觉就是这样。在一个节点需要决定它在哪个社区的情况下，它可能需要最多h个联系人来决定。随着时间的延长，这个决策时间所以会变长。因此，当一个节点与它所属的社区连接时，它加入社区所需的时间更长，从而延长了收敛时间。
E:共享节点及其对社区的影响
一个例子说明了该算法区分社区的能力，这是一个例子，其中两个节点组在它们之间共享少量的节点。在图6中，我们看到一个这样的网络，共享节点的数量从4到44不等。报告的数字是所有50次模拟运行中的平均社区数。随着连接两个组的共享节点数量的增加，两个组都属于同一个社区的可能性也随之增大。

F:在random spatial network中找到社区，在这个网络中，30个节点被随机地播种在一个30x30的单位方格上。在每一次迭代中，都会在每个节点及其三个最近的邻居之间发现一条边，随后，节点以随机概率移动一个较小的距离。在h=20，d=1,p=4000,rc=20生成图上进行模拟。
（1）Relabeling Event：
（2）Community Growth and Shrinkage
结论：本文提出了一种实时分布式社区结构估计算法。它非常适合于分布式计算，其运行时以h为线性，是历史长度参数。h是可以调节的所以算法的成本可以调节。该算法在人工生成的网络上进行了仿真，并对人工社区进行了正确的估计。此外，它还在随机生成的网络上找到了一个合理的社区结构。
社区结构的准确确定取决于用户对仿真中探讨的几个关键参数h、d、p和rc的调整。h是最重要的，它影响运行时间和收敛时间。然而，适当的d值有助于提高收敛时间，而rc的正确值则可使relabel发生。
未来的工作：今后的发展可以包括允许每个节点具有多个社区附属关系。此外，该算法不允许网络的一部分经常改变社区隶属关系，而另一部分则更稳定。今后的工作包括调整h和其他在每个节点上测量以在网络的不同部分创建自定义行为