一种新的基于粗糙集K-均值的社区发现方法

张云雷; 吴斌; 刘宇

doi:10.11999/JEIT160516

一种新的基于粗糙集K-均值的社区发现方法

doi: 10.11999/JEIT160516

基金项目:

国家重点基础研究发展计划(2013CB329606)，北京市共建项目

计量
- 文章访问数: 1498
- HTML全文浏览量: 255
- PDF下载量: 472
- 被引次数: 0
出版历程
- 收稿日期: 2016-05-23
- 修回日期: 2016-09-23
- 刊出日期: 2017-04-19

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

Funds:

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

摘要

摘要: 针对许多社区发现方法将社区看作一个集合而无法描述社区模糊区域的问题，该文提出一种基于粗糙集理论的社区发现方法。该方法将社区看作两个集合，即社区的下近似集和上近似集，来刻画社区的模糊区域。该方法首先选择K个节点作为社区的中心节点，然后根据节点与社区中心之间的距离将节点关联到社区中心节点形成社区，接着重新计算社区的中心点及节点的社区标签，如此迭代直到收敛。通过公开数据集和仿真数据集验证了该方法在社区发现方面的可行性和有效性。
- 社交网络分析 /
- 社区发现 /
- 粗糙集 /
- K-均值
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

HTML全文

参考文献(22)

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.

施引文献

资源附件(0)

访问统计