新闻资讯
看你所看,想你所想

派系过滤算法

派系过滤算法

派系过滤算法

CPM算法是最早的重叠社区发现算法,它的思想是基于团渗透理论的。算法在二分图、有向图及加权图中均已有所套用。CFinder是G.Palla等基于CPM算法开发的一个自由软体,它不仅能非常有效地定位和可视化处理大规模稀疏网路社群,而且还可用于定量描述社会网路的演变。

基本介绍

  • 中文名:派系过滤算法
  • 外文名:CPM
  • 时间:2005
算法原理:
派系过滤算法(cliquepercolationmethod,CPM)认为社区是具有共享节点的全连通子图集合,并通过一种团过滤算法来识别网路中的社区结构。算法首先搜寻所有具有k个节点的完全子图,而后建立以k-clique为节点的新图,在该图中如果两个k-clique有(k-1)个公共节点则在新图中为代表他们的节点间建立一条边。最终在新图中,每个连通子图即为一个社团。
算法主要步骤:
1)找到网路中的所有团,构造一个团团重叠矩阵,矩阵是对称的,矩阵的第i行第j列即ccom[i][j]表示第i个团和第j个团的公共节点数。
2)给定参数k,将团团矩阵中非对角线上元素小于k-1,且对角线上元素小于k的所有项置0,其他的元素为1;这样,所有对角线为1的团为k团,而非对角线为1的团i、团j是相邻的。通过这个矩阵可以得到相应的社区。
注意:
由于k是个输入参数值,从而k的取值将会影响CPM算法的最终社区发现结果,当k取值越小社区将会越大,且社区结构为稀疏。但是实验证明k的取值影响不是很大,一般值为4到6。然而,由于该算法是基于完全子图,因此比较适用于完全子图比较多的网路,即边密集的网路,对于稀疏网路效率将会很低,且该算法还无法分配完全子图外的顶点。

相关推荐

声明:此文信息来源于网络,登载此文只为提供信息参考,并不用于任何商业目的。如有侵权,请及时联系我们:yongganaa@126.com