基于三支决策的非重叠社团划分  

Three-way decision based on non-overlapping community division

作　　者：方莲娣 张燕平[1,2] 陈洁[1,2] 王倩倩[3] 刘峰[1,2] 王刚[1,2] 

机构地区：[1]安徽大学计算机科学与技术学院,安徽合肥230601 [2]安徽大学计算机智能与信号处理教育部重点实验室,安徽合肥230601 [3]安徽大学国际商学院,安徽合肥230601

出　　处：《智能系统学报》2017年第3期293-300,共8页CAAI Transactions on Intelligent Systems

基　　金：国家"863"计划项目(2015AA124102);国家自然科学基金项目(61673020;61602003;61402006);安徽省自然科学基金项目(1508085MF113;1708085QF156;1708085QF143;1708085MF163);安徽省高等学校省级自然科学基金重点项目(KJ2013A016;KJ2016A016);教育部人文社科青年基金项目(14YJC860020)

摘　　要：基于三支决策理论,提出了一种基于三支决策的非重叠社团划分算法(N-TWD),该方法将初始聚类形成的重叠社团进行二次划分以形成最终的非重叠社团。N-TWD算法首先利用层次聚类形成有重叠的社团结构,将两个存在重叠的社团的左边社团中非重叠部分定义为正域,右边社团中非重叠部分定义为负域,而两个社团的重叠部分定义为边界域。然后,针对边界域中的节点,分别计算边界域中节点与正域和负域的社团归属度B_P、B_N进行二次划分。对于二次划分后仍然留在边界域中的节点将利用投票的方法决定其最终归属,最终获得非重叠的社团结构。本文选取4个经典社交网络数据集和1个真实世界数据集对N-TWD算法进行了验证,相比较其他社团划分算法(GN、NFA、LPA、CACDA),N-TWD时间复杂度较低,总体获取的社团模块度值更高。This paper proposes an algorithm called N-TWD based on the theory of three-way decision,which can further divide overlapping communities formed by the initial clustering into non-overlapping communities. First,it utilizes a hierarchical clustering algorithm to get an overlapping community structure. The nodes in the nonoverlapping parts of the community of the left side between two communities with overlapping parts were defined as positive regions. Then,the nodes on its right are denoted as the negative region,and nodes in the overlapping parts are denoted as the boundary region. The degree of belonging( B_P,B_N) between the positive and negative regions was calculated using the nodes in the boundary region. Moreover,a further division was done based on the degree of belonging. After division,the belonging of the rest nodes in the boundary region would be determined by voting to ultimately get a non-overlapping community structure. The experimental results for four classical social networks and one real-world data-set indicate that the proposed algorithm has a lower time complexity and gets a higher modularity value than other community division algorithms( GN,NFA,LPA,CACDA).

关 键 词：复杂网络 社团划分 重叠节点 三支决策理论 粒化系数 层次聚类 社团结构 节点归属度 

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