CS224W：图机器学习8

社区检测community detection

我们通常会有这样一种概念，认为一个网络结构应该长成这样：

我们发现这样的网络结构呈现出一种“大杂居小聚居”的形态，会有一些点组成小集群，同时边也可以分成long和short两种形式，比如我们用下面这样一个社交网络作为例子：

• 在这个图结构里面，人依照关系亲密进行了划分，形成了一些团簇。粗线表示的是亲密朋友关系，而细线表示的是熟人关系。
• 一项研究发现在社交网络中，人们往往更喜欢去寻求熟人而不是朋友的帮助来找工作，这就说明在这个问题中细线边比粗线边更重要，在社交网络的信息传递中起到更重要的作用。
• 因此科学家对社交网络中的各种边进行了结构和社会学双重意义上的分析，将边分成了强弱两种

Edge Overlap

edge overlap可以用来判断一条边是不是一个local bridge(即连通了两个不相交的节点集群的边)，被定义为：

%20%5Ccap%20N(j))-%5C%7Bi%2C%20j%5C%7D%20%5Cmid%7D%7B%7C(N(i)%20%5Ccup%20N(j))-%5C%7Bi%2C%20j%5C%7D%20%5Cmid%7D%0A#card=math&code=O_%7Bij%7D%3D%5Cfrac%7B%7C%28N%28i%29%20%5Ccap%20N%28j%29%29-%5C%7Bi%2C%20j%5C%7D%20%5Cmid%7D%7B%7C%28N%28i%29%20%5Ccup%20N%28j%29%29-%5C%7Bi%2C%20j%5C%7D%20%5Cmid%7D%0A&id=m5lFm)

• 如果一个edge overlap的计算结果是0，就说明这条边是local bridge

网络社区检测

网络社区(Network Community)被定义为是图结构中有较多内部连接和较少外部连接的点的集合，我们可以根据网络社群对节点进行聚类。

Modularity模块度

可以用模块性Modularity这个量来表示一个图是否被很好地被分成几个社群，可以用来检测图分割的质量，如果将图G分割成了若干个部分构成集合S，那么Modularity的计算方法可以表示为：

也就是说对于一个分割中的每一个group，计算其边的数量和应有的边的数量之差并求和。而这里需要一个null model来作为对照，我们可以对一个有n个节点m条边的图G随机生成一个度数分布与之相同的图，并且假设每个节点的度数为，则有：

两个节点i和j之间期望的边的条数是

这种计算方式在加权图和不加权的图中都可以使用，这样一来就有了计算按照期望应有的边的数量的方式，modularity的计算方式可以表示为：

%3D%5Cfrac%7B1%7D%7B2%20m%7D%20%5Csum%7Bs%20%5Cin%20S%7D%20%5Csum%7Bi%20%5Cin%20s%7D%20%5Csum%7Bj%20%5Cin%20s%7D%5Cleft(A%7Bi%20j%7D-%5Cfrac%7Bk%7Bi%7D%20k%7Bj%7D%7D%7B2%20m%7D%5Cright)%5Cin%20%5B-1%2C1%5D%0A#card=math&code=Q%28G%2C%20S%29%3D%5Cfrac%7B1%7D%7B2%20m%7D%20%5Csum%7Bs%20%5Cin%20S%7D%20%5Csum%7Bi%20%5Cin%20s%7D%20%5Csum%7Bj%20%5Cin%20s%7D%5Cleft%28A%7Bi%20j%7D-%5Cfrac%7Bk%7Bi%7D%20k%7Bj%7D%7D%7B2%20m%7D%5Cright%29%5Cin%20%5B-1%2C1%5D%0A&id=iImBI)

• 这个计算方式可以等价地表示成：

%5Cdelta%20(ci.c_j)%0A#card=math&code=Q%3D%5Cfrac%7B1%7D%7B2m%7D%5Csum%7Bij%7D%5Cleft%28A%7Bi%20j%7D-%5Cfrac%7Bk%7Bi%7D%20k_%7Bj%7D%7D%7B2%20m%7D%5Cright%29%5Cdelta%20%28c_i.c_j%29%0A&id=wR3Yw)

• 一般来说大于0.3-0.7就可以认为这是一个重要的社群结构，同时我们通过让Q最大化来寻找图中存在的社群。

社区检测算法

• 这一部分主要讲了两种社区检测算法，一种是Louvain算法，基于贪心策略，时间复杂度达到了#card=math&code=O%28N%5Clog%20N%29&id=eUWJU)，另一种是可以发现网络结构中的overlapping community的BigCLAM算法，具体的就不深入了解了。