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

基于三支决策理论，提出了一种基于三支决策的非重叠社团划分算法（N-TWD），该方法将初始聚类形成的重叠社团进行二次划分以形成最终的非重叠社团。N-TWD算法首先利用层次聚类形成有重叠的社团结构，将两个存在重叠的社团的左边社团中非重叠部分定义为正域，右边社团中非重叠部分定义为负域，而两个社团的重叠部分定义为边界域。然后，针对边界域中的节点，分别计算边界域中节点与正域和负域的社团归属度B_P、B_N进行二次划分。对于二次划分后仍然留在边界域中的节点将利用投票的方法决定其最终归属，最终获得非重叠的社团结构。本文选取4个经典社交网络数据集和1个真实世界数据集对N-TWD算法进行了验证，相比较其他社团划分算法（GN、NFA、LPA、CACDA），N-TWD时间复杂度较低，总体获取的社团模块度值更高。

Three-way decision based on non-overlapping community division

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 non-overlapping 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).