A Novel Community Detection Method Based on Rough Set K-Means
ZHANG Yunlei WU Bin LIU Yu
(Beijing Key Laboratory of Intelligent Telecommunications Software and Multimedia, Beijing University of Posts and Telecommunications, Beijing 100876, China)
Due to many community detection approaches regarding a community as one set of nodes which can not depict the vagueness of the community. A method based on rough set is proposed, it considers community as a lower and an upper approximation set which could depict the vagueness of the community. The method selects K nodes as the central nodes, then assembles iteratively nodes to their closest central nodes to form communities, and calculates subsequently a new central node in each community, around which to gather nodes again until convergence. Experimental results on public and synthetic networks verify the feasibility and effectiveness of the proposed method.
张云雷,吴斌,刘宇. 一种新的基于粗糙集K-均值的社区发现方法[J]. 电子与信息学报, 2017, 39(4): 770-777.
ZHANG Yunlei, WU Bin, LIU Yu. A Novel Community Detection Method Based on Rough Set K-Means. JEIT, 2017, 39(4): 770-777.
FORTUNATO S. Community detection in graphs[J]. Physics Reports, 2010, 486(3-5): 75-174. doi: 10.1016/j.physrep.2009. 11.002.
[2]
BEDI P and SHARMA C. Community detection in social networks[J]. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2016, 6(3): 115-135. doi: 10.1002/ widm.1178.
[3]
KROGAN N J, GERARD C, HAIYUAN Y, et al. Global landscape of protein complexes in the yeast saccharomyces cerevisiae[J]. Nature, 2006, 440(7084): 637-643.
[4]
WASSERMAN S and FAUST K. Social Network Analysis Methods and Applications[M]. Cambridge, UK, Cambridge University Press, 2010, Chapter 7.
[5]
KERNIGHAN B W and LIN S. An efficient heuristic procedure for partitioning graphs[J]. Bell Labs Technical Journal, 1970, 49(2): 291-307. doi: 10.1002/j.1538-7305.1970. tb01770.x.
[6]
NEWMAN M E. Modularity and community structure in networks[J]. Proceedings of the National Academy of Sciences, 2006, 103(23): 8577-8582.
[7]
BLONDEL V, GUILLAUME J, LAMBIOTTE R, et al. Fast unfolding of communities in large networks[J]. Journal of Statistical Mechanics Theory & Experiment, 2008, 30(2): 155-168.
[8]
PIZZUTI C. GA-Net: a genetic algorithm for community detection in social networks[J]. Parallel Problem Solving from Nature-PPSN X. Berlin Heidelberg: Springer-Verlag, 2008, LNCS 5199:1081-1090. doi:10.1007/978-3-540-87700-4_107.
[9]
USHA NANDINI R, RKA A, and SOUNDAR K. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2007, 76(3): 036106.
[10]
XIN Y, YANG J, and XIE ZQ. A semantic overlapping community detection algorithm based on field sampling[J]. Expert Systems with Applications, 2015, 42: 366-375. doi: 10.1016/j.eswa.2014.07.009.
LIU Yang, JI Xinsheng, and LIU Caixia. Detection local community structure based on the identification of boundary nodes in complex networks[J]. Journal of Electronics & Information Technology, 2014, 36(12): 2809-2815. doi: 10.3724/SP.J.1146.2013.01955.
[12]
SHAO Junming, HAN Zhichao, YANG Qinli, et al. Community detection based on distance dynamics[C]. Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, Sydney, 2015: 1075-1084.
[13]
WANG Z and WANG Z. Research in social network based on rough set clustering algorithm[J]. International Journal of Advancements in Computing Technology, 2012, 4(15): 295-301.
ZHU Wenqiang, and FU Shuchen. Community structure detection algorithm based on rough set[J]. Computer Engineering, 2011, 37(14): 41-43. doi: 10.3969/j.issn.1000- 3428.2011.14.012.
[15]
PAWLAK Z. Rough sets[J]. International Journal of Computer & Information Sciences, 1982, 11(5): 341-356.
[16]
DüNTSCH I and GEDIGA G. Handbook of Cluster Analysis [M]. Chapman & Hall, 2016, Chapter 5.
[17]
DONGEN S. A clustering algorithm for graphs[R]. CWI, Amsterdam, The Netherlands, 2000.
[18]
RAND W M. Objective criteria for the evaluation of clustering methods[J]. Journal of the American Statistical Association, 1971, 66(336): 846-850.
[19]
STREHL A, and GHOSH J. Cluster ensembles-a knowledge reuse framework for combining multiple partitions[J]. Journal of Machine Learning Research, 2002, 3(12): 583-617.
[20]
ANDREA L, SANTO F, and FILIPPO R. Benchmark graphs for testing community detection algorithms[J]. Physical Review E, 2008, 78(4): 561-570.
