|
|
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) |
|
|
Abstract 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.
|
Received: 23 May 2016
Published: 02 December 2016
|
|
Fund: The National Key Basic Research Program of China (2013CB329606), The Special Fund for Beijing Common Construction Project |
Corresponding Authors:
ZHANG Yunlei
E-mail: yunlei0518@126.com
|
|
|
|
[1] |
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.
|
[11] |
刘阳, 季新生, 刘彩霞. 一种基于边界节点识别的复杂网络局部社区发现算法[J]. 电子与信息学报, 2014, 36(12): 2809-2815. doi: 10.3724/SP.J.1146.2013.01955.
|
|
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.
|
[14] |
朱文强, 伏玉琛. 一种基于粗糙集的社区结构发现算法[J] . 计算机工程, 2011, 37(14): 41-43. doi: 10.3969/j.issn.1000- 3428.2011.14.012.
|
|
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.
|
[21] |
NEWMAN Mark. Network data[OL]. http://www-personal. umich.edu/~mejn/netdata/,2016.
|
|
|
|