[1]方莲娣,张燕平,陈洁,等.基于三支决策的非重叠社团划分[J].智能系统学报,2017,12(3):293-300.[doi:10.11992/tis.201705013]
FANG Liandi,ZHANG Yanping,CHEN Jie,et al.Three-way decision based on non-overlapping community division[J].CAAI Transactions on Intelligent Systems,2017,12(3):293-300.[doi:10.11992/tis.201705013]
点击复制
FANG Liandi,ZHANG Yanping,CHEN Jie,et al.Three-way decision based on non-overlapping community division[J].CAAI Transactions on Intelligent Systems,2017,12(3):293-300.[doi:10.11992/tis.201705013]
基于三支决策的非重叠社团划分
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
12
期数:
2017年第3期
页码:
293-300
栏目:
学术论文—智能系统
出版日期:
2017-06-25
- Title:
- Three-way decision based on non-overlapping community division
- Keywords:
- complex network; community division; overlapping node; three-way decision; granulation coefficient; hierarchical clustering; community structure; node belonging degree
- 分类号:
- TP301
- 摘要:
- 基于三支决策理论，提出了一种基于三支决策的非重叠社团划分算法（N-TWD），该方法将初始聚类形成的重叠社团进行二次划分以形成最终的非重叠社团。N-TWD算法首先利用层次聚类形成有重叠的社团结构，将两个存在重叠的社团的左边社团中非重叠部分定义为正域，右边社团中非重叠部分定义为负域，而两个社团的重叠部分定义为边界域。然后，针对边界域中的节点，分别计算边界域中节点与正域和负域的社团归属度BP、BN进行二次划分。对于二次划分后仍然留在边界域中的节点将利用投票的方法决定其最终归属，最终获得非重叠的社团结构。本文选取4个经典社交网络数据集和1个真实世界数据集对N-TWD算法进行了验证，相比较其他社团划分算法（GN、NFA、LPA、CACDA），N-TWD时间复杂度较低，总体获取的社团模块度值更高。
- 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,BN) 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).
- 参考文献/References:
-
[1] SHEN H, CHENG X, CAI K, et al. Detect overlapping and hierarchical community structure in networks[J]. Physica a: statistical mechanics and its applications, 2009, 388(8): 1706-1712.
[2] LIU Y, PAN L, JIA X, et al. Three-way decision based overlapping community detection[C]//Rough Sets and Knowledge Technology. Springer, Berlin, 2013: 279-290.
[3] 柯望. 基于层次粒化的社团发现方法研究[D]. 合肥: 安徽大学, 2016.KE Wang. Reach on community detection algorithm based on Hierarchical Granulation[D]. Hefei: Anhui University, 2016.
[4] KERNIGHAN B W, LIN S. An efficient heuristic procedure for partitioning graphs[J]. The bell system technical journal, 1970, 49(2): 291-307.
[5] ZHANG Y P, WANG Y. Detecting communities using spectral bisection method based on normal matrix[J]. Computer engineering and applications, 2006, 46(27): 43-45.
[6] POTHEN A, SIMON H D, LIOU K P. Partitioning sparse matrices with eigenvectors of graphs[J]. SIAM journal on matrix analysis and applications, 1990, 11(3): 430-452.
[7] GIRVAN M, NEWMAN M E J. Community structure in social and biological networks[J]. Proceedings of the national academy of sciences, 2002, 99(12): 7821-7826.
[8] 金弟, 杨博, 刘杰,等. 复杂网络簇结构探测——基于随机游走的蚁群算法[J]. 软件学报, 2012, 23(3):451-464.JIN Di,YANG Bo,LIU Jie, et al. Ant colony optimization based on random walk for community detection in complex networks [J]. Journal of software, 2012, 23(3): 451-464.
[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. 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]. Journal of computer applications, 2014, 34(10): 2812-2815.
[12] YAO Y Y. Three-way decisions with probabilistic rough 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.
[16] YU H, ZHANG C, WANG G. A tree-based incremental overlapping clustering method using the three-way decision theory[J]. Knowledge-based systems, 2016, 91:189-203.
[17] YU H, WANG Y, JIAO P. A three-way decisions approach to density-based overlapping clustering [M]. Berlin Heidelberg:Springer, 2014: 92-109.
[18] YU H, ZHANG C, HU F. An Incremental Clustering Approach Based on Three-Way Decisions[C]//Rough Sets and Current Trends in Computing.Springer,Berlin Heidelberg,2014,8536: 152-159.
[19] LIU Y, PAN L, JIA X, et al. Three-way decision based overlapping community detection[C]//Rough Sets and Knowledge Technology, 2013,8171: 279-290.
[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 representation of decision-theoretic rough set model[J]. International journal of approximate reasoning, 2014, 55(1):156-166.
[23] QIAN Y, ZHANG H, SANG Y, et al. Multi-granulation decision-theoretic rough sets[J]. International journal of approximate reasoning, 2014, 55(1): 225-237.
[24] NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks[J]. Physical review E, 2004, 69(2): 026113.
[25] 贾修一, 李伟湋, 商琳,等. 一种自适应求三枝决策中决策阈值的算法[J]. 电子学报, 2011, 39(11):2520-2525. JIA Xiuyi, LI Weiwei, SHANG Lin,et al. An adaptive learning parameters algorithm in three-way decision-throretic rough set model[J]. Chinese journal of electronics, 2011, 39(11): 2520-2525
[26] LEICHT E A, HOLME P, NEWMAN M E J. Vertex similarity in networks[J]. Physical review E, 2006, 73(2): 026120.
[27] RAGHAVAN U N, Albert R, Kumara S. Near linear time algorithm to detect community structures in large-scale networks [J]. Physical reviewe, 2007, 76(3): 036106.
- 相似文献/References:
-
[1]王 龙,伏 锋,陈小杰,等.复杂网络上的群体决策[J].智能系统学报,2008,3(2):95.
WANG Long,FU Feng,CHEN Xiao-jie,et al.Collective decision-making over complex networks[J].CAAI Transactions on Intelligent Systems,2008,3():95.
[2]夏承遗,刘忠信,陈增强,等.复杂网络上的传播动力学及其新进展[J].智能系统学报,2009,4(5):392.[doi:10.3969/j.issn.1673-4785.2009.05.002]
XIA Cheng-yi,LIU Zhong-xin,CHEN Zeng-qiang,et al.Transmission dynamics in complex networks[J].CAAI Transactions on Intelligent Systems,2009,4():392.[doi:10.3969/j.issn.1673-4785.2009.05.002]
[3]孙世温,夏承遗,王莉.基于复杂网络的软件结构度量方法综述[J].智能系统学报,2011,6(3):208.
SUN Shiwen,XIA Chengyi,WANG Li.Survey of the measurement of software structures based on complex networks[J].CAAI Transactions on Intelligent Systems,2011,6():208.
[4]赵敬,夏承遗,孙世温,等.复杂网络上同时考虑感染延迟和非均匀传播的SIR模型[J].智能系统学报,2013,8(2):128.[doi:10.3969/j.issn.1673-4785.201210027]
ZHAO Jing,XIA Chengyi,SUN Shiwen,et al.A novel SIR model with infection delay and nonuniform transmission in complex networks[J].CAAI Transactions on Intelligent Systems,2013,8():128.[doi:10.3969/j.issn.1673-4785.201210027]
[5]仇建平,陈立潮,潘理虎.牵制控制下复杂网络的同步性研究[J].智能系统学报,2014,9(6):734.[doi:10.3969/j.issn.1673-4785.201311014]
QIU Jianping,CHEN Lichao,PAN Lihu.Synchronization in complex networks via pinning control[J].CAAI Transactions on Intelligent Systems,2014,9():734.[doi:10.3969/j.issn.1673-4785.201311014]
[6]刘富,姜奕含,邹青宇.复杂网络结构比对算法研究进展[J].智能系统学报,2015,10(4):508.[doi:10.3969/j.issn.1673-4785.201408006]
LIU Fu,JIANG Yihan,ZOU Qingyu.Advances in algorithms for construction alignment of complex networks research[J].CAAI Transactions on Intelligent Systems,2015,10():508.[doi:10.3969/j.issn.1673-4785.201408006]
[7]晁永翠,纪志坚,王耀威,等.复杂网络在路形拓扑结构下可控的充要条件[J].智能系统学报,2015,10(4):577.[doi:10.3969/j.issn.1673-4785.201411031]
CHAO Yongcui,JI Zhijian,WANG Yaowei,et al.Necessary and sufficient conditions for the controllability of complex networks with path topology[J].CAAI Transactions on Intelligent Systems,2015,10():577.[doi:10.3969/j.issn.1673-4785.201411031]
[8]王景丽,许立波,庞超逸.复杂网络中的在线社交网络演化模型[J].智能系统学报,2015,10(6):949.[doi:10.11992/tis.201507042]
WANG Jingli,XU Libo,PANG Chaoyi.Evolution model of online social networks based on complex networks[J].CAAI Transactions on Intelligent Systems,2015,10():949.[doi:10.11992/tis.201507042]
[9]赵姝,赵晖,陈洁,等.基于社团结构的多粒度结构洞占据者发现及分析[J].智能系统学报,2016,11(3):343.[doi:10.11992/tis.201603048]
ZHAO Shu,ZHAO Hui,CHEN Jie,et al.Recognition and analysis of structural hole spanner in multi-granularitybased on community structure[J].CAAI Transactions on Intelligent Systems,2016,11():343.[doi:10.11992/tis.201603048]
[10]郑文萍,张浩杰,王杰.基于稠密子图的社区发现算法[J].智能系统学报,2016,11(3):426.[doi:10.11992/tis.201603045]
ZHENG Wenping,ZHANG Haojie,WANG Jie.Community detection algorithm based on dense subgraphs[J].CAAI Transactions on Intelligent Systems,2016,11():426.[doi:10.11992/tis.201603045]
[11]李伟,杨晓峰,张重阳,等.复杂网络社团的投影聚类划分[J].智能系统学报,2011,6(1):57.
LI Wei,YANG Xiaofeng,ZHANG Chongyang,et al.A clustering method for community detection on complex networks[J].CAAI Transactions on Intelligent Systems,2011,6():57.
备注/Memo
收稿日期:2017-05-12。
基金项目:国家“863”计划项目（2015AA124102）；国家自然科学基金项目（61673020，61602003，61402006）；安徽省自然科学基金项目（1508085MF113，1708085QF156，1708085QF143，1708085MF163）；安徽省高等学校省级自然科学基金重点项目（KJ2013A016，KJ2016A016）；教育部人文社科青年基金项目（14YJC860020）.
作者简介:方莲娣,女,1992年生,硕士研究生,主要研究领域为三支决策和机器学习;张燕平,女,1962年生,教授,博士,主要研究方向为粒计算、智能计算、机器学习。获发明专利2项,发表学术论文80余篇;陈洁,女,1982年生,副教授,博士,主要研究方向为智能计算、机器学习、三支决策。发表学术论文10余篇。
通讯作者:张燕平.E-mail:zhangyp2@gmail.com.
更新日期/Last Update:
2017-06-25