一种面向度中心性及重叠网络社区的发现算法  

Algorithm for Discovering Network Community with Centrality and Overlap

作　　者：刘井莲[1,2] 王大玲[1,3] 赵卫绩[2] 冯时[1,3] 张一飞[1,3] 

机构地区：[1]东北大学信息科学与工程学院,沈阳110819 [2]绥化学院信息工程学院,绥化152061 [3]东北大学医学影像计算教育部重点实验室,沈阳110819

出　　处：《计算机科学》2016年第3期33-37,71,共6页Computer Science

基　　金：国家自然科学基金(61370074;61402091)资助

摘　　要：针对社会网络中存在较多以度中心节点为中心并且具有多社区重叠节点的网络社区结构,提出了一种面向度中心性及重叠网络社区的两阶段发现算法。第一阶段发现初始社区:选取度最大的Top-k个节点作为候选中心节点,并将每个节点与其邻居节点形成候选初始社区,其中如果某候选社区与已形成的初始社区的重叠度低于阈值,则形成一个新的初始社区;第二阶段调整社区划分:通过偏离度机制进行调整,将偏离度最大值对应的节点划分到连接紧密的相应社区内,形成最终社区划分。实验表明,该方法不仅能够揭示网络中以某个节点为中心的密集的社区结构,还能有效处理初始社区不同程度的重叠问题。相比现有算法,所提方法对预先输入的候选初始社区数k值不敏感,并具有较高的准确性和灵活性。Many social networks have central nodes and overlap nodes in more than one initial community,so a twostage algorithm for discovering network community with centrality and overlap was proposed in this paper.In the first stage,initial communities are found.First,the top-k maximum degree nodes are chosen as candidate central nodes and the central nodes with their own neighbor nodes form separate candidate initial communities,and then the overlap degree of the candidate initial communities is computed one by one with generated initial communities.If all the overlap degrees are less than a given threshold,a new initial community is formed.In the second stage,the community division is adjusted.A concept of deviate degree is defined,and the corresponding nodes are merged to a closely linked community with maximum deviate degree.Finally community division is formed.Experimental results show that it can not only reveal the tightly-knit network communities in network with centrality,but also deal with problems of overlap initial communities effectively.Compared with existing algorithms,the algorithm in this paper is not sensitive to the prior number of candidate initial communities k,and has a high accuracy and flexibility.

关 键 词：社会网络 社区发现 度中心性 重叠度 偏离度 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]