[1]李伟,杨晓峰,张重阳,等.复杂网络社团的投影聚类划分[J].智能系统学报,2011,6(1):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,6(1):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,6(1):57-62.
复杂网络社团的投影聚类划分
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
6
期数:
2011年第1期
页码:
57-62
栏目:
学术论文—人工智能基础
出版日期:
2011-02-25
- Title:
- A clustering method for community detection on complex networks
- 文章编号:
- 1673-4785(2011)01-0057-06
- Keywords:
- complex networks; community detection; cluster; PCA
- 分类号:
- TP311；TP393;N94
- 文献标志码:
- A
- 摘要:
- 社团结构划分对研究复杂网络有重要作用，由于该问题的复杂性，复杂网络中的社团划分问题成为近期的一个研究热点.从经典数据分析的角度研究了复杂网络的社团结构，首先依据网络的拓扑信息，将网络节点投影成高维空间的点，使得一个网络对应到高维空间中的一个点分布；接着使用主分量分析方法PCA对高维点分布降维，保留点群分布的主要结构信息；再通过Kmeans聚类结果来推断网络的社团结构.基于2mode数据和1mode网络数据实验表明，该方法可以快速、可靠地找出网络的社团.将经典数据分析的聚类方法应用到网络分析中，验证了该思路的有效性，为网络社团分析提供一个新视角.
- 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 highdimensional space, and the network was associated with a data cloud. Second, principal component analysis (PCA) was used to reduce the highdimensional data cloud into a lowdimensional one, which kept the main structural information. Third, Kmeans 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 (2mode) and Zachary (1mode) 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］. ［20100520］. 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): 12751335.
［3］汪秉宏,周涛,何大韧. 统计物理与复杂系统研究最近发展趋势分析［J］.中国基础科学, 2005, 7(3): 3743.
WANG Binghong, ZHOU Tao, HE Daren. The trend of recent research on statistical physics and complex systems［J］. China Basic Science, 2005, 7(3): 3743.
［4］ALBERT R, BARABASI A L. Statistical mechanics of complex networks［J］. Reviews of Modern Physics, 2002, 74(1): 4797.
［5］NEWMAN M E J. The structure and function of complex networks［J］. SIAM Review, 2003, 45(2): 167256.
［6］BOCCALETTI S, LATORA V, MORENO Y, et al. Complex networks: structure and dynamics［J］. Physics Reports, 2006, 424(4/5): 175308.
［7］WATTS D J, STROGATZ S H. Collective dynamics of ‘smallworld’ networks［J］. Nature, 1998, 393(6638): 440442.
［8］BARABASI A L, ALBERT R. Emergence of scaling in random networks［J］. Science, 1999, 286(5439): 509512.
［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): 78217826.
［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)： 75174.
［12］解㑇,汪小帆.复杂网络中的社团结构分析算法研究综述［J］.复杂系统与复杂性科学, 2005, 2(3): 112.
XIE Zhou, WANG Xiaofan. An overview of algorithms for analyzing community structure in complex networks［J］. Complex Systems and Complexity Science, 2005, 2(3): 112.
［13］KERNIGHAN B W, LIN S. A efficient heuristic procedure for partitioning graphs［J］. Bell System Technical Journal, 1970, 49(2): 291307.
［14］FIEDLER M. Algebraic connectivity of graphs［J］. Czech Math Journal, 1973, 23(98): 298305.
［15］BRANDES U, DELLING D, GAERTLER M, et al. Maximizing modularity is hard［EB/OL］. (20060830)［20100520］. 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): 3641.
［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): 167242.
［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: 19071916.
［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: 114121.
［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: 452473.
［23］FREEMAN L. Dynamic social network modeling and analysis［M］. Washington, DC, USA: The National Academic Press, 2003: 3997.
- 相似文献/References:
-
[1]王 龙,伏 锋,陈小杰,等.复杂网络上的群体决策[J].智能系统学报,2008,3(2):95.
WANG Long,FU Feng,CHEN Xiao-jie,et al.Collective decision-making over complex networks[J].CAAI Transactions on Intelligent Systems,2008,3():95.
[2]夏承遗,刘忠信,陈增强,等.复杂网络上的传播动力学及其新进展[J].智能系统学报,2009,4(5):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,4():392.[doi:10.3969/j.issn.1673-4785.2009.05.002]
[3]孙世温,夏承遗,王莉.基于复杂网络的软件结构度量方法综述[J].智能系统学报,2011,6(3):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,6():208.
[4]赵敬,夏承遗,孙世温,等.复杂网络上同时考虑感染延迟和非均匀传播的SIR模型[J].智能系统学报,2013,8(2):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,8():128.[doi:10.3969/j.issn.1673-4785.201210027]
[5]仇建平,陈立潮,潘理虎.牵制控制下复杂网络的同步性研究[J].智能系统学报,2014,9(6):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,9():734.[doi:10.3969/j.issn.1673-4785.201311014]
[6]刘富,姜奕含,邹青宇.复杂网络结构比对算法研究进展[J].智能系统学报,2015,10(4):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,10():508.[doi:10.3969/j.issn.1673-4785.201408006]
[7]晁永翠,纪志坚,王耀威,等.复杂网络在路形拓扑结构下可控的充要条件[J].智能系统学报,2015,10(4):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,10():577.[doi:10.3969/j.issn.1673-4785.201411031]
[8]王景丽,许立波,庞超逸.复杂网络中的在线社交网络演化模型[J].智能系统学报,2015,10(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,10():949.[doi:10.11992/tis.201507042]
[9]赵姝,赵晖,陈洁,等.基于社团结构的多粒度结构洞占据者发现及分析[J].智能系统学报,2016,11(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,11():343.[doi:10.11992/tis.201603048]
[10]郑文萍,张浩杰,王杰.基于稠密子图的社区发现算法[J].智能系统学报,2016,11(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,11():426.[doi:10.11992/tis.201603045]
[11]方莲娣,张燕平,陈洁,等.基于三支决策的非重叠社团划分[J].智能系统学报,2017,12(3):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,12():293.[doi:10.11992/tis.201705013]
备注/Memo
收稿日期：2010-05-24.
基金项目：国家自然科学基金资助项目(60632050,60873151).
通信作者：杨静宇.
E-mail:yangjy@mail.njust.edu.cn.
作者简介：
李伟，男，1978年生，博士.主要研究方向为复杂网络、模式识别、机器学习；杨晓峰，男，1982年生，博士，主要研究方向为网络安全、人工智能；杨静宇，男，1941年生，教授，博士生导师，教育部图像信息处理与智能控制重点实验室学术委员会委员，国际信息处理联合会（IFIP）观察员.主要研究方向为模式识别、智能机器人、智能系统.曾获奖14 项， 其中国家级2项，省部级12 项.发表学术论文300余篇，出版论（译）著7部；杨静宇，男，1941年生，教授，博士生导师，教育部图像信息处理与智能控制重点实验室学术委员会委员，国际信息处理联合会（IFIP）观察员.主要研究方向为模式识别、智能机器人、智能系统.曾获奖14 项， 其中国家级2项，省部级12 项.发表学术论文300余篇，出版论（译）著7部.
更新日期/Last Update:
2011-04-13