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

针对社会网络中存在较多以度中心节点为中心并且具有多社区重叠节点的网络社区结构,提出了一种面向度中心性及重叠网络社区的两阶段发现算法。第一阶段发现初始社区:选取度最大的Top-k个节点作为候选中心节点,并将每个节点与其邻居节点形成候选初始社区,其中如果某候选社区与已形成的初始社区的重叠度低于阈值,则形成一个新的初始社区；第二阶段调整社区划分:通过偏离度机制进行调整,将偏离度最大值对应的节点划分到连接紧密的相应社区内,形成最终社区划分。实验表明,该方法不仅能够揭示网络中以某个节点为中心的密集的社区结构,还能有效处理初始社区不同程度的重叠问题。相比现有算法,所提方法对预先输入的候选初始社区数k值不敏感,并具有较高的准确性和灵活性。

Algorithm for Discovering Network Community with Centrality and Overlap

Many social networks have central nodes and overlap nodes in more than one initial community,so a two-stage 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.