[1]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]
Copy

Three-way decision based on non-overlapping community division

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 12 Number of periods: 2017 3 Page number: 293-300 Column: 学术论文—智能系统 Public date: 2017-06-25
Title:
Three-way decision based on non-overlapping community division
Author(s):
FANG Liandi1; 2;  ZHANG Yanping1; 2;  CHEN Jie1; 2;  WANG Qianqian3;  LIU Feng1; 2;  WANG Gang1; 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
Keywords:
complex network; community division; overlapping node; three-way decision; granulation coefficient; hierarchical clustering; community structure; node belonging degree
CLC:
TP301
DOI:
10.11992/tis.201705013
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.
Similar References:

Memo

-

Last Update: 2017-06-25

Copyright © CAAI Transactions on Intelligent Systems