一種新的基于粗糙集K-均值的社區(qū)發(fā)現(xiàn)方法

張?jiān)评?/>
	<meta name=; 劉宇

doi:10.11999/JEIT160516

一種新的基于粗糙集K-均值的社區(qū)發(fā)現(xiàn)方法

doi: 10.11999/JEIT160516 cstr: 32379.14.JEIT160516

張?jiān)评?/a>¹,

吳斌¹,
劉宇¹

基金項(xiàng)目:

國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃(2013CB329606)，北京市共建項(xiàng)目

計(jì)量
- 文章訪問數(shù): 1560
- HTML全文瀏覽量: 270
- PDF下載量: 474
- 被引次數(shù): 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

摘要

摘要: 針對(duì)許多社區(qū)發(fā)現(xiàn)方法將社區(qū)看作一個(gè)集合而無(wú)法描述社區(qū)模糊區(qū)域的問題，該文提出一種基于粗糙集理論的社區(qū)發(fā)現(xiàn)方法。該方法將社區(qū)看作兩個(gè)集合，即社區(qū)的下近似集和上近似集，來(lái)刻畫社區(qū)的模糊區(qū)域。該方法首先選擇K個(gè)節(jié)點(diǎn)作為社區(qū)的中心節(jié)點(diǎn)，然后根據(jù)節(jié)點(diǎn)與社區(qū)中心之間的距離將節(jié)點(diǎn)關(guān)聯(lián)到社區(qū)中心節(jié)點(diǎn)形成社區(qū)，接著重新計(jì)算社區(qū)的中心點(diǎn)及節(jié)點(diǎn)的社區(qū)標(biāo)簽，如此迭代直到收斂。通過(guò)公開數(shù)據(jù)集和仿真數(shù)據(jù)集驗(yàn)證了該方法在社區(qū)發(fā)現(xiàn)方面的可行性和有效性。
- 社交網(wǎng)絡(luò)分析 /
- 社區(qū)發(fā)現(xiàn) /
- 粗糙集 /
- 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全文

參考文獻(xiàn)(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.

劉陽(yáng), 季新生, 劉彩霞. 一種基于邊界節(jié)點(diǎn)識(shí)別的復(fù)雜網(wǎng)絡(luò)局部社區(qū)發(fā)現(xiàn)算法[J]. 電子與信息學(xué)報(bào), 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.

朱文強(qiáng), 伏玉琛. 一種基于粗糙集的社區(qū)結(jié)構(gòu)發(fā)現(xiàn)算法[J] . 計(jì)算機(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.

相關(guān)文章

施引文獻(xiàn)

資源附件(0)

訪問統(tǒng)計(jì)