[科普中国]-派系过滤算法

算法原理1：

派系过滤算法2（cliquepercolationmethod，CPM）认为社区是具有共享节点的全连通子图集合，并通过一种团过滤算法来识别网络中的社区结构。算法首先搜索所有具有k个节点的完全子图，而后建立以k-clique为节点的新图，在该图中如果两个k-clique有(k-1)个公共节点则在新图中为代表他们的节点间建立一条边。最终在新图中，每个连通子图即为一个社团。

算法主要步骤3：

1）找到网络中的所有团，构造一个团团重叠矩阵,矩阵是对称的，矩阵的第i行第j列即ccom[i][j]表示第i个团和第j个团的公共节点数。

2）给定参数k，将团团矩阵中非对角线上元素小于k-1，且对角线上元素小于k的所有项置0，其他的元素为1；这样，所有对角线为1的团为k团，而非对角线为1的团i、团j是相邻的。通过这个矩阵可以得到相应的社区。

注意4：

由于k是个输入参数值，从而k的取值将会影响CPM算法的最终社区发现结果，当k取值越小社区将会越大，且社区结构为稀疏。但是实验证明k的取值影响不是很大，一般值为4到6。然而，由于该算法是基于完全子图，因此比较适用于完全子图比较多的网络，即边密集的网络，对于稀疏网络效率将会很低，且该算法还无法分配完全子图外的顶点。