第1期 李伟，等：复杂网络社团的投影聚类划分 ·59 个NP-hard问题).许多实际算法存在着需要预设 1,2,…,P5 参数，选择社团尺度，或者每次只能二分网络等限 2)当距离越大时，节点间的影响越小，计算距 制16，因而，网络中的社团划分问题仍然是一个挑 离的倒数1/d,作为节点间影响力度量； 战.本文从一个新的角度考虑网络划分问题：首先将 3)节点i对p个基准点的影响力向量为f:= 网络投影成高维空间的一个数据分布，接着使用主 （1/da,…,1/dn),当基准点选取的具有充分代表性 分量方法抽取主要分布结构，最后通过K-means算 时∫：可以表示节点i的网络影响力，向量∫将节点 法聚类低维空间中的数据，进而反推原网络的社团 i投影到高维度量空间. 结构. 2.2PCA降维 在得到所有n个网络节点的影响力向量后，构 2网络社团划分的投影聚类算法 建p×n影响矩阵F=[fif2…fn].再使用主分量分 近来，数据分析方法被有效地应用在网络分析 析PCA对矩阵F作降维，抽取主要结构信息， 领域719)，文献[19]首先将网络投影成高维空间的 1)首先在p维测量空间R”中计算F的标准化 点群分布，然后使用数据分析的主分量分析(PCA) 矩阵X,X的行均值为0，方差为1. 来抽取点群的主结构，并依据点群结构特征来反推 2)计算X的协方差矩阵C=Xx,对C作奇异 原网络的结构属性，结果表明，该方法可以重现复杂 值分解： 网络研究领域中mall-world网、scale-free网、nter C=Xx=(UV)(VΣU)=UAU net的层次结构等经典结果.在目前网络分析方法的 3)选择U的前q列记作U,计算R=U,X,R 研究尚未成熟时，通过将网络问题转化成一个传统 即为X的q维投影. 的数据分析问题，并有效地利用数据分析领域中经 接着用经典的K-means算法[2]对网络低维投 典方法来解决网络问题，具有广泛的实际意义， 影点R作聚类分析，将同一类的点所对应的原网络 本文沿用上述思路，首先将网络节点投影成高 顶点划分到个社团. 维空间点，接着使用P℃A对生成的点分布降维，最 3实验 后采用K-means方法聚类低维空间点，再根据聚类 结果来划分网络社团，方法原理见图2 3.1数据集 社横 我们使用了2个数据集作为实验数据，分别是 (a) 南方女士数据集DGC和空手道俱乐部数据集Za chary. 南方女士数据集是美国5位民族学者于20世 纪30年代在研究一个南部小镇阶层时收集的，根据 几位收集者的姓名首字母简称为DCG2I].DGC数 节点投影 据记录了9个月期间，18位女士(P1~P18)参加14 h 数据降维 件非正式的社会活动(E1~E14)的情况，是一个反 应行动者与事件之间关系的2-mode数据集.DCG 数据集的网络表示见图3，矩阵表示见表1，其中 ‘X’表示参加了该活动. 聚类 图2网络社团结构即聚类划分算法 Fig.2 Network community structure and illustra- tion of clustering algorithm 2.1节点投影 首先度量网络节点对网络的影响力，并依据节点 的影响力度量将其投影到度量空间，具体步骤如下， 图3南方女士数据集DGG的网络结构 1)随机选择p个网络节点作为度量基准点，计 Fig.3 Dllustration of DGG network 算当前度量节点到p个基准点的图论距离d;j=