基于子模优化的边界域处理社团发现算法  

Community detection algorithm for boundary region processing based on submodular optimization

作　　者：杨雪洁 曹风云 陈洁[2] 赵姝[2] 张燕平[2] Yang Xuejie;Cao Fengyun;Chen Jie;Zhao Shu;Zhang Yanping(School of Computer,Hefei Normal University,Hefei 230061,China;School of Computer Science and Technology,Anhui University,Hefei 230061,China;Anhui Province Key Laboratory of Simulation and Design for Electronic Information System,Hefei 230061,China)

机构地区：[1]合肥师范学院计算机学院,合肥230601 [2]安徽大学计算机科学与技术学院,合肥230601 [3]合肥师范学院,电子信息系统仿真设计安徽省重点实验室,合肥230601

出　　处：《电子测量与仪器学报》2020年第4期111-117,共7页Journal of Electronic Measurement and Instrumentation

基　　金：国家自然科学基金(61673020,61602003);安徽省自然科学基金(1708085QF156);安徽省高校优秀青年人才项目(gxyq2019068);电子信息系统仿真设计安徽省重点实验室开放基金(2019ZDSYSZY06)资助项目。

摘　　要：使用聚类粒化方法求取非重叠社团结构时,经常会出现重叠区域。三支决策模型将两个存在重叠的社团的左边社团中非重叠部分定义为正域,右边社团中非重叠部分定义为负域,而两个社团的重叠部分定义为边界域。为了获得更好的社团性能,须将边界域中的节点进行二次划分。子模优化在机器学习中有广泛的应用,如果目标函数具有子模性,则存在一个简单的贪心算法能在多项式时间内以常数因子逼近问题的最优解。将子模优化思想引入社团重叠区域节点的处理,提出一种基于子模优化的边界域处理社团发现算法(SO-CDA)。定义设备选址函数进行子模优化,重叠节点的划分可以转化为子模函数最大化问题,在7个真实网络上的实验结果表明,SO-CDA能够有效地进行社团划分,性能更加稳定。Overlapping regions often occur when non-overlapping community structure is obtained by clustering granulation method.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.In order to achieve better community structure,it is necessary to divide the nodes in the boundary region into non-overlapping parts.Submodular optimization is widely used in machine learning,If the objective function has sub-modularity,it exists a simple greedy algorithm which can approximate the optimal solution of the problem with constant factor in polynomial time.In this paper,submodular optimization is introduced into the processing of nodes in overlapping communities.and a community detection algorithm(SO-CDA)for boundary region processing based on submodular optimization is proposed.The device location function is defined for submodular optimization,the partition of overlapping nodes is converted to the maximization of submodular function.The experimental results on seven real networks show that SO-CDA can effectively divide communities and achieve more stable performance.

关 键 词：子模函数 三支决策 复杂网络 社团发现 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程] TN99[自动化与计算机技术—控制科学与工程]