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

A novel local community detection algorithm based on common neighbors similarity measurement with weighted neighbor nodes

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

Community structure is a common property in many networks.Traditional community detection algorithms aim at discovering all communities in a network and the running time of these algorithms usually depends on the size of the entire network.For big networks,it is difficult to discover their global community structure due to the high time complexity.Local community detection surges as a kind of methods which start with a given node that is already known to be in the target community,and the goal is to uncover the remaining nodes in the community.This kind of algorithms usually starts from a given node and gradually expands outward without requiring global network structure.The running time of these local communities detection algorithms depends on the size of the community rather than that of the entire network.Thus local community detection has important applicationsignificance in big network analysis tasks.So far the research of local community detection has drawn a lot of attention and many algorithms have been proposed.Most of the existing local community detection algorithms require users to specify the parameter values manually and have low accuracy.For solving this problem,a new local community detection algorithm is proposed in this paper.Firstly,we propose a new common neighbors based similarity measurement with weighted neighbor nodes,which is employed to calculate the similarity between two nodes in a network.Secondly,based on this similarity measurement,a new local community quality metric is given.We discover a local community of the given node by iteratively adding a node from shell node set to the target community which has the largest embedded degree with the current local community,while ensuring the gain of the current local community quality metric is not negative.Extensive experimental results on both synthetic and real-world network datasets show that the proposed algorithm is highly effective at local community detection compared with Clauset,LWP and GMAC algorithms.