在进行社交网络分析时，一个常见的问题是如何检测社区，如相互了解或者经常互动的一群人。社区其实就是连通性非常密集的图的子图。

在这篇文章中，我将列举一些寻找社区的常用算法。

首先，社区检测可以看作图分区问题。在这种情况下，单个节点将只属于一个社区。换句话说，社区之间不会相互重叠。

删除高边介数的边（High Betweenness Edge Removal）

通常来讲，社区内的成员之间联系紧密，并可以通过许多路径相互连接。另外，不同社区的节点需要跨社区连接才能相互访问，而这些跨社区连接往往具有较高的边介数。

因此，通过删除这些高边介数的边，社交图将被分成不同的社区。

算法：

1. 对于每个边，计算边介数
2. 删除最高边介数的边
3. 直到分离的区域足够

然而，尽管这种方法可以得到不错的结果，但是当节点超过两千个，并且节点之间联系紧密时，这种方法非常慢并且效率不高。

层次聚类

这是社区检测中一种非常普遍的方法。首先定义每对节点之间的距离（或相似度）的度量方式，并进行相应的计算。然后可以使用经典的层次聚类技术。应该选择能使得同一社区的成员之间的距离较小，而不同社区的成员之间的距离较大的距离度量方式。

随机游走

随机游走可以用来计算每对节点之间的距离、以及节点B（node-B）和节点C（node-C）。我们先来关注无向图。一个随机游走者从节点B开始，投掷一个骰子得到一个概率β，它根据链接的权重随机挑选一个邻居进行访问，并且它会有（1-β）的概率回到原始节点v。在无限次的访问之后，如果节点B和节点C属于相同的社区，则节点w上的着落概率分布将很高。直观上讲，随机游走者趋于被困在社区中，因此具有高概率分布的所有节点倾向于与节点B（随机游走者开始的节点）在同一社区内。

请注意，概率β大小的选择很重要。如果它太大（接近1），则收敛后的概率与起始节点无关（即：概率分布仅反映每个节点的中心性，而不反映起始节点的社区）。如果概率β太小（接近零），那么在完全探索社区的连通性之前，随机游走者会过快地停止。

这个问题有一个解析解。

定义M为每对节点之前的转换矩阵。V代表随机行走者的概率分布。

节点B与其他所有节点之间的“距离”是M的特征向量。我们可以重复相同的步骤来找出所有节点对的距离，然后将结果反馈给层次聚类算法。

标签传播

其基本思想是，统计一个节点的相邻节点的标签，并将其这个节点的标签设置为其相邻节点中数量最多的标签。

1. 开始时为每个节点分配一个唯一的标签。
2. 在每一轮中，每个节点检查其所有相邻节点的标签都将其自己的标签设置为其相邻节点中数量最多的标签，当出现两种标签数量相同的情况时，将进行随机选择。
3. 直到标签分配没有更多变化

模块度优化

在一个社区内，2个节点有链接的概率应该比链接刚好在整个图中随机形成的概率要高。

随机链接的概率= deg(node-B) * deg(node-C) / (N * (N-1))

实际链路=邻接矩阵[B, C]

定义com(B)为节点B的社区，com(C) 为节点C的社区

所以创建一个实用功能“模块度”，如下所示...

sum_over_v_w((actual - random) * delta(com(B), com(C)))

算法：

1.开始时每个节点都有自己的社区，所以Q=0因为δ(k,s)会变成0

2.合并两个在Q中获得最大值结果的社区

3.直到结果小于一个阈值

接下来我们来研究可以重叠的社区。即：单个节点可以属于多个社区。

寻找团

简单的社区检测通常从团开始。团是一个子图，每个节点是否连接到任何其他节点。在一个K团（K-Clique）中，它们之间有K个节点和K^2条边。

然而，社区的定义较为宽松，我们并不要求每个人都认识社区内的其他人，但我们需要他们认识“足够多”的（可能是一个确定的比例） 同一个社区的其他人。K核心（K-core）的定义更宽松，它要求K核心的节点至少连接了K个其他成员。还有有一些不算特别流行的宽松的限定，K宗派（K-Clan）要求每个节点在K个步骤（路径长度小于K）内连接每个其他成员。K丛（K-plex）要求节点连接到K丛（K-plex）中N个成员总数中的（N-K）个成员。

该社区被定义为发现的K核心（K-core），或K宗派（K-Clan）或K丛（K-plex）。

K-团（K-Clique）渗滤

社区检测的另一种流行方式是在邻近的K-团（K-Clique）上滚动。如果两个K-Clique共享K-1个节点，则它们相邻。我们要根据期望的社区人群密度选取K这个参数。

该算法如下图所示。

K团（K-Clique）渗透法是识别可能相互重叠的社区的流行方式。