基于覆盖最优划分的社团发现算法

摘要

覆盖最优划分思想是将子集间重叠区域样本通过覆盖的合并和分割,使原来有交集的覆盖划分为无交集的类误差最小.文中将覆盖的最优划分思想引入社团发现中,提出基于覆盖最优划分的社团发现算法(CDA OPC),将社团发现问题转化为求给定覆盖的最优划分问题.首先利用节点间邻域重叠关系构造覆盖,然后运用覆盖的最优划分概念,通过覆盖子集的合并与分割达到对覆盖的最优逼近,最后计算社团间的相似度,将相似度最大的社团两两合并,在多层次合并后最终形成多粒度的社团结构.在真实网络上的实验表明,CDA OPC可以有效划分社团.