[1]李伟,杨晓峰,张重阳,等.复杂网络社团的投影聚类划分[J].智能系统学报,2011,(01):57-62.
 LI Wei,YANG Xiaofeng,ZHANG Chongyang,et al.A clustering method for community detection on complex networks[J].CAAI Transactions on Intelligent Systems,2011,(01):57-62.
点击复制

复杂网络社团的投影聚类划分(/HTML)
分享到:

《智能系统学报》[ISSN:1673-4785/CN:23-1538/TP]

卷:
期数:
2011年01期
页码:
57-62
栏目:
出版日期:
2011-02-25

文章信息/Info

Title:
A clustering method for community detection on complex networks
文章编号:
1673-4785(2011)01-0057-06
作者:
李伟杨晓峰张重阳汤可宗杨静宇
南京理工大学 计算机系,江苏 南京 210094
Author(s):
LI Wei YANG Xiaofeng ZHANG Chongyang TANG Kezong YANG Jingyu
Department of Computer Science, Nanjing University of Science and Technology, Nanjing 210094, China
关键词:
复杂网络社团划分聚类主分量分析
Keywords:
complex networks community detection cluster PCA
分类号:
TP311;TP393;N94
文献标志码:
A
摘要:
社团结构划分对研究复杂网络有重要作用,由于该问题的复杂性,复杂网络中的社团划分问题成为近期的一个研究热点.从经典数据分析的角度研究了复杂网络的社团结构,首先依据网络的拓扑信息,将网络节点投影成高维空间的点,使得一个网络对应到高维空间中的一个点分布;接着使用主分量分析方法PCA对高维点分布降维,保留点群分布的主要结构信息;再通过Kmeans聚类结果来推断网络的社团结构.基于2mode数据和1mode网络数据实验表明,该方法可以快速、可靠地找出网络的社团.将经典数据分析的聚类方法应用到网络分析中,验证了该思路的有效性,为网络社团分析提供一个新视角.
Abstract:
Community detection is important for understanding complex networks. Because of its high complexity, community detection in complex networks has recently attracted significant interest from research groups. In this work, a data analysis perspective was proposed for community detection on complex networks. First, based on the network topology, the nodes of the studied network were projected as data points in a highdimensional space, and the network was associated with a data cloud. Second, principal component analysis (PCA) was used to reduce the highdimensional data cloud into a lowdimensional one, which kept the main structural information. Third, Kmeans algorithms were used to find clusters of the data points in the reduced data cloud, which inferred the communities of the studied network. Experiments on datasets DGG (2mode) and Zachary (1mode) indicated that the proposed method can reveal network communities effectively. The proposed method provided a novel perspective of the community detection of complex networks.

参考文献/References:

[1]JASNY B R, ZAHN L M, MARSHALL E. Special online collection: complex systems and networks[EB/OL]. [20100520]. http://www.sciencemag.org/complexity/.
[2]DOROGOVTSEV S N, GOLTSEV A V, MENDES J F F. Critical phenomena in complex networks[J]. Reviews of Modern Physics, 2008, 80(4): 12751335.
[3]汪秉宏,周涛,何大韧. 统计物理与复杂系统研究最近发展趋势分析[J].中国基础科学, 2005, 7(3): 3743.
WANG Binghong, ZHOU Tao, HE Daren. The trend of recent research on statistical physics and complex systems[J]. China Basic Science, 2005, 7(3): 3743.
[4]ALBERT R, BARABASI A L. Statistical mechanics of complex networks[J]. Reviews of Modern Physics, 2002, 74(1): 4797. 
[5]NEWMAN M E J. The structure and function of complex networks[J]. SIAM Review, 2003, 45(2): 167256.
[6]BOCCALETTI S, LATORA V, MORENO Y, et al. Complex networks: structure and dynamics[J]. Physics Reports, 2006, 424(4/5): 175308.
[7]WATTS D J, STROGATZ S H. Collective dynamics of ‘smallworld’ networks[J]. Nature, 1998, 393(6638): 440442.
[8]BARABASI A L, ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509512.
[9]GIRVAN M, NEWMAN M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2001, 99(12): 78217826.
[10]NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks[J]. Physical Review E, 2004, 69(2): 026113.
[11]FORTUNATO S. Community detection in graphs[J]. Physics Reports, 2010, 486(3/4/5): 75174.
[12]解㑇,汪小帆.复杂网络中的社团结构分析算法研究综述[J].复杂系统与复杂性科学, 2005, 2(3): 112.
XIE Zhou, WANG Xiaofan. An overview of algorithms for analyzing community structure in complex networks[J]. Complex Systems and Complexity Science, 2005, 2(3): 112.
[13]KERNIGHAN B W, LIN S. A efficient heuristic procedure for partitioning graphs[J]. Bell System Technical Journal, 1970, 49(2): 291307.
[14]FIEDLER M. Algebraic connectivity of graphs[J]. Czech Math Journal, 1973, 23(98): 298305.
[15]BRANDES U, DELLING D, GAERTLER M, et al. Maximizing modularity is hard[EB/OL]. (20060830)[20100520]. http://arxiv.org/abs/physics/0608255.
[16]FORTUNATO S, BARTHELEMY M. Resolution limit in community detection[J]. Proceedings of the National Academy of Sciences of the United States of America, 2007, 104(1): 3641.
[17]COSTA L D F, RODRIGUES F A, TRAVIESO G, et al. Characterization of complex networks: a survey of measurements[J]. Advances in Physics, 2007, 56(1): 167242.
[18]LI Wei, YANG Jingyu. Comparing networks from a data analysis perspective[J]. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, 2009, 5: 19071916. 
[19]LI Wei, YANG Jingyu, HADDEN W C. Analyzing complex networks from a data analysis viewpoint[J]. Europhysics Letters, 2009, 88(6): 68007.
[20]DUDA R O, HART P E, STORK D G. Pattern classification[M]. New York, USA: John Wiley & Sons, Inc., 2001: 114121.
[21]DAVIS A, GARDNER B B, GARDNER M R. Deep south[M]. Chicago: The University of Chicago Press, 1941: 147.
[22]ZACHARY W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1977, 33: 452473.
[23]FREEMAN L. Dynamic social network modeling and analysis[M]. Washington, DC, USA: The National Academic Press, 2003: 3997.

相似文献/References:

[1]王 龙,伏 锋,陈小杰,等.复杂网络上的群体决策[J].智能系统学报,2008,(02):95.
 WANG Long,FU Feng,CHEN Xiao-jie,et al.Collective decision-making over complex networks[J].CAAI Transactions on Intelligent Systems,2008,(01):95.
[2]夏承遗,刘忠信,陈增强,等.复杂网络上的传播动力学及其新进展[J].智能系统学报,2009,(05):392.[doi:10.3969/j.issn.1673-4785.2009.05.002]
 XIA Cheng-yi,LIU Zhong-xin,CHEN Zeng-qiang,et al.Transmission dynamics in complex networks[J].CAAI Transactions on Intelligent Systems,2009,(01):392.[doi:10.3969/j.issn.1673-4785.2009.05.002]
[3]孙世温,夏承遗,王莉.基于复杂网络的软件结构度量方法综述[J].智能系统学报,2011,(03):208.
 SUN Shiwen,XIA Chengyi,WANG Li.Survey of the measurement of software structures based on complex networks[J].CAAI Transactions on Intelligent Systems,2011,(01):208.
[4]赵敬,夏承遗,孙世温,等.复杂网络上同时考虑感染延迟和非均匀传播的SIR模型[J].智能系统学报,2013,(02):128.[doi:10.3969/j.issn.1673-4785.201210027]
 ZHAO Jing,XIA Chengyi,SUN Shiwen,et al.A novel SIR model with infection delay and nonuniform transmission in complex networks[J].CAAI Transactions on Intelligent Systems,2013,(01):128.[doi:10.3969/j.issn.1673-4785.201210027]
[5]仇建平,陈立潮,潘理虎.牵制控制下复杂网络的同步性研究[J].智能系统学报,2014,(06):734.[doi:10.3969/j.issn.1673-4785.201311014]
 QIU Jianping,CHEN Lichao,PAN Lihu.Synchronization in complex networks via pinning control[J].CAAI Transactions on Intelligent Systems,2014,(01):734.[doi:10.3969/j.issn.1673-4785.201311014]
[6]刘富,姜奕含,邹青宇.复杂网络结构比对算法研究进展[J].智能系统学报,2015,(04):508.[doi:10.3969/j.issn.1673-4785.201408006]
 LIU Fu,JIANG Yihan,ZOU Qingyu.Advances in algorithms for construction alignment of complex networks research[J].CAAI Transactions on Intelligent Systems,2015,(01):508.[doi:10.3969/j.issn.1673-4785.201408006]
[7]晁永翠,纪志坚,王耀威,等.复杂网络在路形拓扑结构下可控的充要条件[J].智能系统学报,2015,(04):577.[doi:10.3969/j.issn.1673-4785.201411031]
 CHAO Yongcui,JI Zhijian,WANG Yaowei,et al.Necessary and sufficient conditions for the controllability of complex networks with path topology[J].CAAI Transactions on Intelligent Systems,2015,(01):577.[doi:10.3969/j.issn.1673-4785.201411031]
[8]王景丽,许立波,庞超逸.复杂网络中的在线社交网络演化模型[J].智能系统学报,2015,(6):949.[doi:10.11992/tis.201507042]
 WANG Jingli,XU Libo,PANG Chaoyi.Evolution model of online social networks based on complex networks[J].CAAI Transactions on Intelligent Systems,2015,(01):949.[doi:10.11992/tis.201507042]
[9]赵姝,赵晖,陈洁,等.基于社团结构的多粒度结构洞占据者发现及分析[J].智能系统学报,2016,(3):343.[doi:10.11992/tis.201603048]
 ZHAO Shu,ZHAO Hui,CHEN Jie,et al.Recognition and analysis of structural hole spanner in multi-granularitybased on community structure[J].CAAI Transactions on Intelligent Systems,2016,(01):343.[doi:10.11992/tis.201603048]
[10]郑文萍,张浩杰,王杰.基于稠密子图的社区发现算法[J].智能系统学报,2016,(3):426.[doi:10.11992/tis.201603045]
 ZHENG Wenping,ZHANG Haojie,WANG Jie.Community detection algorithm based on dense subgraphs[J].CAAI Transactions on Intelligent Systems,2016,(01):426.[doi:10.11992/tis.201603045]
[11]方莲娣,张燕平,陈洁,等.基于三支决策的非重叠社团划分[J].智能系统学报,2017,(03):293.[doi:10.11992/tis.201705013]
 FANG Liandi,ZHANG Yanping,CHEN Jie,et al.Three-way decision based on non-overlapping community division[J].CAAI Transactions on Intelligent Systems,2017,(01):293.[doi:10.11992/tis.201705013]

备注/Memo

备注/Memo:
收稿日期:2010-05-24.
基金项目:国家自然科学基金资助项目(60632050,60873151).
通信作者:杨静宇.
E-mail:yangjy@mail.njust.edu.cn.
作者简介:
李伟,男,1978年生,博士.主要研究方向为复杂网络、模式识别、机器学习.
杨晓峰,男,1982年生,博士,主要研究方向为网络安全、人工智能.
杨静宇,男,1941年生,教授,博士生导师,教育部图像信息处理与智能控制重点实验室学术委员会委员,国际信息处理联合会(IFIP)观察员,国家教委和人事部全国优秀留学回国人员,江苏省优秀学科带头人.主要研究方向为模式识别、智能机器人、智能系统.曾获奖14 项, 其中国家级2项,省部级12 项.发表学术论文300余篇,出版论(译)著7部.
更新日期/Last Update: 2011-04-13