CS224W-图神经网络笔记4.3：Community Structure in Networks - 网络中重叠社区的挖掘——BigCLAM 算法

本文总结之日CS224W Winter 2021只更新到了第四节，所以下文会参考2021年课程的PPT并结合2019年秋季课程进行总结以求内容完整
课程主页： CS224W: Machine Learning with Graphs
视频链接：【斯坦福】CS224W：图机器学习( 中英字幕 | 2019秋)

[toc]

上面介绍了非重叠社区挖掘的Louvin算法，本节聊聊重叠社区的挖掘过程。两类社区区别可以反映在邻接矩阵上。

通过前面的介绍，基于图生成模型，可以生成一个网络。 相反的基于一个网络，能否确定一个图生成模型。并且模型自动划分节点的社区结构。

听起来好像想的过分美好，但实际上是真实可行的。而这个特殊的图生成模型就是 AGM模型（Community-Affiliation Graph Model）。

整个算法步骤分为三步

利用AGM(Community Affiliation Graph Model)构造一个图生成模型。

根据我们实际的图G，迭代AGM的模型参数，寻找一个最优拟合（fitting）实际图的AGM。

通过这个AGM，确定每个节点所属的社区

模型是一个二部图结构。用表示.四个参数含义如下：

社区 A 内部的每对节点相连的概率为

p_c

.每个社区对应一个。

两个社区重叠的部分越多，则重叠区域的节点彼此相连的概率越高

对于彼此之间没有共同社区的两个节点之间的连接概率并不为0，而为𝑷(𝒖,𝒗)=𝜺，叫做


           背景社区

称为

\varepsilon - community

。论文中建议

(\varepsilon = 2|E|/(|V|(|V|-1)))

虽然，AMG模型是在重叠社区挖掘的时候引入的，但并不意味着AMG模型只能生成有重叠社区的网络。事实上，其非常灵活，可以生成不同类型的社区结构。如

通过最终的AGM模型可以很容易得到最终的社区结构。

本算法是老师在2014年提出的算法（原论文为参考资料3）， 其时间复杂度低，可以运用于大型网络数据。 另外一提，cs224w 每年老师讲的内容的详细程度不尽相同，建议大家结合起来一起看。

CS224W-图神经网络 笔记4.3：Community Structure in Networks - 网络中重叠社区的挖掘——BigCLAM 算法