基于kNN发现社团主干的社团检测算法

摘要

随着复杂网络规模和种类的日渐增加,如何检测任意结构,任意规模的社团成为了社团检测的一个难点.为了解决该问题,提出了一种可以通过k最近邻发现社团主干的社团检测算法DCCB(detection community based on kNN to discover community backbone).该算法首先遍历所有节点,将两个互为k近邻的相似节点及它们的共同邻居聚集到一个社团主干中;接着,在遍历过程中,若不在主干中的节点与某个社团主干内任何节点存在互近邻关系,那么该节点也会被吸引到这个社团主干中;然后,该算法检测出社团主干中的异常节点,并将其标记为无类标节点;最后,该算法利用影响力分配无类标节点,得到最终的社团结构.该算法简单且时间复杂度较低.通过4个不同结构真实网络以及3个不同规模的人工合成网络的综合测试表明:DCCB算法能检测出任意结构与任意规模的社团,且发现的社团质量高于所用的5个基准算法.