基于连边相似度的重叠社区发现算法研究

Overlapping communities detecting based on similarity of edge

针对GN算法在发现重叠社区时存在的不足,以及为了降低算法时间复杂度,提出一种基于网络图中连边相似度划分连边集的重叠社区发现算法EGN。算法依据网络图的连边集进行划分,每一条边被划分到某个特定的社区,而一个节点可以关联多条连边,因此节点可以被划分到不同的社区,从而发现重叠社区。EGN算法首先需要构造网络节点之间连边关系的边图;然后根据边图中节点的关系计算网络图中连边的相似度,在节点之间相似度的基础上提出了连边之间相似度的计算方法;再按照相似度由小到大对边图删除边,构建出边图的树状图。树状图的每一层对应网络的一个划分,采用划分密度函数来衡量划分的质量,以此寻找最优的划分。最后将算法应用到Zachary空手道俱乐部网络中,并与GN算法进行对比,实验结果表明EGN算法能够很好地发现重叠社区。

To void GN alorithm＇s problem and reduce the computational complexity,this paper proposed a new algorithm called EGN which based on the partition of edges in network.According to the partition of edges,each edge would be partitioned to an independent community,consequently nodes could be partitioned to multiple communities.It could detect the overlapping community in networks at last.Line graph would be constructed before using EGN algorithm which based on the relationship of nodes in network.And after that,the algorithm calculated the similarity of edges in network.It proposed the method of calculation of edge similarity which based on the similarity of node,and then constructed dendrogram of line graph in the whole process at last.Each layer of the dendrogram was related to the partition of networks.Through dividing the dendrogram in one layer,it detected the communities.It used a function of partition density to measure the capability of partition.At last,it applied this algorithm in the Zachary＇s Karate Club network,and compared with GN algorithm.The results of experiment show that the EGN algorithm is able to detect overlapping communities very well.