第12卷第3期 智能系统学报 Vol.12 No.3 2017年6月 CAAI Transactions on Intelligent Systems Jun.2017 D0I:10.11992/is.201705013 网络出版地址：htp:/kns.cmki.net/kcms/detail/23.1538.TP.20170705.1656.006.html 基于三支决策的非重叠社团划分 方莲娣12，张燕平12，陈洁12，王倩倩3，刘峰12，王刚12 (1.安徽大学计算机科学与技术学院，安徽合肥230601：2.安徽大学计算机智能与信号处理教育部重点实验室，安 徽合肥230601：3.安徽大学国际商学院，安徽合肥230601) 摘要：基于三支决策理论，提出了一种基于三支决策的非重叠社团划分算法(NTWD),该方法将初始聚类形成的 重叠社团进行二次划分以形成最终的非重叠社团。NTWD算法首先利用层次聚类形成有重叠的社团结构，将两个 存在重叠的社团的左边社团中非重叠部分定义为正域，右边社团中非重叠部分定义为负域，而两个社团的重叠部分 定义为边界域。然后，针对边界域中的节点，分别计算边界域中节点与正域和负域的社团归属度B。、B,进行二次划 分。对于二次划分后仍然留在边界域中的节点将利用投票的方法决定其最终归属，最终获得非重叠的社团结构。 本文选取4个经典社交网络数据集和1个真实世界数据集对NTVD算法进行了验证，相比较其他社团划分算法 (GN、NFA,LPA、CACDA),N-TWD时间复杂度较低，总体获取的社团模块度值更高。 关键词：复杂网络：社团划分：重叠节点：三支决策理论：粒化系数；层次聚类；社团结构：节点归属度 中图分类号：TP301文献标志码：A文章编号：1673-4785(2017)03-0293-08 中文引用格式：方莲娣，张燕平，陈洁，等.基于三支决策的非重叠社团划分[J].智能系统学报，2017,12(3)：293-300. 英文引用格式：FANG Liandi,ZHANG Yanping,CHEN Jie,etal.Three-way decision based on non-overlapping community division[J].CAAI transactions on intelligent systems,2017,12(3):293-300. Three-way decision based on non-overlapping community division FANG Liandi.2,ZHANG Yanping"2,CHEN Jie2,WANG Qiangian,LIU Feng2,WANG Gang'.2 (1.School of Computer Science and Technology,Anhui University,Hefei 230601,China;2.Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education,Anhui University,Hefei 230601,China;3.School of Business,Anhui University, Hefei 230601,China) Abstract: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 (Bp,B)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). Keywords:complex network;community division;overlapping node;three-way decision;granulation coefficient; hierarchical clustering;community structure;node belonging degree 在现实世界中，很多事物的联系都是以网络的 统中的人际关系网，生态系统中的神经元网和蛋白 形式存在的。例如，互联网中的社交网络，社会系 质交互网。大量的研究表明，许多实际网络中都存 在着社团结构-]。社团将网络中具有紧密联系的 收稿日期：2017-05-12.网络出版日期：2017-07-05， 事物划分在一起，每个社团内部的节点之间连接相 基金项目：国家“863”计划项目(2015AA124102):国家自然科学基金项 目(61673020.61602003.61402006)：安徽省自然科学基金项 对紧密而社团之间的连接比较稀疏[)。研究网络 目(1508085MF113,1708085QF156,1708085QF143,1708085MF163): 中的社团结构具有重要意义。如何有效地进行社 安徽省高等学校省级自然科学基金重点项目(KJ2013A016」 KJ2016A016):教育部人文社科青年基金项目(14Y门C860020). 团划分，成为了社团研究者们一直致力于研究的一 通信作者：张燕平.E-mail:zhangyp2@gmail.com
第 １２ 卷第 ３ 期 智 能 系 统 学 报 Ｖｏｌ．１２ №．３ ２０１７ 年 ６ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｊｕｎ． ２０１７ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１７０５０１３ 网络出版地址：ｈｔｔｐ： ／ ／ ｋｎｓ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１７０７０５．１６５６．００６．ｈｔｍｌ 基于三支决策的非重叠社团划分 方莲娣１，２ ，张燕平１，２ ，陈洁１，２ ，王倩倩３ ，刘峰１，２ ，王刚１，２ （１．安徽大学 计算机科学与技术学院， 安徽 合肥 ２３０６０１；２．安徽大学 计算机智能与信号处理教育部重点实验室，安 徽 合肥 ２３０６０１； ３．安徽大学 国际商学院，安徽 合肥 ２３０６０１） 摘 要：基于三支决策理论，提出了一种基于三支决策的非重叠社团划分算法（Ｎ⁃ＴＷＤ）， 该方法将初始聚类形成的 重叠社团进行二次划分以形成最终的非重叠社团。 Ｎ⁃ＴＷＤ 算法首先利用层次聚类形成有重叠的社团结构，将两个 存在重叠的社团的左边社团中非重叠部分定义为正域，右边社团中非重叠部分定义为负域，而两个社团的重叠部分 定义为边界域。 然后，针对边界域中的节点，分别计算边界域中节点与正域和负域的社团归属度 ＢＰ 、ＢＮ 进行二次划 分。 对于二次划分后仍然留在边界域中的节点将利用投票的方法决定其最终归属，最终获得非重叠的社团结构。 本文选取 ４ 个经典社交网络数据集和 １ 个真实世界数据集对 Ｎ⁃ＴＷＤ 算法进行了验证，相比较其他社团划分算法 （ＧＮ、ＮＦＡ、ＬＰＡ、ＣＡＣＤＡ），Ｎ⁃ＴＷＤ 时间复杂度较低，总体获取的社团模块度值更高。 关键词：复杂网络；社团划分；重叠节点；三支决策理论；粒化系数；层次聚类；社团结构；节点归属度 中图分类号：ＴＰ３０１ 文献标志码：Ａ 文章编号：１６７３－４７８５（２０１７）０３－０２９３－０８ 中文引用格式：方莲娣，张燕平，陈洁，等． 基于三支决策的非重叠社团划分［Ｊ］． 智能系统学报， ２０１７， １２（３）： ２９３－３００． 英文引用格式：ＦＡＮＧ Ｌｉａｎｄｉ， ＺＨＡＮＧ Ｙａｎｐｉｎｇ， ＣＨＥＮ Ｊｉｅ， ｅｔ ａｌ． Ｔｈｒｅｅ⁃ｗａｙ ｄｅｃｉｓｉｏｎ ｂａｓｅｄ ｏｎ ｎｏｎ⁃ｏｖｅｒｌａｐｐｉｎｇ ｃｏｍｍｕｎｉｔｙ ｄｉｖｉｓｉｏｎ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１７， １２（３）： ２９３－３００． Ｔｈｒｅｅ⁃ｗａｙ ｄｅｃｉｓｉｏｎ ｂａｓｅｄ ｏｎ ｎｏｎ⁃ｏｖｅｒｌａｐｐｉｎｇ ｃｏｍｍｕｎｉｔｙ ｄｉｖｉｓｉｏｎ ＦＡＮＧ Ｌｉａｎｄｉ １， ２ ， ＺＨＡＮＧ Ｙａｎｐｉｎｇ １， ２ ， ＣＨＥＮ Ｊｉｅ １， ２ ， ＷＡＮＧ Ｑｉａｎｑｉａｎ ３ ， ＬＩＵ Ｆｅｎｇ １， ２ ， ＷＡＮＧ Ｇａｎｇ １， ２ （１．Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ａｎｈｕｉ Ｕｎｉｖｅｒｓｉｔｙ， Ｈｅｆｅｉ ２３０６０１， Ｃｈｉｎａ； ２．Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ ｏｆ Ｉｎｔｅｌｌｉｇｅｎｔ Ｃｏｍｐｕｔｉｎｇ ａｎｄ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｉｎｇ ｏｆ Ｍｉｎｉｓｔｒｙ ｏｆ Ｅｄｕｃａｔｉｏｎ， Ａｎｈｕｉ Ｕｎｉｖｅｒｓｉｔｙ， Ｈｅｆｅｉ ２３０６０１， Ｃｈｉｎａ； ３． Ｓｃｈｏｏｌ ｏｆ Ｂｕｓｉｎｅｓｓ， Ａｎｈｕｉ Ｕｎｉｖｅｒｓｉｔｙ， Ｈｅｆｅｉ ２３０６０１， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｓ ａｎ ａｌｇｏｒｉｔｈｍ ｃａｌｌｅｄ Ｎ⁃ＴＷＤ ｂａｓｅｄ ｏｎ ｔｈｅ ｔｈｅｏｒｙ ｏｆ ｔｈｒｅｅ－ｗａｙ ｄｅｃｉｓｉｏｎ， ｗｈｉｃｈ ｃａｎ ｆｕｒｔｈｅｒ ｄｉｖｉｄｅ ｏｖｅｒｌａｐｐｉｎｇ ｃｏｍｍｕｎｉｔｉｅｓ ｆｏｒｍｅｄ ｂｙ ｔｈｅ ｉｎｉｔｉａｌ ｃｌｕｓｔｅｒｉｎｇ ｉｎｔｏ ｎｏｎ⁃ｏｖｅｒｌａｐｐｉｎｇ ｃｏｍｍｕｎｉｔｉｅｓ． Ｆｉｒｓｔ， ｉｔ ｕｔｉｌｉｚｅｓ ａ ｈｉｅｒａｒｃｈｉｃａｌ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｔｏ ｇｅｔ ａｎ ｏｖｅｒｌａｐｐｉｎｇ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ． Ｔｈｅ ｎｏｄｅｓ ｉｎ ｔｈｅ ｎｏｎ⁃ ｏｖｅｒｌａｐｐｉｎｇ ｐａｒｔｓ ｏｆ ｔｈｅ ｃｏｍｍｕｎｉｔｙ ｏｆ ｔｈｅ ｌｅｆｔ ｓｉｄｅ ｂｅｔｗｅｅｎ ｔｗｏ ｃｏｍｍｕｎｉｔｉｅｓ ｗｉｔｈ ｏｖｅｒｌａｐｐｉｎｇ ｐａｒｔｓ ｗｅｒｅ ｄｅｆｉｎｅｄ ａｓ ｐｏｓｉｔｉｖｅ ｒｅｇｉｏｎｓ． Ｔｈｅｎ， ｔｈｅ ｎｏｄｅｓ ｏｎ ｉｔｓ ｒｉｇｈｔ ａｒｅ ｄｅｎｏｔｅｄ ａｓ ｔｈｅ ｎｅｇａｔｉｖｅ ｒｅｇｉｏｎ， ａｎｄ ｎｏｄｅｓ ｉｎ ｔｈｅ ｏｖｅｒｌａｐｐｉｎｇ ｐａｒｔｓ ａｒｅ ｄｅｎｏｔｅｄ ａｓ ｔｈｅ ｂｏｕｎｄａｒｙ ｒｅｇｉｏｎ． Ｔｈｅ ｄｅｇｒｅｅ ｏｆ ｂｅｌｏｎｇｉｎｇ （ＢＰ ，ＢＮ ） ｂｅｔｗｅｅｎ ｔｈｅ ｐｏｓｉｔｉｖｅ ａｎｄ ｎｅｇａｔｉｖｅ ｒｅｇｉｏｎｓ ｗａｓ ｃａｌｃｕｌａｔｅｄ ｕｓｉｎｇ ｔｈｅ ｎｏｄｅｓ ｉｎ ｔｈｅ ｂｏｕｎｄａｒｙ ｒｅｇｉｏｎ． Ｍｏｒｅｏｖｅｒ， ａ ｆｕｒｔｈｅｒ ｄｉｖｉｓｉｏｎ ｗａｓ ｄｏｎｅ ｂａｓｅｄ ｏｎ ｔｈｅ ｄｅｇｒｅｅ ｏｆ ｂｅｌｏｎｇｉｎｇ． Ａｆｔｅｒ ｄｉｖｉｓｉｏｎ， ｔｈｅ ｂｅｌｏｎｇｉｎｇ ｏｆ ｔｈｅ ｒｅｓｔ ｎｏｄｅｓ ｉｎ ｔｈｅ ｂｏｕｎｄａｒｙ ｒｅｇｉｏｎ ｗｏｕｌｄ ｂｅ ｄｅｔｅｒｍｉｎｅｄ ｂｙ ｖｏｔｉｎｇ ｔｏ ｕｌｔｉｍａｔｅｌｙ ｇｅｔ ａ ｎｏｎ⁃ｏｖｅｒｌａｐｐｉｎｇ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ． Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｆｏｒ ｆｏｕｒ ｃｌａｓｓｉｃａｌ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ ａｎｄ ｏｎｅ ｒｅａｌ⁃ｗｏｒｌｄ ｄａｔａ⁃ｓｅｔ ｉｎｄｉｃａｔｅ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ ｈａｓ ａ ｌｏｗｅｒ ｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ ａｎｄ ｇｅｔｓ ａ ｈｉｇｈｅｒ ｍｏｄｕｌａｒｉｔｙ ｖａｌｕｅ ｔｈａｎ ｏｔｈｅｒ ｃｏｍｍｕｎｉｔｙ ｄｉｖｉｓｉｏｎ ａｌｇｏｒｉｔｈｍｓ （ＧＮ， ＮＦＡ， ＬＰＡ， ＣＡＣＤＡ）． Ｋｅｙｗｏｒｄｓ： ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋ； ｃｏｍｍｕｎｉｔｙ ｄｉｖｉｓｉｏｎ； ｏｖｅｒｌａｐｐｉｎｇ ｎｏｄｅ； ｔｈｒｅｅ⁃ｗａｙ ｄｅｃｉｓｉｏｎ； ｇｒａｎｕｌａｔｉｏｎ ｃｏｅｆｆｉｃｉｅｎｔ； ｈｉｅｒａｒｃｈｉｃａｌ ｃｌｕｓｔｅｒｉｎｇ；ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ； ｎｏｄｅ ｂｅｌｏｎｇｉｎｇ ｄｅｇｒｅｅ 收稿日期：２０１７－０５－１２． 网络出版日期：２０１７－０７－０５． 基金项目：国家“８６３”计划项目（２０１５ＡＡ１２４１０２）；国家自然科学基金项 目（６１６７３０２０，６１６０２００３，６１４０２００６）； 安徽省自然科学基金项 目（１５０８０８５ＭＦ１１３，１７０８０８５ＱＦ１５６，１７０８０８５ＱＦ１４３，１７０８０８５ＭＦ１６３）； 安徽省高等学校省级自然科学基金重点项目（ＫＪ２０１３Ａ０１６， ＫＪ２０１６Ａ０１６）； 教育部人文社科青年基金项目（１４ＹＪＣ８６００２０）． 通信作者：张燕平．Ｅ⁃ｍａｉｌ ：ｚｈａｎｇｙｐ２＠ ｇｍａｉｌ．ｃｏｍ． 在现实世界中，很多事物的联系都是以网络的 形式存在的。 例如，互联网中的社交网络，社会系 统中的人际关系网，生态系统中的神经元网和蛋白 质交互网。 大量的研究表明，许多实际网络中都存 在着社团结构［１－２］ 。 社团将网络中具有紧密联系的 事物划分在一起，每个社团内部的节点之间连接相 对紧密而社团之间的连接比较稀疏［３］ 。 研究网络 中的社团结构具有重要意义。 如何有效地进行社 团划分，成为了社团研究者们一直致力于研究的一
·294 智能系统学报 第12卷 个重要方向之一。近年来，许多学者分别从不同角 紧密关系依次进行划分，而不仅仅只根据邻居数目 度对社团进行划分研究，其中著名的算法有 进行投票，更好地体现了节点的真实归属。本文采 Kernighan-Lin算法[、谱平分法s-6和GN算法[) 用4个真实的社交网络数据集和1个真实数据集对 等。随着研究的深入，人们发现在进行社团划分时 N-TWD算法进行了验证，实验结果证明了三支决策 经常会出现重叠部分，即一个节点被多个社团包 方法对部分重叠节点处理的可行性和有效性。 含。因实际需要将重叠节点划分到单个社团中，更 有助于发现社团内存在的规律，并预测网络的行为 1 相关工作 和功能[】。因此，对于非重叠社团划分的研究，也 1.1三支决策理论 是十分必要的。 三支决策理论对于现实世界中的不确定信息 对于非重叠社团划分的研究也引起了很多学 决策问题的解决具有高效性，尤其对那些信息缺 者的关注和研究。Newman快速算法(newman fast 失、证据不充分或者不完整的情况。这时，由于信 algorithm,NFA)I)依靠模块度获得最优社团结构： 息不精确、不一致、不完整等原因，无法立即做出接 Radicchi等[io提出了自包含GN算法(self-contained 受或拒绝的决策。于是，可以采用一种延迟决策或 GN algorithm),给出了强社团和弱社团结构两种量 边界决策，即不做任何承诺的决策。正常情况下， 的定义，为如何确定社团结构提供了一种衡量标 当证据变得足够或者完备时，就有可能进一步做出 准：赵姝等山将粒计算思想引入到网络的社团划分 正决策或负决策。 中，通过对网络结构的聚类粒化实现社团划分，其 三支决策的主要思想是将整体分为3个独立的 时间复杂度低、收敛速度快、精确度高，实现了时间 部分：正域、负域、边界域。对不同的部分采取不同 复杂度与精确度之间的平衡。这些现有的非重叠 的处理方法，为求解复杂问题提供了一种有效的策 社团划分算法从不同的角度和应用层面对非重叠 略与方法[5 社团的划分进行了研究，并取得了丰硕的研究成 当前，三支决策的研究主要基于决策粗糙集， 果。但这些算法对重叠部分处理时都只应用了传 整个论域被划分成3个部分，即正域(POS)、负域 统的二支决策[2-]方法，即根据已有的信息只做出 (NEG)和边界域(BND),分别代表着接受、拒绝和 接受或拒绝决策。但重叠部分的节点往往因为信 不承诺3种决策结果。决策粗糙集模型理论 息量不够无法决定其归属，才会出现在重叠部分， (decision--theoretic rough set model,DTRS),是由姚 如果强制做出决策，可能影响最终非重叠社团划分 一豫等在1990年提出2-23]。它将概率粗糙集和最 的结果。三支决策对于处理那些不确定信息具有 小风险贝叶斯决策结合起来，通过计算各类分类决 一定的实用性141。当信息不足时，三支决策理论 策风险损失值，对正域(POS)、负域(NEG)和边界 对不确定性问题首先做三分类，即正域、负域、边界 域(BND)进行划分。假设有两种状态的集合2= 域：再通过进一步观察，获得足够的信息，将边界域 {X,X},X和X是互补关系的两种状态，即对象属 的对象进行二次划分，实现最终的二支决策。本文 于X或者属于X。由于分类结果有3个域，给定决 在文献[11]的基础上，引入三支决策思想〔0)，改进 策集A=(P,B,N),其中P、B、N分别表示将对象划 了对于重叠部分的处理方法，提出了一种基于三支 分到正域、负域、边界域的决策行为。由于采取不 决策的非重叠划分算法(three-way decision based on 同决策行为会产生不同的损失，AP、入即、AP分别代 non-overlapping community division,N-TWD),以划分 表当x属于X时，x被划分到正域、负域、边界域的 出更合理的非重叠社团。以划分出更合理的非重 损失；AvAN入w则分别代表当x不属于X时，x 叠社团。该算法首先将两个存在重叠部分的社团 被划分到正域、负域、边界域的损失。表1为对应的 的左边社团非重叠部分定义为正域，右边社团的非 决策损失矩阵。 重叠部分定义为负域，而两个社团的重叠部分定义 表13种决策的损失矩阵 为边界域，分别计算边界域中的节点与正域和负域 Table 1 Loss function matrix of three-way decisions 的社团归属度B、B、,依据两者的差值进行二次划 状态 P B N 分。对于二次划分后仍然留在边界域中的节点将 X 利用投票的方法决定其最终归属，最终获得非重叠 App ARP ANP 的社团结构。 X APN 入BN λNW N-TWD算法对于社团重叠部分（边界域）获取 根据Bayes决策过程的推导，通过引入参数a、 了节点，与已明确划分的社团（正域/负域）之间的 B可得到基于决策粗糙集的三支决策规则
个重要方向之一。 近年来，许多学者分别从不同角 度对 社 团 进 行 划 分 研 究， 其 中 著 名 的 算 法 有 Ｋｅｒｎｉｇｈａｎ⁃Ｌｉｎ 算法［４］ 、谱平分法［５－６］ 和 ＧＮ 算法［７］ 等。 随着研究的深入，人们发现在进行社团划分时 经常会出现重叠部分，即一个节点被多个社团包 含。 因实际需要将重叠节点划分到单个社团中，更 有助于发现社团内存在的规律，并预测网络的行为 和功能［８］ 。 因此，对于非重叠社团划分的研究，也 是十分必要的。 对于非重叠社团划分的研究也引起了很多学 者的关注和研究。 Ｎｅｗｍａｎ 快速算法（ ｎｅｗｍａｎ ｆａｓｔ ａｌｇｏｒｉｔｈｍ，ＮＦＡ） ［９］ 依靠模块度获得最优社团结构； Ｒａｄｉｃｃｈｉ 等［１０］提出了自包含 ＧＮ 算法（ｓｅｌｆ⁃ｃｏｎｔａｉｎｅｄ ＧＮ ａｌｇｏｒｉｔｈｍ），给出了强社团和弱社团结构两种量 的定义，为如何确定社团结构提供了一种衡量标 准；赵姝等［１１］将粒计算思想引入到网络的社团划分 中，通过对网络结构的聚类粒化实现社团划分，其 时间复杂度低、收敛速度快、精确度高，实现了时间 复杂度与精确度之间的平衡。 这些现有的非重叠 社团划分算法从不同的角度和应用层面对非重叠 社团的划分进行了研究，并取得了丰硕的研究成 果。 但这些算法对重叠部分处理时都只应用了传 统的二支决策［１２－１３］方法，即根据已有的信息只做出 接受或拒绝决策。 但重叠部分的节点往往因为信 息量不够无法决定其归属，才会出现在重叠部分， 如果强制做出决策，可能影响最终非重叠社团划分 的结果。 三支决策对于处理那些不确定信息具有 一定的实用性［１４－１９］ 。 当信息不足时，三支决策理论 对不确定性问题首先做三分类，即正域、负域、边界 域；再通过进一步观察，获得足够的信息，将边界域 的对象进行二次划分，实现最终的二支决策。 本文 在文献［１１］的基础上，引入三支决策思想［２０］ ，改进 了对于重叠部分的处理方法，提出了一种基于三支 决策的非重叠划分算法（ｔｈｒｅｅ⁃ｗａｙ ｄｅｃｉｓｉｏｎ ｂａｓｅｄ ｏｎ ｎｏｎ⁃ｏｖｅｒｌａｐｐｉｎｇ ｃｏｍｍｕｎｉｔｙ ｄｉｖｉｓｉｏｎ，Ｎ⁃ＴＷＤ），以划分 出更合理的非重叠社团。 以划分出更合理的非重 叠社团。 该算法首先将两个存在重叠部分的社团 的左边社团非重叠部分定义为正域，右边社团的非 重叠部分定义为负域，而两个社团的重叠部分定义 为边界域，分别计算边界域中的节点与正域和负域 的社团归属度 ＢＰ 、ＢＮ，依据两者的差值进行二次划 分。 对于二次划分后仍然留在边界域中的节点将 利用投票的方法决定其最终归属，最终获得非重叠 的社团结构。 Ｎ⁃ＴＷＤ 算法对于社团重叠部分（边界域）获取 了节点，与已明确划分的社团（正域／ 负域） 之间的 紧密关系依次进行划分，而不仅仅只根据邻居数目 进行投票，更好地体现了节点的真实归属。 本文采 用 ４ 个真实的社交网络数据集和 １ 个真实数据集对 Ｎ⁃ＴＷＤ 算法进行了验证，实验结果证明了三支决策 方法对部分重叠节点处理的可行性和有效性。 １ 相关工作 １．１ 三支决策理论 三支决策理论对于现实世界中的不确定信息 决策问题的解决具有高效性，尤其对那些信息缺 失、证据不充分或者不完整的情况。 这时，由于信 息不精确、不一致、不完整等原因，无法立即做出接 受或拒绝的决策。 于是，可以采用一种延迟决策或 边界决策，即不做任何承诺的决策。 正常情况下， 当证据变得足够或者完备时，就有可能进一步做出 正决策或负决策。 三支决策的主要思想是将整体分为 ３ 个独立的 部分：正域、负域、边界域。 对不同的部分采取不同 的处理方法，为求解复杂问题提供了一种有效的策 略与方法［１５］ 。 当前，三支决策的研究主要基于决策粗糙集， 整个论域被划分成 ３ 个部分，即正域（ ＰＯＳ）、负域 （ＮＥＧ）和边界域（ＢＮＤ），分别代表着接受、拒绝和 不承 诺 ３ 种 决 策 结 果。 决 策 粗 糙 集 模 型 理 论 （ｄｅｃｉｓｉｏｎ⁃ｔｈｅｏｒｅｔｉｃ ｒｏｕｇｈ ｓｅｔ ｍｏｄｅｌ， ＤＴＲＳ），是由姚 一豫等在 １９９０ 年提出［２１－２３］ 。 它将概率粗糙集和最 小风险贝叶斯决策结合起来，通过计算各类分类决 策风险损失值，对正域（ ＰＯＳ）、负域（ＮＥＧ） 和边界 域（ＢＮＤ） 进行划分。 假设有两种状态的集合 Ω ＝ ｛Ｘ，¬Ｘ｝，Ｘ 和¬Ｘ 是互补关系的两种状态，即对象属 于 Ｘ 或者属于¬Ｘ。 由于分类结果有 ３ 个域，给定决 策集 Ａ ＝ （Ｐ，Ｂ，Ｎ），其中 Ｐ、Ｂ、Ｎ 分别表示将对象划 分到正域、负域、边界域的决策行为。 由于采取不 同决策行为会产生不同的损失，λＰＰ 、λＢＰ 、λＮＰ分别代 表当 ｘ 属于 Ｘ 时，ｘ 被划分到正域、负域、边界域的 损失；λＰＮ、λＢＮ、λＮＮ则分别代表当 ｘ 不属于 Ｘ 时，ｘ 被划分到正域、负域、边界域的损失。 表 １ 为对应的 决策损失矩阵。 表 １ ３ 种决策的损失矩阵 Ｔａｂｌｅ １ Ｌｏｓｓ ｆｕｎｃｔｉｏｎ ｍａｔｒｉｘ ｏｆ ｔｈｒｅｅ⁃ｗａｙ ｄｅｃｉｓｉｏｎｓ 状态 Ｐ Ｂ Ｎ Ｘ λＰＰ λＢＰ λＮＰ ¬ Ｘ λＰＮ λＢＮ λＮＮ 根据 Ｂａｙｅｓ 决策过程的推导，通过引入参数 α、 β 可得到基于决策粗糙集的三支决策规则。 ·２９４· 智 能 系 统 学 报 第 １２ 卷
第3期 方莲娣，等：基于三支决策的非重叠社团划分 ·295· 若P(X|[X]R)≥a,则x∈POS(X)(1) BND」表示正域、负域和边界域中所有不同节点的 若B<P(XI[X]R)<a,则x∈BND(X)(2) 个数。 若P(X[X]e)≤B,则x∈NEG(X) (3) 给出一个参数入∈[0,1]，当粒集合中存在任意 其中 两个粒的粒化系数f(Gr)≥入时，对这两个粒进行邻 入PN-入BN 接粒化操作，否则，就不对该粒集合进行邻接粒化 (4) (APW-入BN)+(ABP-入PP） 操作。 入Pm-AN 模块度函数Q2]模块度函数Q是由Newman B= (5) (ABN-AN)+（AP-入BP） 和Girvan提出的，在社交网络中，它是衡量一个非 1.2重叠社团中的3个域 重叠社团划分好坏的量化指标。目前，模块度函数 本文基于三支决策的思想，实现对网络的非重 Q作为社团划分评价标准已经被广泛使用。其定义 叠社团结构划分。对于初始聚类粒化后获得重叠 如下： 的社团结构定义如下。 Q=∑(ea-a)=Tre-le2l (7) 1)正域(P0S):左边社团的非重叠节点。 式中：‖e2‖表示矩阵e2中所有元素之和。先定义一 2)负域(NEG):右边社团的非重叠节点。 个kx水的对称矩阵e=(e:),e,表示网络中连接两个 3)边界域(BND):重叠部分的节点。 不同社团的节点的边在所有边中所占的比例，这两 其中，正域与负域仅仅为相对的概念，也可将 个节点分别位于第i个社团和第广个社团。设矩阵 边界域的左边定义为负域，右边定义为正域。本文 中对角线上的元素之和为Tre=∑e:,ea表示网络中 为叙述方便，只将左边称为正域，右边称为负域。 连接某一个社团内部各节点的边在所有的边的数 如图1所示，左右两个椭圆分别代表两个社团 目中所占的比例。定义每行（或每列）中各元素之 结构，从图中可以看出两个社团存在一定的重叠部 和为a,=∑ea,其表示与第i个社团中节点相连的边 分，如图中阴影部分，节点9和节点10。依据三支 决策思想，可以将重叠部分定义为边界域，重叠部 在所有边中所占的比例。如果社团内部边的比例 分左边社团定义为正域(POS(X)),即节点集合{1， 不大于任意连接时的期望值，则有Q=0。Q的上限 2,3,4},重叠部分右边社团定义为负域(NEG(X)), 为Q=1。社团结构越明显，则越接近1。在实际网 即节点集合{5,6,7,8}。图1中的阴影部分为边界 络中，Q的取值范围一般为0.3~0.7。 域(BND(X)),即节点集合{9,10}。 2 基于三支决策的非重叠社团划分 BND 算法 NEG 三支决策模型根据正域、负域和边界域获取决 策规则，在处理模糊性、不完整性数据时，可以给出 不承诺规则，能够降低误判2，提高决策正确性。 图1重叠社团3个域的划分 对于社团划分，边界域的存在是暂时的，随着获取 Fig.1 The division of three domains in overlapping 信息的增多，对边界域中对象的认识更加细化，最 community 终的划分必须是明确的，即正域和负域。为了划分 1.3社团评价标准 边界域中节点的归属问题，本文基于三支决策理 本文采用与文献[11]相同的聚类粒化思想进 论，计算边界域节点的社团归属度，增加新的信息 行初始社团划分，形成重叠的社团结构。算法中以 进行二次决策，提出一种基于三支决策的非重叠社 粒化系数为阈值控制合成过程，并选取模块度函数 团划分算法。 Q对划分结果进行评价，现将粒化系数和模块度概 2.1节点相似度与社团归属度 念介绍如下。 为了评价边界域中的节点与正域、负域间的归 粒化系数f(C)是判断是否对社团进行聚类 属关系，给出如下定义。 粒化的一个标准，其公式如下： 定义1节点相似度SVV[21。给定一个无向 LBND 无权网络G=(V,E),其中V={,i=1,2,…,n}代表 粒化系数f(C)=LPOS+NEG+BND可 (6) 网络中节点的集合，E={(u,v)|u,ve}代表边的 式中：C:,CSC,BND=C:nC,POS=C:-BND 集合。邻居节点的相似度可以表示为 NEG=C,-BND;C是粒化到当前的粒集合；LBND」 rv)n r) 表示两个粒集合中相同节点的个数；LPOS+NEG+ SVV(vi,;)=- k()×k(巴) (8)
若 Ｐ（Ｘ ［Ｘ］ Ｒ ） ≥ α，则 ｘ ∈ ＰＯＳ（Ｘ） （１） 若 β ＜ Ｐ（Ｘ ［Ｘ］ Ｒ ） ＜ α，则 ｘ ∈ ＢＮＤ（Ｘ） （２） 若 Ｐ（Ｘ ［Ｘ］ Ｒ ） ≤ β，则 ｘ ∈ ＮＥＧ（Ｘ） （３） 其中 α ＝ λＰＮ － λＢＮ （λＰＮ － λＢＮ） ＋ （λＢＰ － λＰＰ ） （４） β ＝ λＰＮ － λＮＮ （λＢＮ － λＮＮ） ＋ （λＮＰ － λＢＰ ） （５） １．２ 重叠社团中的 ３ 个域 本文基于三支决策的思想，实现对网络的非重 叠社团结构划分。 对于初始聚类粒化后获得重叠 的社团结构定义如下。 １）正域 （ＰＯＳ）：左边社团的非重叠节点。 ２）负域 （ＮＥＧ）：右边社团的非重叠节点。 ３）边界域 （ＢＮＤ）：重叠部分的节点。 其中，正域与负域仅仅为相对的概念，也可将 边界域的左边定义为负域，右边定义为正域。 本文 为叙述方便，只将左边称为正域，右边称为负域。 如图 １ 所示，左右两个椭圆分别代表两个社团 结构，从图中可以看出两个社团存在一定的重叠部 分，如图中阴影部分，节点 ９ 和节点 １０。 依据三支 决策思想，可以将重叠部分定义为边界域，重叠部 分左边社团定义为正域(ＰＯＳ(Ｘ) ) ，即节点集合｛１， ２，３，４｝，重叠部分右边社团定义为负域(ＮＥＧ(Ｘ) ) ， 即节点集合｛５，６，７，８｝。 图 １ 中的阴影部分为边界 域(ＢＮＤ(Ｘ) ) ，即节点集合｛９，１０｝。 图 １ 重叠社团 ３ 个域的划分 Ｆｉｇ．１ Ｔｈｅ ｄｉｖｉｓｉｏｎ ｏｆ ｔｈｒｅｅ ｄｏｍａｉｎｓ ｉｎ ｏｖｅｒｌａｐｐｉｎｇ ｃｏｍｍｕｎｉｔｙ １．３ 社团评价标准 本文采用与文献［１１］ 相同的聚类粒化思想进 行初始社团划分，形成重叠的社团结构。 算法中以 粒化系数为阈值控制合成过程，并选取模块度函数 Ｑ 对划分结果进行评价，现将粒化系数和模块度概 念介绍如下。 粒化系数 ｆ（Ｃ） 是判断是否对社团进行聚类 粒化的一个标准，其公式如下： 粒化系数 ｆ（Ｃ） ＝ ⌊ＢＮＤ」 ⌊ＰＯＳ ＋ ＮＥＧ ＋ ＢＮＤ」 （６） 式中： Ｃｉ， Ｃｊ ⊆ Ｃ， ＢＮＤ ＝ Ｃｉ ∩ Ｃｊ， ＰＯＳ ＝ Ｃｉ － ＢＮＤ， ＮＥＧ＝Ｃｊ －ＢＮＤ；Ｃ 是粒化到当前的粒集合；⌊ ＢＮＤ」 表示两个粒集合中相同节点的个数；⌊ ＰＯＳ ＋ＮＥＧ＋ ＢＮＤ」表示正域、负域和边界域中所有不同节点的 个数。 给出一个参数 λ∈ [０，１] ，当粒集合中存在任意 两个粒的粒化系数 ｆ(Ｇｒ) ≥λ 时，对这两个粒进行邻 接粒化操作，否则，就不对该粒集合进行邻接粒化 操作。 模块度函数 Ｑ ［２４］ 模块度函数 Ｑ 是由 Ｎｅｗｍａｎ 和 Ｇｉｒｖａｎ 提出的，在社交网络中，它是衡量一个非 重叠社团划分好坏的量化指标。 目前，模块度函数 Ｑ 作为社团划分评价标准已经被广泛使用。 其定义 如下： Ｑ ＝ ∑ｉ ｅｉｉ － ａ ２ ｉ ( ) ＝ Ｔｒｅ － ｅ ２ （７） 式中： ｅ ２ 表示矩阵 ｅ ２ 中所有元素之和。 先定义一 个 ｋ×ｋ 的对称矩阵 ｅ ＝ ｅｉｊ ( ) ，ｅｉｊ表示网络中连接两个 不同社团的节点的边在所有边中所占的比例，这两 个节点分别位于第 ｉ 个社团和第 ｊ 个社团。 设矩阵 中对角线上的元素之和为 Ｔｒｅ ＝ ∑ｉ ｅｉｉ，ｅｉｉ表示网络中 连接某一个社团内部各节点的边在所有的边的数 目中所占的比例。 定义每行（或每列） 中各元素之 和为ａｉ ＝∑ ｊ ｅｉｊ，其表示与第 ｉ 个社团中节点相连的边 在所有边中所占的比例。 如果社团内部边的比例 不大于任意连接时的期望值，则有 Ｑ ＝ ０。 Ｑ 的上限 为 Ｑ＝ １。 社团结构越明显，则越接近 １。 在实际网 络中，Ｑ 的取值范围一般为 ０．３～０．７。 ２ 基于三支决策的非重叠社团划分 算法 三支决策模型根据正域、负域和边界域获取决 策规则，在处理模糊性、不完整性数据时，可以给出 不承诺规则，能够降低误判［２５］ ，提高决策正确性。 对于社团划分，边界域的存在是暂时的，随着获取 信息的增多，对边界域中对象的认识更加细化，最 终的划分必须是明确的，即正域和负域。 为了划分 边界域中节点的归属问题，本文基于三支决策理 论，计算边界域节点的社团归属度，增加新的信息 进行二次决策，提出一种基于三支决策的非重叠社 团划分算法。 ２．１ 节点相似度与社团归属度 为了评价边界域中的节点与正域、负域间的归 属关系，给出如下定义。 定义 １ 节点相似度 ＳＶＶ ［２６］ 。 给定一个无向 无权网络 Ｇ ＝ (Ｖ，Ｅ) ，其中 Ｖ ＝ ｖ { ｉ，ｉ ＝ １，２，…，ｎ}代表 网络中节点的集合，Ｅ ＝ { (ｕ，ｖ) ｕ，ｖ∈Ｖ} 代表边的 集合。 邻居节点的相似度可以表示为 ＳＶＶ ｖｉ，ｖｊ ( ) ＝ Γ ｖｉ ( ) ∩ Γ ｖｊ ( ) ｋ ｖｉ ( ) × ｋ ｖｊ ( ) （８） 第 ３ 期 方莲娣，等：基于三支决策的非重叠社团划分 ·２９５·
·296· 智能系统学报 第12卷 式中：对于边界域中的节点，定义它的邻居为 By-B90.11-0.05 T(w),k()=|T()|是节点v的度；T(:)、T(e)表 对于节点9，Bp-B= =1>y,则被划 0.06 示节点u:心的邻居数目；|T(:)∩T(e)表示共同 BNIO-BPIO 0.03 邻居数目：k(:)、k()分别表示节点：的度。 分到正域中；对于节点10，TB,-B,0.06 =0.5Y,则v∈P0S(X) 输入一个无向无权网络G:(V,E)。 若8，~ 输出无重叠的网络社团结构POS(X)、 ->y,则v∈NEG(X)(12) Bp-Bxm NEG(X)。 Be-Bx 1)初始化网络，根据公式(6)计算粒化系数 若Bp-B ·<Y,则v∈BND(X)(13) POS(X)、NEG(X)、BND(X)。 根据式(11)~(13)可将边界域参数映射到[0， 2)计算边界域中节点与正域、负域中的社团的 1]区间。将边界域中的节点进一步划分到正域或 归属度Bp和Bv: 负域中。如图2所示，通过分别计算边界域中节点 Bp-Bx 9、10与正域（负域）的归属度及其差值，即 while BND(X)y do Bw=0.11,B9=0.05; 、 Bp-BN Bm-B9=0.11-0.05=0.06: -8,y B9-Bm=0.05-0.11=-0.06; then vE POS(X)POS(X)=POS(X)+v) Bpo=0.12,B0=0.09; else vE NEG(X),NEG(X)=NEG(X)+v) Bpm0-B0=0.12-0.09=0.03: end while Bmo-Bp0=0.09-0.12=-0.03; 3)在2)完成后，对于仍然留在边界域中的节点 则|Bp-Bxlm=0.11-0.05=0.06,此时当y=0.6时， 进行投票处理：
式中： 对于边界域中的节点 ｖ， 定义它的邻居为 Γ(ｖ) ，ｋ (ｖ) ＝ Γ(ｖ) 是节点 ｖ 的度；Γ ｖｉ ( ) 、Γ ｖｊ ( ) 表 示节点ｖｉ、ｖｊ 的邻居数目； Γ ｖｉ ( ) ∩Γ ｖｊ ( ) 表示共同 邻居数目；ｋ ｖｉ ( ) 、ｋ ｖｊ ( ) 分别表示节点ｖｉ、ｖｊ 的度。 定义 ２ 边界域中节点 ｖ 与正域、负域间的归 属度。 由于边界域节点与正域（负域） 间的归属度 反映了该域节点与正域（负域）连接的紧密程度，归 属度越大，说明它们之间连接越紧密，更有可能被 划分到正域（负域）中。 边界域中节点与正域、负域 之间的归属度分别表示为 ＢＰ ＝ Ｂｅｌｏｎｇｎｅｓｓ＿ＰＯＳ(ｖ，ＰＯＳ) ＝ ∑ ＮＰ ｉ ＳＶＶ ｖｉ，ｖｊ ( ) ＮＰ （９） ＢＮ ＝ Ｂｅｌｏｎｇｎｅｓｓ＿ＮＥＧ(ｖ，ＮＥＧ) ＝ ∑ ＮＮ ｉ ＳＶＶ ｖｉ，ｖｊ ( ) ＮＮ （１０） 式中：ｖｉ∈ＢＮＤ；ｖｊ∈ＰＯＳ(ＮＥＧ) ；ＮＰ 是正域中节点数 目总和，ＮＰ ＝ ＰＯＳ；ＮＮ 是负域中节点数目总和，ＮＮ ＝ ＮＥＧ；ＢＰ 表示边界域中的节点与正域的归属度；ＢＮ 表示边界域中的节点与负域的归属度。 定义 ３ 边界域参数 γ。 ＢＰ 、ＢＮ 表示通过式 （９）、式（１０）计算得到的归属度值，即 ＢＰ 表示边界 域中节点 ｖ 与正域计算得到的归属度，ＢＮ 表示边界 域中节点 ｖ 与负域计算得到的边界域的归属度， ＢＰ －ＢＮ ｍａｘ表示归属度差值绝对值的最大值。 可依 据边界域参数 γ 进行如下划分： 若 ＢＰ － ＢＮ ＢＰ － ＢＮ ｍａｘ ＞ γ，则 ｖ ∈ ＰＯＳ(Ｘ) （１１） 若 ＢＮ － ＢＰ ＢＰ － ＢＮ ｍａｘ ＞ γ，则 ｖ ∈ ＮＥＧ(Ｘ) （１２） 若 ＢＰ － ＢＮ ＢＰ － ＢＮ ｍａｘ ＜ γ，则 ｖ ∈ ＢＮＤ(Ｘ) （１３） 根据式（１１） ～ （１３）可将边界域参数映射到［０， １］区间。 将边界域中的节点进一步划分到正域或 负域中。 如图 ２ 所示，通过分别计算边界域中节点 ９、１０ 与正域（负域）的归属度及其差值，即 ＢＰ９ ＝ ０．１１，ＢＮ９ ＝ ０．０５； ＢＰ９ － ＢＮ９ ＝ ０．１１ － ０．０５ ＝ ０．０６； ＢＮ９ － ＢＰ９ ＝ ０．０５ － ０．１１ ＝ － ０．０６； ＢＰ１０ ＝ ０．１２，ＢＮ１０ ＝ ０．０９； ＢＰ１０ － ＢＮ１０ ＝ ０．１２ － ０．０９ ＝ ０．０３； ＢＮ１０ － ＢＰ１０ ＝ ０．０９ － ０．１２ ＝ － ０．０３； 则 ＢＰ －ＢＮ ｍａｘ ＝ ０．１１－０．０５ ＝ ０．０６，此时当 γ ＝ ０．６ 时， 对于节点 ９， ＢＰ９ －ＢＮ９ ＢＰ －ＢＮ ｍａｘ ＝ ０．１１－０．０５ ０．０６ ＝ １＞γ， 则被划 分到正域中；对于节点 １０， ＢＮ１０ －ＢＰ１０ ＢＰ －ＢＮ ｍａｘ ＝ ０．０３ ０．０６ ＝ ０．５＜ γ，依然留在边界域中，等待下一步投票处理。 图 ２ 计算归属度后 ３ 个域的划分 Ｆｉｇ．２ Ｔｈｅ ｄｉｖｉｓｉｏｎ ｏｆ ｔｈｒｅｅ ｄｏｍａｉｎｓ ａｆｔｅｒ ｃａｌｃｕｌａｔｉｏｎ ｏｆ ｂｅｌｏｎｇｉｎｇ ｄｅｇｒｅｅ ２．２ 算法流程描述 在 Ｎ⁃ＴＷＤ 算法中引入三支决策的思想，算法 流程具体描述如算法 １ 所示。 算法 １ 中针对归属度 处理后依然留在边界域中的节点按照邻居节点投 票法进行处理，假设归属度处理后仍留在边界域中 的节点 ｖ∈ＢＮＤ(Ｘ) ，令与节点 ｖ 直接相连的 ｋ 个节 点的 集 合 为 ｖ１ ，ｖ２ ，．．．，ｖｋ { } ； 如 果 ｖ ∈ ＢＮＤ (Ｘ) 与 ＰＯＳ(Ｘ) 中的节点ｖｉ 有直接连边，则标记ｌ ｐｉ ；反之与 ＮＥＧ(Ｘ) 中的节点ｖｊ 有直接连边，则标记ｌ ｎｉ 。 其中ｐｉ 表示节点ｖｉ 属于正域的编号，ｎｉ 表示节点ｖｊ 属于负 域的编号。 因此，可得归属度处理后仍留在边界域 中的 节 点 ｖ 对 应 的 编 号 集 合 为 Ｌ ＝ Ｌａｂｅｌ (ｖ) ＝ ｌ ｐ １ ，ｐ ２ ，…，ｐ ｋ ( ) ，ｌ ｎ１ ，ｎ２ ，．．．，ｎｋ ( ) { } ，Ｎ(Ｌ) 函数返回编号集合 Ｌ 中出现频率最高的社团编号。 最终可获得非重叠 的社团结构划分结果。 算法 １ Ｎ－ＴＷＤ 算法。 输入 一个无向无权网络 Ｇ：(Ｖ，Ｅ) 。 输出 无 重 叠 的 网 络 社 团 结 构 ＰＯＳ(Ｘ) 、 ＮＥＧ(Ｘ) 。 １）初始化网络，根据公式（ ６） 计算粒化系数 ＰＯＳ(Ｘ) 、ＮＥＧ(Ｘ) 、ＢＮＤ(Ｘ) 。 ２）计算边界域中节点与正域、负域中的社团的 归属度ＢＰ 和ＢＮ： ｗｈｉｌｅ∃ｖ∈ＢＮＤ(Ｘ) 、 ＢＰ －ＢＮ ＢＰ －ＢＮ ｍａｘ ＞γ ｄｏ ｉｆ ＢＰ －ＢＮ ＢＰ －ＢＮ ｍａｘ ＞γ ｔｈｅｎ ｖ∈ＰＯＳ(Ｘ) ，ＰＯＳ(Ｘ) ＝ ＰＯＳ(Ｘ) ＋{ｖ} ｅｌｓｅ ｖ∈ＮＥＧ(Ｘ) ，ＮＥＧ(Ｘ) ＝ＮＥＧ(Ｘ) ＋{ｖ} ｅｎｄ ｗｈｉｌｅ ３）在 ２）完成后，对于仍然留在边界域中的节点 进行投票处理： ·２９６· 智 能 系 统 学 报 第 １２ 卷
第3期 方莲娣，等：基于三支决策的非重叠社团划分 ·297. Be-Bx 较少，所以使用本算法划分后效果不明显。总体 whileBND(X)By do 上，即当y≠0时，在4个数据集上社团划分评价指标 L=Label(v) Q的值都基本优于y=0和y=1时的值，此时划分 ifN(L)∈POS(X) 后的社团内部联系比较紧密，说明采用三支决策的 then vE POS(X),POS(X)=POS(X)+v) 方法对边界域中重叠节点进行二步决策对社团划 else,vENEG(X),NEG(X)=NEG(X)+v) 分有明显的作用，使社团划分更加合理。 end while 0.40 4)输出POS(X)和NEG(X)。 0.35 -=0.04 -=0 3实验分析 0.30 0.25 3.1基准数据实验 0 0.20 为了验证N-TWD算法的有效性和可行性，本 0.15 文采用了4个典型社交网络数据集作为测试数据 0.10 集，分别是著名的空手道俱乐部网络(Zachary's 0.05 karate club)、足球联盟网络(American college 0.20.3 0.40.50.60.70.8 football)、海豚网络(dolphin social network)和悲惨 (a)karate数据集 世界网络(lesmis)。实验数据集的基本信息如表2。 0.6 表2实验数据集的基本信息 0.5 Table 2 Benchmark datasets information 0.4 数据集 节点数 边数 0.3 karate 34 78 dolphins 62 159 0.2 football 115 613 0.19 s 0-=0 lesmis 77 254 0.2 0.3 0.4 0.50.60.70.8 在N-TWD算法中，粒化参数入、边界域参数y 的取值对算法的最终结果有一定的影响。参数入 (b)football数据集 作为粒化系数，控制着初始社团粒度，对于最终的 0.50 社团划分好坏有一定的影响。若入为1，则任意两 0.45 粒子都不满足粒化条件，算法无法进行粒化操作迭 0.40 代，直接按投票法获得最终的社团结构：若入为0， 0.35 则任意两粒子之间均可进行粒化操作，迭代后所得 0.30 到的粒子包含了所有网络的节点，即该网络可视为 0.25 一个社团。参数Y作为边界域参数，它的大小决定 0.2 0.2 0.3040.50.60.70.8 投票和归属度这两种方法对边界域中节点处理的 多少。y为1时，则边界域中的节点采用全投票法， (c)dolphin数据集 等同于文献[11]所提算法；y为0时，则边界域中的 0.55 节点采用全归属度方法处理。图3给出了在不同数 0.45 据集上γy取得最优值时Q值随参数入值变化的关 0.35 系图。其中，y=1表示完全采用投票处理边界域中 0.25 的节点；y=0表示完全使用归属度处理边界域中的 节点；γ≠0表示对边界域中的节点先采用归属度处 0.15 Fl -±.=0.02 理后，对于仍留在边界域中的节点采用投票法处 。-0 0.05 理。从图3中(a)、(b)、(d)明显可以看出，随着 00.2030.40.50.60.70.8 入的增大，折线入≠0基本都在折线入=0和y=1上 (d)lesmis数据集 方。图3中(c)图，由于dolphin数据集自身网络特 图3Q值与入值关系图 别稀疏，在层次聚类粒化的过程中获得的重叠部分 Fig.3 The connection between A and O
ｗｈｉｌｅ∃ｖ∈ＢＮＤ(Ｘ) ， ＢＰ －ＢＮ ＢＰ －ＢＮ ｍａｘ ＜γ ｄｏ Ｌ ＝ Ｌａｂｅｌ(ｖ) ｉｆ Ｎ(Ｌ) ∈ＰＯＳ(Ｘ) ｔｈｅｎ ｖ∈ＰＯＳ(Ｘ) ，ＰＯＳ(Ｘ) ＝ ＰＯＳ(Ｘ) ＋{ｖ} ｅｌｓｅ，ｖ∈ＮＥＧ(Ｘ) ，ＮＥＧ(Ｘ) ＝ＮＥＧ(Ｘ) ＋{ｖ} ｅｎｄ ｗｈｉｌｅ ４）输出 ＰＯＳ(Ｘ) 和 ＮＥＧ(Ｘ) 。 ３ 实验分析 ３．１ 基准数据实验 为了验证 Ｎ⁃ＴＷＤ 算法的有效性和可行性，本 文采用了 ４ 个典型社交网络数据集作为测试数据 集，分别是 著 名 的 空 手 道 俱 乐 部 网 络 （ Ｚａｃｈａｒｙｓ ｋａｒａｔｅ ｃｌｕｂ ）、 足 球 联 盟 网 络 （ Ａｍｅｒｉｃａｎ ｃｏｌｌｅｇｅ ｆｏｏｔｂａｌｌ）、海豚网络（ ｄｏｌｐｈｉｎ ｓｏｃｉａｌ ｎｅｔｗｏｒｋ） 和悲惨 世界网络（ｌｅｓｍｉｓ）。 实验数据集的基本信息如表 ２。 表 ２ 实验数据集的基本信息 Ｔａｂｌｅ ２ Ｂｅｎｃｈｍａｒｋ ｄａｔａｓｅｔｓ ｉｎｆｏｒｍａｔｉｏｎ 数据集 节点数 边数 ｋａｒａｔｅ ３４ ７８ ｄｏｌｐｈｉｎｓ ６２ １５９ ｆｏｏｔｂａｌｌ １１５ ６１３ ｌｅｓｍｉｓ ７７ ２５４ 在 Ｎ⁃ＴＷＤ 算法中，粒化参数 λ、边界域参数 γ 的取值对算法的最终结果有一定的影响。 参数 λ 作为粒化系数，控制着初始社团粒度，对于最终的 社团划分好坏有一定的影响。 若 λ 为 １，则任意两 粒子都不满足粒化条件，算法无法进行粒化操作迭 代，直接按投票法获得最终的社团结构；若 λ 为 ０， 则任意两粒子之间均可进行粒化操作，迭代后所得 到的粒子包含了所有网络的节点，即该网络可视为 一个社团。 参数 γ 作为边界域参数，它的大小决定 投票和归属度这两种方法对边界域中节点处理的 多少。 γ 为 １ 时，则边界域中的节点采用全投票法， 等同于文献［１１］所提算法；γ 为 ０ 时，则边界域中的 节点采用全归属度方法处理。 图 ３ 给出了在不同数 据集上 γ 取得最优值时 Ｑ 值随参数 λ 值变化的关 系图。 其中，γ ＝ １ 表示完全采用投票处理边界域中 的节点；γ ＝ ０ 表示完全使用归属度处理边界域中的 节点；γ≠０ 表示对边界域中的节点先采用归属度处 理后，对于仍留在边界域中的节点采用投票法处 理。 从图 ３ 中（ ａ）、（ ｂ）、（ ｄ） 明显可以看出，随着 λ 的增大，折线 λ≠０ 基本都在折线 λ ＝ ０ 和 γ ＝ １ 上 方。 图 ３ 中（ｃ）图，由于 ｄｏｌｐｈｉｎ 数据集自身网络特 别稀疏，在层次聚类粒化的过程中获得的重叠部分 较少，所以使用本算法划分后效果不明显。 总体 上，即当γ≠０时，在 ４ 个数据集上社团划分评价指标 Ｑ 的值都基本优于 γ ＝ ０ 和 γ ＝ １ 时的值，此时划分 后的社团内部联系比较紧密，说明采用三支决策的 方法对边界域中重叠节点进行二步决策对社团划 分有明显的作用，使社团划分更加合理。 （ａ）ｋａｒａｔｅ 数据集 （ｂ）ｆｏｏｔｂａｌｌ 数据集 （ｃ）ｄｏｌｐｈｉｎ 数据集 （ｄ）ｌｅｓｍｉｓ 数据集 图 ３ Ｑ 值与 λ 值关系图 Ｆｉｇ．３ Ｔｈｅ ｃｏｎｎｅｃｔｉｏｎ ｂｅｔｗｅｅｎ λ ａｎｄ Ｑ 第 ３ 期 方莲娣，等：基于三支决策的非重叠社团划分 ·２９７·
·298 智能系统学报 第12卷 从图3的分析可知，边界域参数y的引入可以 表3数据集中不同算法Q值的比较 使延迟决策划分到边界域中的重叠节点做出二次 Table 3 Comparison of O by different algorithm in datasets 决策，决策结果对非重叠社团划分的好坏有较为显 Networks karate football dolphin lesmis 著的影响。图4给出了在4个不同数据集上，当入 N-TWD 0.391 0.594 0.477 0.544 取上述最优值时，Q值随着边界域参数y的变化情 GN 0.359 0.54 0.519 0.51 况。由于各个数据集自身网络结构不同，需要从不 NFA 0.381 0.577 0.495 0.498 同的侧面来了解网络结构，从而获得更充分的信息 LPA 0.374 0.476 0.475 0.417 做出二次决策。在二次决策时，我们引入归属度计 CACDA 0.364 0.594 0.474 0.527 算和邻居节点投票处理。归属度反映了节点与社 团间联系的紧密程度：投票法根据节点的邻居数目 表3给出了N-TWD算法与其他相关算法划分 多少决定其归属。这两者从不同的侧面对边界域 后最优的模块度值的对比实验结果。从表3中可以 中的对象有了更细化的认识，而y取值的大小决定 看出，本文提出的算法N-TWD在karate和lesmis、 football上都获得了最高的模块度值，在dolphin上 两种方法对重叠部分处理的多少。根据不同数据 也获得了较高的模块度值。CACDA在football上获 集的自身特性选择合适的值作为边界域参数y的 得了最高的模块度值，但没能在其他网络上获取较 值。由图4可以看出，随着y的增大，数据集 高的模块度值。由于本文算法和CACDA算法的主 karate、football、lesmis的模块度Q值在0~0.05范围 要开销在于进行粒化，需要遍历邻接矩阵的每行 先增后减，在y=0.05~0.25之间波动范围不大。而 (每列)，其时间复杂度均为O(n2)。GN虽然在数 dolphin数据集在y=0.1~0.15之间先增后减，在y= 据集dolphin上取得最高的Q值，但是它的时间复 0.15~0.2之间虽有增大趋势但未超过最高值，在 杂度是这5种算法中最高的，为O(n3)。NFA虽然 y=O.2以后基本趋于平稳。其中karate、football、 在dolphin获得了第2高模块度值，但由于NFA本 dolphin、lesmis这4个数据集中y取值分别为0.04 身是贪婪寻优算法，所以可以获得很高的模块度算 0.15、0.2、0.02时，Q值最大，说明y∈[0,0.2]时，边 法，且NFA需要非常多的时间进行迭代，其时间复 界域中节点划分效果最好。 杂度为O((m+n)n)。LPA的线性复杂度为O(m+ n)。从表3中可以看出，本文提出的算法相比其他 0.60 0.55,+* 0-09-0-0 00000066666 4个算法，时间复杂度较低，获取的社团模块度值总 0.501 在4d--- 0.45 体上更高，总体性能更优。 0.40 3.2应用数据实验 o0.35 为了进一步验证本文所提出的N-TWD算法的 0.30 0.25 .karate 有效性，本文以某市移动通信的实际应用数据为例 0.20 ..football 0.15 --dolphin 进行实验。实验数据根据通信基站间是否有信号 -lesmis 0.10 切换确定两基站节点间是否存在边来构建网络模 0.050.10 0.15 0.200.25 型。构建的无权无向网络如图5所示，其中包含 图4y值与Q值关系图 3644个顶点，6976条边。 Fig.4 The connection between y and Q 作者将本文算法与其他相关社团划分算法 (GN、NFA、LPA、CACDA)在4个真实的网络数据集 上的模块度Q值进行了对比，实验结果如表3所 示。其中，G)为经典的分裂式层次社团挖掘算 法，NFA[)为Newman快速算法，是基于模块度优化 的凝聚式社团挖掘算法，LPA[2)]为快速标签传播算 图5无权无向网络 Fig.5 A unweighted and undirected network 法，CACDA为基于邻接粒化的社团发现算法
从图 ３ 的分析可知，边界域参数 γ 的引入可以 使延迟决策划分到边界域中的重叠节点做出二次 决策，决策结果对非重叠社团划分的好坏有较为显 著的影响。 图 ４ 给出了在 ４ 个不同数据集上，当 λ 取上述最优值时，Ｑ 值随着边界域参数 γ 的变化情 况。 由于各个数据集自身网络结构不同，需要从不 同的侧面来了解网络结构，从而获得更充分的信息 做出二次决策。 在二次决策时，我们引入归属度计 算和邻居节点投票处理。 归属度反映了节点与社 团间联系的紧密程度；投票法根据节点的邻居数目 多少决定其归属。 这两者从不同的侧面对边界域 中的对象有了更细化的认识，而 γ 取值的大小决定 两种方法对重叠部分处理的多少。 根据不同数据 集的自身特性选择合适的值作为边界域参数 γ 的 值。 由图 ４ 可 以 看 出， 随 着 γ 的 增 大， 数 据 集 ｋａｒａｔｅ、ｆｏｏｔｂａｌｌ、ｌｅｓｍｉｓ 的模块度 Ｑ 值在 ０ ～ ０．０５ 范围 先增后减，在 γ ＝ ０．０５～ ０．２５ 之间波动范围不大。 而 ｄｏｌｐｈｉｎ 数据集在 γ ＝ ０．１～０．１５ 之间先增后减，在 γ ＝ ０．１５ ～ ０．２ 之间虽有增大趋势但未超过最高值，在 γ ＝ ０． ２ 以后基本趋于平稳。 其中 ｋａｒａｔｅ、 ｆｏｏｔｂａｌｌ、 ｄｏｌｐｈｉｎ、ｌｅｓｍｉｓ 这 ４ 个数据集中 γ 取值分别为 ０．０４、 ０．１５、０．２、０．０２ 时，Ｑ 值最大，说明 γ∈ [０，０．２] 时，边 界域中节点划分效果最好。 图 ４ γ 值与 Ｑ 值关系图 Ｆｉｇ．４ Ｔｈｅ ｃｏｎｎｅｃｔｉｏｎ ｂｅｔｗｅｅｎ γ ａｎｄ Ｑ 作者将本文算法与其他相关社团划分算法 （ＧＮ、ＮＦＡ、ＬＰＡ、ＣＡＣＤＡ）在 ４ 个真实的网络数据集 上的模块度 Ｑ 值进行了对比，实验结果如表 ３ 所 示。 其中，ＧＮ ［７］ 为经典的分裂式层次社团挖掘算 法，ＮＦＡ ［９］为 Ｎｅｗｍａｎ 快速算法，是基于模块度优化 的凝聚式社团挖掘算法，ＬＰＡ ［２７］ 为快速标签传播算 法，ＣＡＣＤＡ ［１１］为基于邻接粒化的社团发现算法。 表 ３ 数据集中不同算法 Ｑ 值的比较 Ｔａｂｌｅ ３ Ｃｏｍｐａｒｉｓｏｎ ｏｆ Ｑ ｂｙ ｄｉｆｆｅｒｅｎｔ ａｌｇｏｒｉｔｈｍ ｉｎ ｄａｔａｓｅｔｓ Ｎｅｔｗｏｒｋｓ ｋａｒａｔｅ ｆｏｏｔｂａｌｌ ｄｏｌｐｈｉｎ ｌｅｓｍｉｓ Ｎ－ＴＷＤ ０．３９１ ０．５９４ ０．４７７ ０．５４４ ＧＮ ０．３５９ ０．５４ ０．５１９ ０．５１ ＮＦＡ ０．３８１ ０．５７７ ０．４９５ ０．４９８ ＬＰＡ ０．３７４ ０．４７６ ０．４７５ ０．４１７ ＣＡＣＤＡ ０．３６４ ０．５９４ ０．４７４ ０．５２７ 表 ３ 给出了 Ｎ⁃ＴＷＤ 算法与其他相关算法划分 后最优的模块度值的对比实验结果。 从表 ３ 中可以 看出，本文提出的算法 Ｎ⁃ＴＷＤ 在 ｋａｒａｔｅ 和 ｌｅｓｍｉｓ、 ｆｏｏｔｂａｌｌ 上都获得了最高的模块度值，在 ｄｏｌｐｈｉｎ 上 也获得了较高的模块度值。 ＣＡＣＤＡ 在 ｆｏｏｔｂａｌｌ 上获 得了最高的模块度值，但没能在其他网络上获取较 高的模块度值。 由于本文算法和 ＣＡＣＤＡ 算法的主 要开销在于进行粒化，需要遍历邻接矩阵的每行 （每列），其时间复杂度均为 Ｏ（ ｎ ２ ）。 ＧＮ 虽然在数 据集 ｄｏｌｐｈｉｎ 上取得最高的 Ｑ 值，但是它的时间复 杂度是这 ５ 种算法中最高的，为 Ｏ（ｎ ３ ）。 ＮＦＡ 虽然 在 ｄｏｌｐｈｉｎ 获得了第 ２ 高模块度值，但由于 ＮＦＡ 本 身是贪婪寻优算法，所以可以获得很高的模块度算 法，且 ＮＦＡ 需要非常多的时间进行迭代，其时间复 杂度为 Ｏ（（ｍ＋ｎ） ｎ）。 ＬＰＡ 的线性复杂度为 Ｏ（ｍ＋ ｎ）。 从表 ３ 中可以看出，本文提出的算法相比其他 ４ 个算法，时间复杂度较低，获取的社团模块度值总 体上更高，总体性能更优。 ３．２ 应用数据实验 为了进一步验证本文所提出的 Ｎ⁃ＴＷＤ 算法的 有效性，本文以某市移动通信的实际应用数据为例 进行实验。 实验数据根据通信基站间是否有信号 切换确定两基站节点间是否存在边来构建网络模 型。 构建的无权无向网络如图 ５ 所示，其中包含 ３ ６４４个顶点，６ ９７６条边。 图 ５ 无权无向网络 Ｆｉｇ．５ Ａ ｕｎｗｅｉｇｈｔｅｄ ａｎｄ ｕｎｄｉｒｅｃｔｅｄ ｎｅｔｗｏｒｋ ·２９８· 智 能 系 统 学 报 第 １２ 卷
第3期 方莲娣，等：基于三支决策的非重叠社团划分 .299. 将图5所示的网络采用本文N-TWD算法进行 a:statistical mechanics and its applications,2009,388 社团划分，图6给出了在真实数据集上Q值与入值 (8):1706-1712. 的关系图。从图6可以看出，在真实数据集网络中， [2]LIU Y,PAN L,JIA X,et al.Three-way decision based 对于划分到边界域中的重叠节点，采用本算法进行 overlapping community detection[C]//Rough Sets and 社团划分依然具有有效性。图6中虚折线表示 Knowledge Technology.Springer,Berlin,2013:279-290. [3]柯望.基于层次粒化的社团发现方法研究[D].合肥：安 N-TWD算法处理后社团模块度的变化趋势，正方形 徽大学，2016. 实折线和圆形实折线分别表示仅采用投票和仅采 KE Wang.Reach on community detection algorithm based on 用归属度处理情况下的模块度变化趋势。图6中随 Hierarchical Granulation[D].Hefei:Anhui University,2016. 着入的变化，y取得最优值时(y=0.03)能比投票 [4]KERNIGHAN B W,LIN S.An efficient heuristic procedure (y=0.2)和归属度方法(y=0)直接决策取得更高 for partitioning graphs [J].The bell system technical Q值，采用和文献[11]相同的干扰模型评价可以得 journal.1970,49(2):291-307. 到更优的频点干扰值。表明在N-TWD算法划分下 [5]ZHANG Y P,WANG Y.Detecting communities using 可以更真实地体现应用数据集中的网络结构特征。 spectral bisection method based on normal matrix [J]. 022 Computer engineering and applications,2006,46(27):43-45. +1020.03=0 0.20 4 [6]POTHEN A,SIMON H D,LIOU K P.Partitioning sparse 0.18, matrices with eigenvectors of graphs[].SIAM journal on 0.16 matrix analysis and applications,1990,11(3):430-452. [7]GIRVAN M,NEWMAN M E J.Community structure in 0.14 social and biological networks[]].Proceedings of the 0.12 national academy of sciences,2002,99(12):7821-7826. 0.104 [8]金弟，杨博，刘杰，等.复杂网络簇结构探测一基于随 0.7 0.8 0.9 1.0 机游走的蚁群算法[J].软件学报，2012,23(3)： 451-464. 图6真实数据集中Q值与入值关系图 JIN Di,YANG Bo LIU Jie,et al.Ant colony optimization Fig.6 The connection between A and O of true dataset based on random walk for community detection in complex networks [J].Journal of software,2012,23(3):451-464. 4结束语 [9]NEWMAN M E J.Fast algorithm for detecting community 本文将三支决策的思想应用于非重叠社团划 structure in networks [J].Physical review E,2004,69 分，提出了一种基于三支决策的非重叠社团划分算 (6):066133. [10]RADICCHI F,CASTELLANO C.CECCONI F,et al. 法(N-TWD),旨在解决社团划分过程中出现的节点 Defining and identifying communities in networks J]. 重叠部分。本文算法基于三支决策的思想，对于社 Proceedings of the national academy of sciences of the 团重叠部分（边界域）通过计算节点与明确社团（正 United States of America,2004,101(9):2658-2663. 域/负域)间的归属度，再对重叠节点的具体归属进 [11]赵妹，柯望，陈洁，等.基于聚类粒化的社团发现算法 行二次决策，从而进行三分类，即正域、负域、待处 [J].计算机应用，2014,34(10)：2812-2815 理（仍留在边界域），对于待处理部分采取邻居节点 ZHAO Shu,KE Wang,CHEN Jie,et al.Community 投票法进行再一次决策，最终将其准确划分到正域 detection algorithm based on clustering granulation [J]. 或负域中。与其他算法相比，本文算法随着决策步 Joumal of computer applications,2014,34(10):2812-2815. 骤的增加，对边界域中样本的归属认知更加细化， [12]YAO YY.Three-way decisions with probabilistic rough 时间复杂度总体较低，且获取了更高的Q值，划分 sets [J].Information sciences,2010,180(3):341-353. 后的社团结构联系比较紧密，说明边界域中的重叠 [13]YAO Y.Two semantic issues in a probabilistic rough set model [J].Fundamental informaticae,2011,108(3/4): 节点得到了更为稳定的划分。下一步将会基于网 249-265 络的局部信息，进一步改进初始重叠社团的获取 [14]贾修一，商琳，周献中，等.三支决策理论与应用[M], 方法。 南京：南京大学出版社，2012. 参考文献： [15]于洪，王国胤，李天瑞，等.三支决策：复杂问题求解方 法与实践[M].北京：科学出版社，2015. [1]SHEN H,CHENG X,CAI K,et al.Detect overlapping and [16]YU H,ZHANG C,WANG G.A tree-based incremental hierarchical community structure in networks J].Physica overlapping clustering method using the three-way decision
将图 ５ 所示的网络采用本文 Ｎ⁃ＴＷＤ 算法进行 社团划分，图 ６ 给出了在真实数据集上 Ｑ 值与 λ 值 的关系图。 从图 ６ 可以看出，在真实数据集网络中， 对于划分到边界域中的重叠节点，采用本算法进行 社团划分依然具有有效性。 图 ６ 中虚折线表示 Ｎ⁃ＴＷＤ算法处理后社团模块度的变化趋势，正方形 实折线和圆形实折线分别表示仅采用投票和仅采 用归属度处理情况下的模块度变化趋势。 图 ６ 中随 着 λ 的变化，γ 取得最优值时（ γ ＝ ０．０３） 能比投票 （γ ＝ ０．２）和归属度方法（ γ ＝ ０） 直接决策取得更高 Ｑ 值，采用和文献［１１］相同的干扰模型评价可以得 到更优的频点干扰值。 表明在 Ｎ⁃ＴＷＤ 算法划分下 可以更真实地体现应用数据集中的网络结构特征。 图 ６ 真实数据集中 Ｑ 值与 λ 值关系图 Ｆｉｇ．６ Ｔｈｅ ｃｏｎｎｅｃｔｉｏｎ ｂｅｔｗｅｅｎ λ ａｎｄ Ｑ ｏｆ ｔｒｕｅ ｄａｔａｓｅｔ ４ 结束语 本文将三支决策的思想应用于非重叠社团划 分，提出了一种基于三支决策的非重叠社团划分算 法（Ｎ⁃ＴＷＤ），旨在解决社团划分过程中出现的节点 重叠部分。 本文算法基于三支决策的思想，对于社 团重叠部分（边界域）通过计算节点与明确社团（正 域／ 负域）间的归属度，再对重叠节点的具体归属进 行二次决策，从而进行三分类，即正域、负域、待处 理（仍留在边界域），对于待处理部分采取邻居节点 投票法进行再一次决策，最终将其准确划分到正域 或负域中。 与其他算法相比，本文算法随着决策步 骤的增加，对边界域中样本的归属认知更加细化， 时间复杂度总体较低，且获取了更高的 Ｑ 值，划分 后的社团结构联系比较紧密，说明边界域中的重叠 节点得到了更为稳定的划分。 下一步将会基于网 络的局部信息，进一步改进初始重叠社团的获取 方法。 参考文献： ［１］ＳＨＥＮ Ｈ， ＣＨＥＮＧ Ｘ， ＣＡＩ Ｋ， ｅｔ ａｌ． Ｄｅｔｅｃｔ ｏｖｅｒｌａｐｐｉｎｇ ａｎｄ ｈｉｅｒａｒｃｈｉｃａｌ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ ｉｎ ｎｅｔｗｏｒｋｓ ［ Ｊ］． Ｐｈｙｓｉｃａ ａ： ｓｔａｔｉｓｔｉｃａｌ ｍｅｃｈａｎｉｃｓ ａｎｄ ｉｔｓ ａｐｐｌｉｃａｔｉｏｎｓ， ２００９， ３８８ （８）： １７０６－１７１２． ［２］ ＬＩＵ Ｙ， ＰＡＮ Ｌ， ＪＩＡ Ｘ， ｅｔ ａｌ． Ｔｈｒｅｅ⁃ｗａｙ ｄｅｃｉｓｉｏｎ ｂａｓｅｄ ｏｖｅｒｌａｐｐｉｎｇ ｃｏｍｍｕｎｉｔｙ ｄｅｔｅｃｔｉｏｎ［Ｃ］ ／ ／ Ｒｏｕｇｈ Ｓｅｔｓ ａｎｄ Ｋｎｏｗｌｅｄｇｅ Ｔｅｃｈｎｏｌｏｇｙ． Ｓｐｒｉｎｇｅｒ， Ｂｅｒｌｉｎ ， ２０１３： ２７９－２９０． ［３］柯望． 基于层次粒化的社团发现方法研究［Ｄ］． 合肥： 安 徽大学， ２０１６． ＫＥ Ｗａｎｇ． Ｒｅａｃｈ ｏｎ ｃｏｍｍｕｎｉｔｙ ｄｅｔｅｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ Ｈｉｅｒａｒｃｈｉｃａｌ Ｇｒａｎｕｌａｔｉｏｎ［Ｄ］． Ｈｅｆｅｉ： Ａｎｈｕｉ Ｕｎｉｖｅｒｓｉｔｙ， ２０１６． ［４］ＫＥＲＮＩＧＨＡＮ Ｂ Ｗ， ＬＩＮ Ｓ． Ａｎ ｅｆｆｉｃｉｅｎｔ ｈｅｕｒｉｓｔｉｃ ｐｒｏｃｅｄｕｒｅ ｆｏｒ ｐａｒｔｉｔｉｏｎｉｎｇ ｇｒａｐｈｓ ［ Ｊ ］． Ｔｈｅ ｂｅｌｌ ｓｙｓｔｅｍ ｔｅｃｈｎｉｃａｌ ｊｏｕｒｎａｌ， １９７０， ４９（２）： ２９１－３０７． ［ ５ ］ ＺＨＡＮＧ Ｙ Ｐ， ＷＡＮＧ Ｙ． Ｄｅｔｅｃｔｉｎｇ ｃｏｍｍｕｎｉｔｉｅｓ ｕｓｉｎｇ ｓｐｅｃｔｒａｌ ｂｉｓｅｃｔｉｏｎ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ｎｏｒｍａｌ ｍａｔｒｉｘ ［ Ｊ ］． Ｃｏｍｐｕｔｅｒ ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ ａｐｐｌｉｃａｔｉｏｎｓ， ２００６， ４６（２７）： ４３－４５． ［６］ＰＯＴＨＥＮ Ａ， ＳＩＭＯＮ Ｈ Ｄ， ＬＩＯＵ Ｋ Ｐ． Ｐａｒｔｉｔｉｏｎｉｎｇ ｓｐａｒｓｅ ｍａｔｒｉｃｅｓ ｗｉｔｈ ｅｉｇｅｎｖｅｃｔｏｒｓ ｏｆ ｇｒａｐｈｓ［Ｊ］． ＳＩＡＭ ｊｏｕｒｎａｌ ｏｎ ｍａｔｒｉｘ ａｎａｌｙｓｉｓ ａｎｄ ａｐｐｌｉｃａｔｉｏｎｓ， １９９０， １１（３）： ４３０－４５２． ［７］ ＧＩＲＶＡＮ Ｍ， ＮＥＷＭＡＮ Ｍ Ｅ Ｊ． Ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ ｉｎ ｓｏｃｉａｌ ａｎｄ ｂｉｏｌｏｇｉｃａｌ ｎｅｔｗｏｒｋｓ［Ｊ］． Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ｎａｔｉｏｎａｌ ａｃａｄｅｍｙ ｏｆ ｓｃｉｅｎｃｅｓ， ２００２， ９９（１２）： ７８２１－７８２６． ［８］金弟， 杨博， 刘杰，等． 复杂网络簇结构探测———基于随 机游 走 的 蚁 群 算 法 ［ Ｊ］． 软 件 学 报， ２０１２， ２３ （ ３ ）： ４５１－４６４． ＪＩＮ Ｄｉ ，ＹＡＮＧ Ｂｏ ，ＬＩＵ Ｊｉｅ， ｅｔ ａｌ． Ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ ｂａｓｅｄ ｏｎ ｒａｎｄｏｍ ｗａｌｋ ｆｏｒ ｃｏｍｍｕｎｉｔｙ ｄｅｔｅｃｔｉｏｎ ｉｎ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｓｏｆｔｗａｒｅ， ２０１２， ２３（３）： ４５１－４６４． ［９］ＮＥＷＭＡＮ Ｍ Ｅ Ｊ． Ｆａｓｔ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｄｅｔｅｃｔｉｎｇ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ ｉｎ ｎｅｔｗｏｒｋｓ ［ Ｊ］． Ｐｈｙｓｉｃａｌ ｒｅｖｉｅｗ Ｅ， ２００４， ６９ （６）： ０６６１３３． ［１０］ ＲＡＤＩＣＣＨＩ Ｆ， ＣＡＳＴＥＬＬＡＮＯ Ｃ， ＣＥＣＣＯＮＩ Ｆ， ｅｔ ａｌ． Ｄｅｆｉｎｉｎｇ ａｎｄ ｉｄｅｎｔｉｆｙｉｎｇ ｃｏｍｍｕｎｉｔｉｅｓ ｉｎ ｎｅｔｗｏｒｋｓ ［ Ｊ ］． Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ｎａｔｉｏｎａｌ ａｃａｄｅｍｙ ｏｆ ｓｃｉｅｎｃｅｓ ｏｆ ｔｈｅ Ｕｎｉｔｅｄ Ｓｔａｔｅｓ ｏｆ Ａｍｅｒｉｃａ， ２００４， １０１（９）： ２６５８－２６６３． ［１１］赵姝， 柯望， 陈洁， 等． 基于聚类粒化的社团发现算法 ［Ｊ］． 计算机应用， ２０１４， ３４（１０）： ２８１２－２８１５． ＺＨＡＯ Ｓｈｕ， ＫＥ Ｗａｎｇ， ＣＨＥＮ Ｊｉｅ， ｅｔ ａｌ． Ｃｏｍｍｕｎｉｔｙ ｄｅｔｅｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｃｌｕｓｔｅｒｉｎｇ ｇｒａｎｕｌａｔｉｏｎ ［ Ｊ ］． Ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔｅｒ ａｐｐｌｉｃａｔｉｏｎｓ， ２０１４， ３４（１０）： ２８１２－２８１５． ［１２］ ＹＡＯ Ｙ Ｙ． Ｔｈｒｅｅ⁃ｗａｙ ｄｅｃｉｓｉｏｎｓ ｗｉｔｈ ｐｒｏｂａｂｉｌｉｓｔｉｃ ｒｏｕｇｈ ｓｅｔｓ ［Ｊ］． Ｉｎｆｏｒｍａｔｉｏｎ ｓｃｉｅｎｃｅｓ， ２０１０， １８０（３）： ３４１－３５３． ［１３］ＹＡＯ Ｙ． Ｔｗｏ ｓｅｍａｎｔｉｃ ｉｓｓｕｅｓ ｉｎ ａ ｐｒｏｂａｂｉｌｉｓｔｉｃ ｒｏｕｇｈ ｓｅｔ ｍｏｄｅｌ ［Ｊ］． Ｆｕｎｄａｍｅｎｔａｌ ｉｎｆｏｒｍａｔｉｃａｅ， ２０１１， １０８（３ ／ ４）： ２４９－２６５． ［１４］贾修一， 商琳， 周献中，等． 三支决策理论与应用［Ｍ］． 南京：南京大学出版社， ２０１２． ［１５］于洪， 王国胤， 李天瑞，等． 三支决策：复杂问题求解方 法与实践［Ｍ］． 北京：科学出版社，２０１５． ［１６］ＹＵ Ｈ， ＺＨＡＮＧ Ｃ， ＷＡＮＧ Ｇ． Ａ ｔｒｅｅ⁃ｂａｓｅｄ ｉｎｃｒｅｍｅｎｔａｌ ｏｖｅｒｌａｐｐｉｎｇ ｃｌｕｓｔｅｒｉｎｇ ｍｅｔｈｏｄ ｕｓｉｎｇ ｔｈｅ ｔｈｒｅｅ⁃ｗａｙ ｄｅｃｉｓｉｏｎ 第 ３ 期 方莲娣，等：基于三支决策的非重叠社团划分 ·２９９·
·300. 智能系统学报 第12卷 theory[J].Knowledge-based systems,2016,91:189-203. JIA Xiuyi,LI Weiwei,SHANG Lin,et al.An adaptive [17]YU H,WANG Y,JIAO P.A three-way decisions leamning parameters algorithm in three-way decision-throretic approach to density-based overlapping clustering [M]. rough set model[J].Chinese journal of electronics,2011, Berlin Heidelberg:Springer,2014:92-109. 39(11):2520-2525 [18]YU H,ZHANG C,HU F.An Incremental Clustering [26]LEICHT E A,HOLME P,NEWMAN M E J.Vertex Approach Based on Three-Way Decisions C]//Rough similarity in networks[]].Physical review E,2006,73 (2):026120. Sets and Current Trends in Computing.Springer,Berlin [27]RAGHAVAN U N,Albert R,Kumara S.Near linear time Heidelberg,2014,8536:152-159. algorithm to detect community structures in large-scale [19]LIU Y,PAN L,JIA X,et al.Three-way decision based networks []Physical reviewe,2007,76(3):036106. overlapping community detection [C]//Rough Sets and 作者简介： Knowledge Technology,2013,8171:279-290. 方莲娣，女，1992年生，硕土研究 [20]YAO Y.An Outline of a theory of three-way decisions 生，主要研究领域为三支决策和机器 [C]//Rough Sets and Currnet Trends in Computing. 学习。 Berlin Heidelberg:Springer,2012:1-17. [21]YAO Y Y,WONG S K M.A decision theoretic framework for approximating concepts [J].International journal of man-machine studies,1992,37(6):793-809. [22]JIA X,TANG Z,LIAO W,et al.On an optimization 张燕平，女，1962年生，教授，博 representation of decision-theoretic rough set model[J]. 士，主要研究方向为粒计算、智能计 International journal of approximate reasoning,2014,55 算、机器学习。获发明专利2项，发表 (1):156-166. 学术论文80余篇。 [23]QIAN Y,ZHANG H,SANG Y,et al.Multi-granulation decision-theoretic rough sets[].International journal of approximate reasoning,2014,55(1):225-237. [24]NEWMAN M E J,GIRVAN M.Finding and evaluating 陈洁，女，1982年生，副教授，博 community structure in networks[J].Physical review E, 士，主要研究方向为智能计算、机器学 2004,69(2):026113. 习、三支决策。发表学术论文10余篇。 [25]贾修一，李伟禕，商琳，等.一种自适应求三枝决策中 决策阈值的算法[J].电子学报，2011,39(11)： 2520-2525
ｔｈｅｏｒｙ［Ｊ］． Ｋｎｏｗｌｅｄｇｅ⁃ｂａｓｅｄ ｓｙｓｔｅｍｓ， ２０１６， ９１：１８９－２０３． ［１７ ］ ＹＵ Ｈ， ＷＡＮＧ Ｙ， ＪＩＡＯ Ｐ． Ａ ｔｈｒｅｅ⁃ｗａｙ ｄｅｃｉｓｉｏｎｓ ａｐｐｒｏａｃｈ ｔｏ ｄｅｎｓｉｔｙ⁃ｂａｓｅｄ ｏｖｅｒｌａｐｐｉｎｇ ｃｌｕｓｔｅｒｉｎｇ ［ Ｍ ］． Ｂｅｒｌｉｎ Ｈｅｉｄｅｌｂｅｒｇ：Ｓｐｒｉｎｇｅｒ， ２０１４： ９２－１０９． ［１８］ ＹＵ Ｈ， ＺＨＡＮＧ Ｃ， ＨＵ Ｆ． Ａｎ Ｉｎｃｒｅｍｅｎｔａｌ Ｃｌｕｓｔｅｒｉｎｇ Ａｐｐｒｏａｃｈ Ｂａｓｅｄ ｏｎ Ｔｈｒｅｅ⁃Ｗａｙ Ｄｅｃｉｓｉｏｎｓ ［ Ｃ ］ ／ ／ Ｒｏｕｇｈ Ｓｅｔｓ ａｎｄ Ｃｕｒｒｅｎｔ Ｔｒｅｎｄｓ ｉｎ Ｃｏｍｐｕｔｉｎｇ． Ｓｐｒｉｎｇｅｒ， Ｂｅｒｌｉｎ Ｈｅｉｄｅｌｂｅｒｇ，２０１４，８５３６： １５２－１５９． ［１９］ ＬＩＵ Ｙ， ＰＡＮ Ｌ， ＪＩＡ Ｘ， ｅｔ ａｌ． Ｔｈｒｅｅ⁃ｗａｙ ｄｅｃｉｓｉｏｎ ｂａｓｅｄ ｏｖｅｒｌａｐｐｉｎｇ ｃｏｍｍｕｎｉｔｙ ｄｅｔｅｃｔｉｏｎ ［ Ｃ］ ／ ／ Ｒｏｕｇｈ Ｓｅｔｓ ａｎｄ Ｋｎｏｗｌｅｄｇｅ Ｔｅｃｈｎｏｌｏｇｙ， ２０１３，８１７１： ２７９－２９０． ［２０］ ＹＡＯ Ｙ． Ａｎ Ｏｕｔｌｉｎｅ ｏｆ ａ ｔｈｅｏｒｙ ｏｆ ｔｈｒｅｅ⁃ｗａｙ ｄｅｃｉｓｉｏｎｓ ［ Ｃ ］ ／ ／ Ｒｏｕｇｈ Ｓｅｔｓ ａｎｄ Ｃｕｒｒｎｅｔ Ｔｒｅｎｄｓ ｉｎ Ｃｏｍｐｕｔｉｎｇ． Ｂｅｒｌｉｎ Ｈｅｉｄｅｌｂｅｒｇ：Ｓｐｒｉｎｇｅｒ， ２０１２： １－１７． ［２１］ＹＡＯ Ｙ Ｙ， ＷＯＮＧ Ｓ Ｋ Ｍ． Ａ ｄｅｃｉｓｉｏｎ ｔｈｅｏｒｅｔｉｃ ｆｒａｍｅｗｏｒｋ ｆｏｒ ａｐｐｒｏｘｉｍａｔｉｎｇ ｃｏｎｃｅｐｔｓ ［ Ｊ］． Ｉｎｔｅｒｎａｔｉｏｎａｌ ｊｏｕｒｎａｌ ｏｆ ｍａｎ⁃ｍａｃｈｉｎｅ ｓｔｕｄｉｅｓ， １９９２， ３７（６）： ７９３－８０９． ［２２］ ＪＩＡ Ｘ， ＴＡＮＧ Ｚ， ＬＩＡＯ Ｗ， ｅｔ ａｌ． Ｏｎ ａｎ ｏｐｔｉｍｉｚａｔｉｏｎ ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ｏｆ ｄｅｃｉｓｉｏｎ⁃ｔｈｅｏｒｅｔｉｃ ｒｏｕｇｈ ｓｅｔ ｍｏｄｅｌ［Ｊ］． Ｉｎｔｅｒｎａｔｉｏｎａｌ ｊｏｕｒｎａｌ ｏｆ ａｐｐｒｏｘｉｍａｔｅ ｒｅａｓｏｎｉｎｇ， ２０１４， ５５ （１）：１５６－１６６． ［２３］ＱＩＡＮ Ｙ， ＺＨＡＮＧ Ｈ， ＳＡＮＧ Ｙ， ｅｔ ａｌ． Ｍｕｌｔｉ⁃ｇｒａｎｕｌａｔｉｏｎ ｄｅｃｉｓｉｏｎ⁃ｔｈｅｏｒｅｔｉｃ ｒｏｕｇｈ ｓｅｔｓ［Ｊ］． Ｉｎｔｅｒｎａｔｉｏｎａｌ ｊｏｕｒｎａｌ ｏｆ ａｐｐｒｏｘｉｍａｔｅ ｒｅａｓｏｎｉｎｇ， ２０１４， ５５（１）： ２２５－２３７． ［２４］ ＮＥＷＭＡＮ Ｍ Ｅ Ｊ， ＧＩＲＶＡＮ Ｍ． Ｆｉｎｄｉｎｇ ａｎｄ ｅｖａｌｕａｔｉｎｇ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ ｉｎ ｎｅｔｗｏｒｋｓ［Ｊ］． Ｐｈｙｓｉｃａｌ ｒｅｖｉｅｗ Ｅ， ２００４， ６９（２）： ０２６１１３． ［２５］贾修一， 李伟湋， 商琳，等． 一种自适应求三枝决策中 决策 阈 值 的 算 法 ［ Ｊ］． 电 子 学 报， ２０１１， ３９ （ １１ ）： ２５２０－２５２５． ＪＩＡ Ｘｉｕｙｉ， ＬＩ Ｗｅｉｗｅｉ， ＳＨＡＮＧ Ｌｉｎ， ｅｔ ａｌ． Ａｎ ａｄａｐｔｉｖｅ ｌｅａｒｎｉｎｇ ｐａｒａｍｅｔｅｒｓ ａｌｇｏｒｉｔｈｍ ｉｎ ｔｈｒｅｅ⁃ｗａｙ ｄｅｃｉｓｉｏｎ⁃ｔｈｒｏｒｅｔｉｃ ｒｏｕｇｈ ｓｅｔ ｍｏｄｅｌ［Ｊ］． Ｃｈｉｎｅｓｅ ｊｏｕｒｎａｌ ｏｆ ｅｌｅｃｔｒｏｎｉｃｓ， ２０１１， ３９（１１）： ２５２０－２５２５ ［２６］ ＬＥＩＣＨＴ Ｅ Ａ， ＨＯＬＭＥ Ｐ， ＮＥＷＭＡＮ Ｍ Ｅ Ｊ． Ｖｅｒｔｅｘ ｓｉｍｉｌａｒｉｔｙ ｉｎ ｎｅｔｗｏｒｋｓ ［ Ｊ］． Ｐｈｙｓｉｃａｌ ｒｅｖｉｅｗ Ｅ， ２００６， ７３ （２）： ０２６１２０． ［２７］ＲＡＧＨＡＶＡＮ Ｕ Ｎ， Ａｌｂｅｒｔ Ｒ， Ｋｕｍａｒａ Ｓ． Ｎｅａｒ ｌｉｎｅａｒ ｔｉｍｅ ａｌｇｏｒｉｔｈｍ ｔｏ ｄｅｔｅｃｔ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅｓ ｉｎ ｌａｒｇｅ⁃ｓｃａｌｅ ｎｅｔｗｏｒｋｓ ［Ｊ］． Ｐｈｙｓｉｃａｌ ｒｅｖｉｅｗｅ， ２００７， ７６（３）： ０３６１０６． 作者简介： 方莲娣， 女 ， １９９２ 年生，硕士研究 生， 主要研究领域为三支决策和机器 学习。 张燕平， 女 ，１９６２ 年生，教授，博 士， 主要研究方向为粒计算、智能计 算、机器学习。 获发明专利 ２ 项，发表 学术论文 ８０ 余篇。 陈洁， 女 ， １９８２ 年生， 副教授， 博 士，主要研究方向为智能计算、机器学 习、三支决策。 发表学术论文 １０ 余篇。 ·３００· 智 能 系 统 学 报 第 １２ 卷