A Novel Community Detection Method Based on Rough Set K-Means

ZHANG Yunlei; WU Bin; LIU Yu

doi:10.11999/JEIT160516

Volume 39 Issue 4

Apr. 2017

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2017 > 39(4): 770-777

ZHANG Yunlei, WU Bin, LIU Yu. A Novel Community Detection Method Based on Rough Set K-Means[J]. Journal of Electronics & Information Technology, 2017, 39(4): 770-777. doi: 10.11999/JEIT160516

Citation:

ZHANG Yunlei, WU Bin, LIU Yu. A Novel Community Detection Method Based on Rough Set K-Means[J]. Journal of Electronics & Information Technology, 2017, 39(4): 770-777. doi: 10.11999/JEIT160516

ZHANG Yunlei, WU Bin, LIU Yu. A Novel Community Detection Method Based on Rough Set K-Means[J]. Journal of Electronics & Information Technology, 2017, 39(4): 770-777. doi: 10.11999/JEIT160516

Citation:

ZHANG Yunlei, WU Bin, LIU Yu. A Novel Community Detection Method Based on Rough Set K-Means[J]. Journal of Electronics & Information Technology, 2017, 39(4): 770-777. doi: 10.11999/JEIT160516

PDF( 1312 KB)

A Novel Community Detection Method Based on Rough Set K-Means

doi: 10.11999/JEIT160516

Funds:

The National Key Basic Research Program of China (2013CB329606), The Special Fund for Beijing Common Construction Project

Received Date: 2016-05-23
Rev Recd Date: 2016-09-23
Publish Date: 2017-04-19

Abstract

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.
- Social network analysis,
- Community detection,
- Rough set,
- K-Means

FullText(HTML)

References(22)

References

FORTUNATO S. Community detection in graphs[J]. Physics Reports, 2010, 486(3-5): 75-174. doi: 10.1016/j.physrep.2009. 11.002.

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.

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.

WASSERMAN S and FAUST K. Social Network Analysis Methods and Applications[M]. Cambridge, UK, Cambridge University Press, 2010, Chapter 7.

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.

NEWMAN M E. Modularity and community structure in networks[J]. Proceedings of the National Academy of Sciences, 2006, 103(23): 8577-8582.

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.

PIZZUTI C. GA-Net: a genetic algorithm for community detection in social networks[J]. Parallel Problem Solving from NaturePPSN X. Berlin Heidelberg: Springer-Verlag, 2008, LNCS 5199:10811090. doi: 10.1007/978-3-540-87700-4_107.

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.

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.

刘阳, 季新生, 刘彩霞. 一种基于边界节点识别的复杂网络局部社区发现算法[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.

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.

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.

朱文强, 伏玉琛. 一种基于粗糙集的社区结构发现算法[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.

PAWLAK Z. Rough sets[J]. International Journal of Computer Information Sciences, 1982, 11(5): 341-356.

DNTSCH I and GEDIGA G. Handbook of Cluster Analysis [M]. Chapman Hall, 2016, Chapter 5.

DONGEN S. A clustering algorithm for graphs[R]. CWI, Amsterdam, The Netherlands, 2000.

RAND W M. Objective criteria for the evaluation of clustering methods[J]. Journal of the American Statistical Association, 1971, 66(336): 846-850.

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.

ANDREA L, SANTO F, and FILIPPO R. Benchmark graphs for testing community detection algorithms[J]. Physical Review E, 2008, 78(4): 561-570.

Relative Articles

Supplements(0)

Cited By

Proportional views