基于模糊聚类的多分辨率社区发现方法

doi:10.11999/JEIT161116

摘要
图/表
参考文献(35)
相关文章 (15)

全文: PDF (366 KB)
输出: BibTeX | EndNote (RIS)

摘要

针对网络结构的复杂性和群体划分的不确定性，该文提出一种基于模糊聚类的多分辨率社区结构发现方法。该方法用模糊方法来处理网络节点间的相似性，以实现社区结构的模糊划分。基于节点间的局部交互信息，考虑节点间的模糊关系和网络拓扑结构相似性传递，实现网络社区的层次聚类。并通过调节模糊参数，挖掘出不同分辨率下的社区结构。同时为了避免主观地确定社区数目，引入一种新的模块度以度量社区划分结果。实验证明该方法能够有效且稳定地揭示潜在的社区结构。

	服务

	把本文推荐给朋友
	加入我的书架
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	汪晓锋
	刘功申
	李建华

关键词 ：社交网络, 社区发现, 模糊聚类, 结构相似性

Abstract：Focusing on the complexity of network structure and the indeterminacy of community partition, this paper puts forward a novel fuzzy clustering method for uncovering community structures. In contrast to previous studies, the proposed method disposes the similarity of connecting vertices with fuzzy relation. Based on local interactive information, it considers the fuzzy relation between vertices and the transitive similarity in network topology to divide vertices into communities. In addition, multiresolution communities can be detected by adjusting fuzzy parameter. In order to avoid subjectivity in the selection of cluster number, a new modularity is introduced to evaluate the effectiveness of the clustering analysis. It is proved by experiments that the method is ef?cient and stable to detect underlying communities.

Key words： Social network Community structure Fuzzy clustering Structural similarity

收稿日期: 2016-10-20 出版日期: 2017-06-14

PACS:

TP391

基金资助:

国家973关键技术研究项目(2013CB329603)，国家自然科学基金(61472248, 61431008)

通讯作者: 刘功申：男，1974年生，博士，副教授，研究方向为自然语言处理、信息安全等. E-mail: lgshen@sjtu.edu.cn

作者简介: 汪晓锋：男，1984年生，博士生，研究方向为复杂网络、社交网络分析、数据挖掘. 刘功申：男，1974年生，博士，副教授，研究方向为自然语言处理、信息安全等. 李建华：男，1965年生，博士，教授，研究方向为计算机通信网、信息安全等.

引用本文:

汪晓锋,刘功申,李建华. 基于模糊聚类的多分辨率社区发现方法[J]. 电子与信息学报, 2017, 39(9): 2033-2039. WANG Xiaofeng, LIU Gongshen, LI Jianhua. Multiresolution Community Detection Based on Fuzzy Clustering. JEIT, 2017, 39(9): 2033-2039.

链接本文:

http://jeit.ie.ac.cn/CN/10.11999/JEIT161116 或 http://jeit.ie.ac.cn/CN/Y2017/V39/I9/2033

[1]	汪小帆, 李翔, 陈关荣. 网络科学导论[M]. 北京: 高等教育出版社, 2012: 1-27.
	WANG Xiaofan, LI Xiang, and CHEN Guanrong. Network Science: A Introduction[M]. Beijing: Higher Education Press, 2012: 1-27.
[2]	NEWMAN M E J. Complex systems: A survey[J]. American Journal of Physics, 2011, 79(8): 800-810. doi: 10.1119/ 1.3590372.
[3]	FORTUNAO S and DARKO H. Community detection in networks: A user guide[J]. Physics Reports, 2016, 659: 1-44. doi: 10.1016/j.physrep.2016.09.002.
[4]	ZHANG P, MOORE C, and NEWMAN M E J. Community detection in networks with unequal groups[J]. Physical Review E, 2016, 93(1): 012303. doi: 10.1103/PhysRevE.93. 012303.
[5]	NEWMAN M E J. Communities, modules and large-scale structure in networks[J]. Nature Physics, 2012, 8(1): 25-31. doi:10.1038/ nphys2162.
[6]	SCHAEFFER S E. Graph clustering[J]. Computer Science Review, 2007, 1(1): 27-64. doi: 10.1016/j.cosrev.2007.05.001.
[7]	MALLIAROS F D and VAZIRGIANNIS M. Clustering and community detection in directed networks: A survey[J]. Physics Reports, 2013, 533(4): 95-142. doi: 10.1016/j.physrep. 2013.08.002.
[8]	CLAUSET A, NEWMAN M E J, and MOORE C. Finding community structure in very large networks[J]. Physical Review E, 2004, 70(6): 066111. doi: 10.1103/PhysRevE.70. 066111.
[9]	LI Ming, DENG Youjin, and WANG Binghong. Clique percolation in random graphs[J]. Physical Review E, 2015, 92(4): 042116. doi: 10.1103/PhysRevE.92.042116.
[10]	LEE C, REID F, FCDAID A, et al. Detecting highly overlapping community structure by greedy clique expansion [C]. Proceeding of 4th SNA-KDD Workshop on Social Network Mining and Analysis, Washington DC, USA, 2010: 33-42.
[11]	AFSARMANESH N and MAGNANI M. Finding overlapping communities in multiplex networks[OL]. https://arxiv.org/ abs/1602.03746.2016.
[12]	YANG B and LIU J. Discovering global network communities based on local centralities[J]. ACM Transactions on the Web, 2008, 2(1): 1-32. doi: 10.1145/1326561.1326570.
[13]	NIKOLAEV A G, RAZIB R, and KUCHERIYA A. On efficient use of entropy centrality for social network analysis and community detection[J]. Social Networks, 2015, 40: 154-162. doi: 10.1016/j.socnet.2014.10.002.
[14]	NASCIMENTO M C V and CARVALHO A C. Spectral methods for graph clustering-A survey[J]. European Journal of Operational Research, 2011, 211(2): 221-231. doi: 10.1016/ j.ejor.2010.08.012.
[15]	YANG J and LESKOVEC J. Defining and evaluating network communities based on ground-truth[J]. Knowledge and Information Systems, 2015, 42(1): 181-213. doi: 10.1007/ s10115-013-0693-z.
[16]	XIANG Ju, HU Tao, ZHANG Yan, et al. Local modularity for community detection in complex networks[J]. Physica A: Statistical Mechanics and Its Applications, 2016, (443): 451-459. doi: 10.1016/j.physa.2015.09.093.
[17]	BLONDEL V D, GUILLAUME J L, LAMBIOTTE R, et al. Fast unfolding of communities in large networks[J]. Journal of Statistical Mechanics: Theory and Experiment, 2008, (10): P10008.
[18]	GOMEZ D, RODRIGUEZ J T, YANEZ J, et al. A new modularity measure for fuzzy community detection problems based on overlap and grouping functions[J]. Approximate Reasoning, 2016, 74: 88-107. doi: 10.1016/j.ijar. 2016.03.003.
[19]	AHN Y Y, BAGROW J P, and LEHMANN S. Link communities reveal multiscale complexity in networks[J]. Nature, 2010, 466(7307): 761-764. doi: 10.1038/nature09182.
[20]	DING Z, ZHANG X, SUN D, et al. Overlapping community detection based on network decomposition[J]. Scientific Reports, 2016, 6: 24115. doi: 10.1038/srep24115.
[21]	HUANG Lan, WANG Guishen, WANG Yan, et al. A link density clustering algorithm based on automatically selecting density peaks for overlapping community detection[J]. International Journal of Modern Physics B, 2016, 30(24): 1650167. doi: 10.1142/S0217979216501678.
[22]	NEWMAN M E J and GIRVAN M. Finding and evaluating community structure in networks[J]. Physical Review E, 2004, 69(2): 026113.
[23]	PAN Y, LI D H, LIU J G, et al. Detecting community structure in complex networks via node similarity[J]. Physica A: Statistical Mechanics and Its Applications, 2010, 389(14): 2849-2857. doi: 10.1016/j.physa. 2010.03.006.
[24]	PAPADOPOULOS F, KITSAK M, SERRANO M A, et al. Popularity versus similarity in growing networks[J]. Nature, 2012, 489(7417): 537-540. doi: 10.1038/nature11459.
[25]	RADICCHI F, CASTELLANO C, CECCONI F, et al. Defining and identifying communities in networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2004, 101(9): 2658-2663. doi: 10.1073/ pnas.0400054101.
[26]	XIE Jierui, KELLEY S, and SZYMANSKI B K. Overlapping community detection in networks: the state-of-the-art and comparative study[J]. ACM Computing Surveys (CSUR), 2013, 45(4): Article No. 43. doi: 10.1145/2501654.2501657.
[27]	XU Rui and WUNSCH D. Survey of clustering alogrithms[J]. IEEE Transactions on Neural Networks, 2005, 3(16): 645-678. doi: 10.1109/TNN.2005.845141.
[28]	陈水利, 李敬功, 王向公. 模糊集理论及其应用[M]. 北京: 科学出版社, 2005: 1-448.
	CHEN Shuili, LI Jinggong, and WANG Xianggong. Fuzzy Set Theory and Its Application[M]. Beijing: Science Press, 2005: 1-448.
[29]	ZADEH L A. Toward a generalized theory of uncertainty (GTU)-an outline[J]. Information Sciences, 2005, 172(1): 1-40.
[30]	BARALDI A and BLONDA P. A survey of fuzzy clustering algorithms for pattern recognition I[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 1999, 29(6): 778-785. doi: 10.1109/3477.809032.
[31]	DANON L, DIAZ-GUILERA A, DUCH J, et al. Comparing community structure identification[J]. Journal of Statistical Mechanics-Theory and Experiment, 2005, (9): P09008.
[32]	NEWMAN M. Network data[OL]. http://www-personal. umich.edu/~mejn/netdata. 2016. 7.
[33]	LANCICHINETTI A, FORTUNATO S, and RADICCHI F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E, 2008, 78(4): 046110. doi: 10.1103/PhysRevE. 78.046110.
[34]	PONS P and LATAPY M. Computing communities in large networks using random walks[C]. Proceeding of 20th International Symposium on Computer and Information Sciences, Turkey, 2005: 284-293. doi: 10.1007/11569596_31.
[35]	ROSVALL M and BERGSTROM C T. Maps of random walks on complex networks reveal community structure[J]. Proceedings of the National Academy of Sciences of the United States of America, 2008, 105(4): 1118-1123. doi: 10.1073/ pnas.0706851105.