CS224w图机器学习（三）：Community Structure

内容简介

本文主要介绍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)和目标函数

梯度下降与优化