社区的直接发现

通过寻找有很多连边的节点子集直接发现社区的技术。

相关概念

1. 团（clique）：任意两个节点之间都存在边的节点子集。
2. 二部图（bipartite graph）：是由左右两个节点集合组成的图，每条边连接的都是左集合的一个节点和右集合中的一个节点。例子如下：
   
3. 完全二部图（complete bipartite graph）：二部图的两部分任意一对节点之间都有边。团是一般图的子图，完全二部图是一般二部图的子图，有时也称二部团。
4. 刚刚

利用完全二部图发现社区

随机将节点分到两个相等的组中，如果存在某个社区，可以期望该社区的一半节点属于上述的组中，而一半的边存在于两个组之间。因此可以：

1. 识别社区中较大的完全二部图（可以看成频繁项集的查找问题）；
2. 以子图为核心，对于两个组中的任意节点，如果和已经属于社区的节点间存在多条边，那就可以将它加入社区。

图划分

利用矩阵理论中的谱方法来建立图划分问题，使得不同分支之间的边或者称为“割（cut）”的数目最少。

图划分的好坏标准

• 最小割：使得连接两个集合的边（或割）数最少；
• 最优割：对“割”的选择有所限制，使得划分的两个集合的大小大致相等。

注意：最小割不一定是最优割。

归一化割

衡量割本身的大小和割导致的不同聚合大小的差异。

假定将途中节点划分成两个不相交的集合S和T，并令Cut(S,T)为连接S中节点和T中节点的边的数目，定义及诶单集合S的容量（volume）为至少一个端点在S中的边数的数目，记为Vol(S)，则S和T的归一化割为：

描述图的一些矩阵

• 邻接矩阵（adjacency matrix）：如果节点i和j之间有边，则矩阵的第i行、第j列的元素为1，否则为0；记作A。
• 度数矩阵（degree matrix）：该矩阵是个对角矩阵，第i行、第i列的元素给出的是第i个节点的度数（连接该点的边数）；记作D。
• 拉普拉斯矩阵（laplacian matrix）：定义为L=D−A，即度数矩阵和邻接矩阵的差矩阵，也就是说拉普拉斯矩阵L和度数矩阵D的对角线元素相同，而对角线之外，如果节点i和j之间有边，则L中i行、第i列的元素为−1，否则为0。其中矩阵的每行或每列之和为0，且为对称矩阵（即第i行、第j列的元素等于第j行、第i列的元素）。

拉普拉斯矩阵的特征值：

1. 对于任意的拉普拉斯矩阵，其最小的特征值都为0，其对应特征向量是[1,1,...,1]。
2. 寻找其第二小特征值，即举证L的第二小特征值为函数xTLx在如下约束条件下的最小值，其中x=[x1,x2,...,xn]是有n个元素的列向量。
   
   1. 向量x的大小为1，即sumni=1x2i=1;
   2. 向量x与最小特征值对应的特征向量正交。

利用拉普拉斯矩阵的特征值进行图划分

1. 计算对应图的拉普拉斯矩阵；
2. 求出拉普拉斯矩阵的第二小特征值及其对应矩阵；
3. 将向量x中正值节点划分到一组，而负值节点划分到另一组，从而得到图的一个划分。（这里也可以设置非零阈值）

结果：这种做法不能保证得到大小相等的节点子集，但是这些集合的大小可能会比较接近。