笔记（4）——Analyzing Communities and Their Evolutions in Dynamic Social Networks

摘要：
提出一个新方法，与传统的两步方法相区别。

我们提出FaceNet来分析社区和它们的演化通过一个强大的统一过程。我们的方法是对问题采用MAP估计，社区结构的估计同时考虑观察到的网络数据和由历史社区结构提供的先验分布。


关于动态网络的研究情况……，它们共同的缺点是：（1）社区和它们的演化是分开来研究的。通常，社区结构独立的用连续的时间步来提取，然后演化的属性用来解释随着时间的变化社区之间的区别。当社区结构是清楚的时候（例如：社区中联系是可用的）两步的方法是有意义的。但是，现实中的数据都是模糊的，而且含有大量的噪声。我们提出的是在同一个框架中分析社区和它们的演化。（2）个人通常划归到一个单独的社区中，我们认为比如一个博客作者他可能是一个专业的舞蹈者也可能是个业余的歌唱爱好者，所以我们提出的是软社区，即个人可以同时属于不同的社区。

我们的贡献是：（1）我们用FacetNet框架来统一的分析社区和他们的演化。在我们的框架中，在给定的时间点T的社区结构由在时间点T观察到的网络数据和由历史社区结构的先验分布同时决定。算法上，我们提出了第一概率生成模型来分析社区和他们的演化。我们表明，该模型可以从概率（贝叶斯）的角度解决进化的聚类问题。发现的社区和它们的演化对噪声更鲁棒，并且更合理。（2）我们采用一种随机块体模型来产生社区和一种基于狄利克莱分布（Dirichlet distribution）的概率模型来抓取社区演化。这些概率模型自然的分配软社区成员给节点，并且这些模型不具有非参数可辨识这个缺点，这是大多数模型都具有的缺点。基于由模型计算出的概率分布，我们进一步提出两种新颖的概念——社区网络和演化网络——分别用来解释社区级别的交互和过渡。（3）我们提供了迭代的EM算法，这可以用来保证收敛到拟定的最佳解决方案。我们证明了算法的正确性和收敛性，并且表明当数据稀疏的时候，算法具有低时间复杂度。我们还提供了一个实际问题原则上的解决方法，比如怎么样决定社区的个数和怎么样在动态的网络中把握增加和去除个体。
论文结构：第2部分,详细介绍我们的模型。第3部分，描述了怎么样抽取社区和他们的演化从我们的概率模型的。第4部分，我们提出了迭代的EM算法来解决我们的模型和讨论时间复杂度。第5部分，我们介绍了我们框架的扩展部分来解决实际的问题。第6部分，我们提供了实验的数据。最后第7部分，我们给出了结论和未来的方向。
--------------------------------未完待续--------------------------------