一种基于非对称三角形割的重叠社区发现算法

发现由相似功能的个体所形成的社区结构是复杂网络分析的重要任务之一. 提出一种基于非对称三角形割的重叠社区发现算法,首先根据社区内三角形连接情况对社区质量进行评价,并根据节点与社区的三角形连接定义了节点对社区的归属度和连接强度. 考虑到网络不同部分连接密度的差异,在将节点从社区中移除或加入社区的过程中,为每个节点分别设置了不同的移除阈值和扩展阈值,以提高社区发现质量. 将每个节点与其邻居节点组成初始社区,将归属度低于移除阈值的边缘节点从社区中移除,将连接强度高于扩展阈值的外围节点加入社区,社区节点移除和扩展阶段迭代进行直至社区结构趋于稳定,最后去掉重叠率过高的社区得到最终结果. 在7个带社区标签的网络上将所提算法与其他7个经典重叠社区检测算法进行比较,通过重叠标准互信息和F₁指标进行评价,结果表明所提算法可以较好地发现不同规模网络中的社区结构.

An Overlapping Community Detection AlgorithmBased on Asymmetric Triangle Cuts

Overlapping community detection has attracted more and more attention in the research of complex networks. An overlapping community detection algorithm has been presented based on asymmetric triangle cuts(ATCO). The fitness of a community is defined as the ratio of the triangles within the community and the asymmetric triangle cuts. Furthermore,the membership and connection strength of a node to a community is defined according to the triangle connection between the node and the community. Considering that difference parts of the complex network usually have different link density,we compute specific removal threshold and extension threshold to each node in community reduction and expansion process. ATCO algorithm consists of three main processes:community initialization,node removal and extension,and high overlapping community removing. An initial community consists of a node and its neighbors,and the neighbors are the periphery of the initial community. A peripheral node will be removed from the community,if its membership to the community is lower than the predefined removal threshold. An external node will be added to a community,if its connection strength to the community is higher than the predefined extension threshold. The removal and extension process will be performed iteratively until a stable result is obtained. Finally,communities with high overlap will be postprocessed. Compared with other 7 classical overlapping community detection algorithms on 7 networks with ground-truth,the proposed algorithm ATCO shows good performance in overlapping standard mutual information and F₁ index.