一种基于加权共同邻居相似度的局部社区发现算法

传统的社区发现算法能够找出网络中所有的社区,其时间复杂度取决于网络的规模.挖掘大网络中的全局社区结构因为时间复杂度高而难以实现,局部社区发现作为一种不需要知道网络的整体结构,从给定的节点逐步向外扩展,寻找该节点所在社区的方法,在大网络时代具有重要的应用意义.目前这方面的研究已经获得广泛关注,并提出了很多局部社区发现算法.针对已有局部社区发现算法需要人工设置参数、准确率低的问题,提出一种新的局部社区发现算法.首先,提出一种加权邻居节点的共同邻居相似度指标,用于计算网络中两个节点间的相似度;然后,基于该相似度指标,给出一种新的局部社区质量度量指标,在保证社区度量指标不下降的前提下,不断选择与当前局部社区嵌入度最大的节点加入到局部社区,逐步找出给定节点所在的社区;最后,在真实网络和仿真网络数据集上进行了实验.实验结果表明,该算法能有效地挖掘出给定节点所在的局部社区,相比具有代表性的Clauset,LWP,GMAC等局部社区发现算法有更高的准确率.