社区检测算法总结

社区检测算法
April 26, 2019
1 社区检测
先来说说什么是社区发现吧，学术上的说法是：一个社区由一组连接紧密的结点组成，
同时这些结点与社区外部的结点连接稀疏，如下图所示。那么，社区发现就是在复杂网络中
发现这些连接紧密的社区结构。其实，我个人觉得，社区发现就是网络中的节点聚类

2 社区检测与聚类的区别
社团检测通常是指将网络中联系紧密的部分找出来，这些部分就称之为社团，那么也可
以认为社团内部联系稠密，而社团之间联系稀疏 。显而易见，其中有一个非常重要的点，
稠密是如何定义的。不管现在想到的定义是什么，但都包含顶点，边，度，或许还有路径这
些字眼，它们有一个共同的特征–网络的结构。所以，社团检测侧重于找到网络中联系紧密
的部分，而经常忽略节点的属性（attributes）。
聚类，顾名思义是将属于同一类的目标聚在一起，通常在聚类之前我们是不知道目标
有哪些类型，这也是一种典型的无监督学习方法。那么现在来想想我们熟知的聚类方法：kmeans，层次聚类等。其中，最核心的一个部分是计算两个目标之间的距离（或者称为相似
度），距离近则它俩是一类，距离远，那就自成一派，或者去找其它距离近的。当然，距离
近只是其中一种方法，还有距离远或者怎么样，就看自己的判断。判断标准不是讨论的重点，
重点是如何计算距离。欧式距离，曼哈顿距离，余弦相似度等，都是直接用目标特征构成的
向量来计算的，没有考虑目标的边，度。所以，聚类侧重于找到一堆属性相似的目标，从而
忽略了目标与目标之间的联系。
两者之间的关系已经很清楚啦，社团检测和聚类存在区别，但是呢，两者又是可以结合
起来的。比如，我们现在有一个网络，只知道顶点和边的情况，顶点的属性是未知的。那么在
做社团检测的时候，可以将顶点与顶点之间的关系构成一个邻接矩阵，通过一系列变化或者
就这个邻接矩阵而言，将每个行看作一个属性，每个列看作目标，就可以很轻松的转为聚类，
用聚类的方法求解。当邻接矩阵高维时，还可以先做降维处理。所以，两者并没有完全独立，
只是考虑的角度不同，可以结合使用。现在社交网络方向有一个很热门的就是用 attributes
来辅助进行社团检测，是对传统的社团检测和聚类方法的一种改进，两者优势互补。
3 图划分
图划分主要是一分为二的划分方法，代表算法是：K-L 算法和谱二分法
3.1 K-L 算法
3.2 谱二分法
3.3 GN 算法（2002 年）
由定义可知，如果一条边连接两个社区，那么这两个社团节点之间的最短路径通过该边
的次数就会最多，相应的边介数最大。如果删除该边，那么两个社团就会分割开。GN 算就
就是基于此思想反复计算当前网络的最短路径，计算每条边的边介数，删除边介数最大的边。
最后在一定条件下，算法停止，即可得到网络的社区结构。

GN 算法的执行流程。1. 使用最短路径算法求在图 1.a 上求出顶点 1 到顶点 8 的最短路
径（图中红色部分）。2. 反复调用步骤 1，探测网络所有顶点之间的最短路径，统计出所有边