内容简介
本文主要介绍CS224W的第四课，图的社区结构。
CS224W Lecture 4: Community Structure in Networks
上图为CS224W第四讲的内容框架，如下链接为第四讲的课程讲义
1 Introduction
上一讲主要介绍图的模块和结构性角色，如下图，在引入角色的时候，将角色和社区放在一起做比对，角色是网络中具有相似功能的一组节点，重在相似性；社区是相互连接的一组节点，重在连接性。本章便主要探讨网络中的社区（Community）。
我们再看课程里是如何详细的引入社区的。
首先引入概念 信息流（Information Flow）：信息在网络中如何流通。 Granovetter教授通过“人们怎么通过社交网络获取求职信息”来研究信息在网络中的流通，人们通常通过熟人获取自己想知道的信息，但不会向自己最亲密的朋友那里去获取信息。 Granovetter从两个角度来定义人们之间的友谊： 1）Structural（结构性）：Friendships span different parts of the network. （友谊会扩展到网络的不同部分） 2）Interpersonal（人际交往）：Friendship between two people is either strong or weak. (朋友间的友谊有强有弱) 对于不同社会角色/结构性角色之间的关系，Granovetter也提供了两个角度： 1）Structural（结构性）：处于同一结构性角色下的社交关系很强（学生和学生的关系），跨越网络不同结构的社交关系相对很弱（学生和教职工的关系）。 2）Information（获取信息）：跨越网络不同结构去收集信息，更容易获得一份工作（学生向教职工求助），同一结构性角色下的成员间信息相对冗余（学生们能够了解到的招聘信息大多是类似的） 即更广的关系可以帮助我们获取不同的、新的信息；而关系亲密的人会形成一个圈子，大家获取信息的来源是类似的，获取到的信息是相对冗余的。这种现象也被称为三角闭合（Triadic Closure = High clustering coefficient）。
关于关系强弱的度量，我们引入一个新的概念edge overlap
关于Edge overlap的计算公式如下，连接节点
和节点
的edge overlap为，节点
的邻居节点与节点
的邻居节点的交集大小，除以其并集大小。
将图中的边按照edges overlap的大小，红色为从小到大删除，黑色为从大到小删除后，图的最大连通分量随着删除边个数的变化如下图所示。
2 Network Community
上一部分简单引入了社区概念，本部分则详细介绍网络社区。什么是社区？
社区（Community）是内部具有大量连接，而到网络其他部分连接很小的节点集合。 Sets of nodes with lots of internal connections and few external ones (to the rest of the net work).
怎么发现网络中的社区呢？
引入参数模块度（Modularity Q）：用来衡量网络社区划分的合理程度。 给定一组网络的社区划分
，对于每个分组
来说，组内edges的数量与预期数量的差异，可以用模块度来衡量。如果这个差值很大，说明这是个很凝聚的团体。
衡量模块度的关键变成寻找计算预期edges的模型。 给定一个包含
个节点，
条边的真实网络
，并基于
重新随机构造新的网络
。与上一章节中随机构造新网络的手段类似。 基于随机构造，我们可知在随机图中，度为
的节点
和度为
的节点
，这两个节点之间存在的边，可由公式计算：
重新构造的网络
，边的条数为：
由此模块度Modularity Q可由如下公式进行计算：
有上述公式可知，模块度Modularity Q也等价于
, 当节点
和节点
同属一个社区时
，否则
。 通常来说，Q越大，网络结构的社区划分效果越好。目前我们已经能够通过模块度来判断社区划分是否可以，那么怎么找到这些社区呢？
3 Louvain algorithm
Louvain社区发现算法，是一种用来划分社区的贪心算法。
Louvain算法包括两个阶段： 1）首先将每个节点都看成一个独立的社区，计算每个节点加入其它社区时的模块度增益
，并将该节点加入到模块度提升最大的社区内，遍历网络中的节点，直到所有节点的社区都不再变化； 2）将每一个社区看成超节点（super node）重新构造网络，超节点之间的边权重，为两个社区之间的所有权重之和。 迭代步骤一和步骤二，直至稳定。 模块度增益
的计算
为社区C内的权重和
为社区C内所有节点的权重和，包含节点在社区内的连接和节点与社区外的连接
为节点
和社区C连接的权重和
为节点
所有连接的权重和 假设节点
原本在社区
，在计算节点
的增益时，还需要计算
的增益。 最终有
。 公式的详细原理如下图。
4 Detecting Overlapping Communities: BigCLAM
Lovain社区发现算法适用于不重叠的社区发现，而我们生活中许多社区都是有重叠的，此时就需要BigCLAM重叠社区发现算法。如下图所示，从邻接矩阵也可以看出重叠社区。
BigCLAM算法过程包含两步
1）基于节点的社区关系，定义一个图的生成模型，比如Community Affiliation Graph Model（AGM）算法； 2）给定一个真实的图，希望AGM算法生成的图尽可能地贴合真实图。
AGM算法生成图的过程
如下图所示，首先给定一组参数
其中
代表节点的个数，
代表社区的个数，
代表成员间的关系，
代表社区
内的节点之间生成边的概率。 如左下图，蓝色和红色部分来自于同一个社区，红色和绿色部分也来自于同一个社区。 当两个节点
和
来自于社区 A时，节点之间有概率
相连（蓝色内部以及蓝色与红色），此时
。 当两个节点
和
分别来自于社区 A和社区B，没有交集时（蓝色与绿色节点），此时
。 当两个节点
和
既来自于社区 A，也来自于社区B时（红色节点与红色节点），此时
基于生成过程，可从预设的社区结构生成随机网络。
上述是从社区结构生成网络的过程，而社区发现是从网络中发现社区结构，即上述AGM生成模型的逆过程。我们已知了网络
，需要找到最为合适的那个二分图模型
，并且得到相关参数。
思想：已知网络
，寻找模型
，使得在模型
的基础之上，
的生成概率最大（类似于极大似然估计）。 如下图所示，解决这个问题，我们需要快速计算生成概率
，并使用梯度下降来优化
的参数。 梯度下降的目标函数如下：
BigCLAM模型的思想也大致相同。只是在节点
和节点
间有边的概率
以及目标函数存在些许差异。BigCLAM模型的设计，可参见下图，梯度下降的方向，则可参见下下图。
BigCLAM的P(u, v)和目标函数
梯度下降与优化
