第6卷第1期 智能系统学报 Vol.6 No.1 2011年2月 CAAI Transactions on Intelligent Systems Feb.2011 doi:10.3969/i.issn.1673-4785.2011.01.007 复杂网络社团的投影聚类划分 李伟，杨晓峰，张重阳，汤可宗，杨静宇 （南京理工大学计算机系，江苏南京210094) 摘要：社团结构划分对研究复杂网络有重要作用，由于该问题的复杂性，复杂网络中的社团划分问题成为近期的 一个研究热点.从经典数据分析的角度研究了复杂网络的社团结构，首先依据网络的拓扑信息，将网络节点投影成 高维空间的点，使得一个网络对应到高维空间中的一个点分布；接着使用主分量分析方法PCA对高维点分布降维， 保留点群分布的主要结构信息；再通过K-means聚类结果来推断网络的社团结构.基于2-mode数据和1-mode网络 数据实验表明，该方法可以快速、可靠地找出网络的社团将经典数据分析的聚类方法应用到网络分析中，验证了该 思路的有效性，为网络社团分析提供一个新视角. 关键词：复杂网络：社团划分：聚类：主分量分析 中图分类号：1P311;TP393;N94文献标识码：A文章编号：16734785(2011)010057-06 A clustering method for community detection on complex networks LI Wei,YANG Xiaofeng,ZHANG Chongyang,TANG Kezong,YANG Jingyu (Department of Computer Science,Nanjing University of Science and Technology,Nanjing 210094,China) 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 commu- nities 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. Keywords:complex networks;community detection;cluster;PCA 近10年来，伴随着互联网的普及，计算技术的 样原来多样的复杂系统就可以从一个通用的网络视 发展，人们共享和处理大量数据的能力得到很大提 角来研究，称之为“复杂网络”研究[16 高，这使得需要大量现实数据支撑的复杂系统的实 复杂网络方法被广泛地应用到各个研究领域， 证研究成为可能.研究者采用整体研究模式，以探索 比如社会学中人际交互网络、合作网络、商业网的研 现实系统的宏观性质为目标，在多个学科领域取得 究，信息技术领域的文献索引网、互联网、万维网研 了重要进展3].特别地，通过忽略原系统中各个体 究，生物学中的蛋白质作用网络、神经网络、捕食网 自身细节，将组成系统的个体抽象为网络节点，即无 等的研究46].通过这样一个独特的研究视角，大量 论是细胞还是社会中的成员，一律看作是无属性的 实证研究证实了复杂网络模型在自然界和人类社会 节点，再将它们之间的相互关系抽象成网络的边，这 中的普遍性和有效性，而且来自于不同领域的复杂 系统惊奇地呈现出一些相同的性质，其中最具有代 收稿日期：2010-05-24 基金项目：国家自然科学基金资助项目(60632050,60873151). 表性的成果有Wats小世界效应]和Barabasi无标 通信作者：杨静宇.E-mai:yangiy@mail.just.edu.cm. 度特征[8