穆宝良 李晋
摘 要:本文对复杂网络的社团发现问题进行研究,分析社团發现问题和聚类问题的相似性,使用自适应仿射传播聚类算法对社团发现问题进行求解,给出了算法的实例,针对算法中的不同参数进行测试比较。结果表明算法具有较好的准确率和运行效率。
关 键 词:复杂网络;社团发现;自适应仿射传播
一、引言
复杂网络是复杂系统研究的重要领域,取得了大量的研究成果[1-3]。网络结构的社团划分是复杂网络新的研究方向。复杂网络的社团可以定义为网络中的一组节点,组内节点之间具有较高的相似度,组间节点具有较低的相似度[4]。社团结构通常对应于网络中的某一功能单元,例如,万维网中不同社团代表不同主题的网页[5];引文网中不同社团代表了不同的研究领域[6]。
根据社团发现过程中社团形成方式的不同,社团发现大体可以分成四类过程:凝聚过程、分裂过程、搜索过程和其他过程。凝聚过程将网络中每一个定点设为一个社团,使用设定的度量标准,将相似度高的或相近的社团合并,重新计算,直到所有定点聚集成一个社团。分裂过程与凝聚过程相反,从所有定点组成的大社团出发,进行分裂,直到每个节点组成一个社团。搜索过程是一个逐步优化目标的过程。其他方法主要有谱分析等。本文使用自适应仿射传播聚类[7]方法求解社团发现问题,相比传统聚类方法,该方法不需要事先指定分类的个数且具有较快的运行速度。
二、基本定义
社团:目前为止,关于社团还没有统一的定义。比较常用的有基于链接频度的定义,网络分组后,即组内的链接稠密,组间的链接稀疏。还有基于连通性的定义,即将全连通子图定义为派系,所以也被称为基于派系的定义,派系的定义也可以通过放宽路径长度进行弱化。上述两个定义都是定性的定义,实践中还有定量的定义,比如使用Girvan和Newman定义的模块化函数来定义社团。
聚类算法:聚类是一个将数据集分类的过程,是数据挖掘领域中使用的技术,用于发现大规模数据中隐藏的模式和规律。聚类方法融合了多种技术,其应用领域也已超出了数据挖掘的范围。聚类分析所解决的问题与社团发现问题具有相似的特性,所以社团结构也可以被称为复杂网络中的聚类。聚类分析的理论和技术可以应用到复杂网络社团发现求解的问题中。
相似度:相似度是两个节点属性相似的程度。对于网络中的节点a和b,当以b为聚类中心时,a和b的相似度记为S(a,b)。相似度可以是对称的,即S(a,b)=S(b,a),也可以是不对称的,即二者不等。一般可以使用欧式距离来定义相似度,比如。将相似度定义为负值,是因为较大的负值说明二者的距离较小,方便程序的计算。
参考度:节点成为聚类中心的可能性定义为参考度。参考度越大,节点作为聚类中心的可能性也越大。节点a的参考度记为P(a)或S(a,a)。参考度的值会影响聚类的数量,也就是所划分出的社团的数量。如果初始时对中心点没有任何限制,可以取所有点的参考度相等,如果取输入适应度的中值,则社团数量中等。
吸引度:描述使用节点k作为节点i的聚类中心的适合程度,记为R(i,k),为从节点k发送到节点i的消息。
归属度:描述节点i选择节点k作为聚类中心的适合程度,记为A(i,k),为从节点i向节点k发送的消息。
阻尼系数:用来控制迭代过程中的收敛,阻尼系数取不同值时,迭代过程的收敛和振荡过程也不同。
三、聚类方法
自适应仿射传播聚类根据输入数据点之间的相似度进行聚类。设输入N个数据点,可以将输入数据点的相似度表示成N×N的矩阵S,S中的值S(i,j)为上面定义的相似度。与传统的聚类方法不同,算法不需要指定生成聚类的数量,而是使用所有输入点作为起始聚类,进行求解。相似度矩阵对角线上的值S(k,k)为前面定义的适应度。本文使用节点输入相似度的中值作为适应度的初始值。算法运行过程中传递两种类型的消息,吸引度和归属度。吸引度和归属度也以矩阵的形式表示。吸引度大说明节点作为聚类中心的可能性大,归属度大说明节点选择对应节点为聚类中心的可能性大。自适应仿射传播聚类算法迭代计算所有点的吸引度和归属度。直到产生若干个聚类中心,且所有数据点都找到聚类中心为止。
吸引度和归属度如下公式计算:
R(i,k)=S(i,k)-max{A(i,j)+S(i,j)} j≠k
R(k,k)=P(k)-max{A(k,j)+S(k,j)} j≠k
A(i,k)=min{0,R(k,k)+ j≠i且j≠k
根据上面公式,当参考度较大使得R(k, k)较大时, 计算所得的归属度A(i, k) 的值相应较大, 增加了k作为聚类中心的可能性; 具有较大参考度值的节点越多,聚类的数量也越多。所以,初始参考度值的大小最终聚类的数量有较大的影响。
自适应仿射传播聚类算法计算过程可以描述如下:
1.初始化:计算相似度矩阵S,计算参考度P。设置最大迭代次数。转步骤2。
2.计算归属度矩阵R值和吸引度A的值,迭代次数加1,如果达到最大迭代次数,转步骤3,否则继续步骤2。
3.使用R(k,k)+A(k,k)的值来判断是否为聚类中心。如果所计算的值大于0,则K点为聚类中心。
四、社团发现求解算法
使用上面的算法,可以求解社团发现问题,求解过程中我们使用阻尼系数lam更新吸引度和归属度,公式如下:
Ri=(1-lam)* Ri+lam *Ri-1
Ai=(1-lam) * Ai+lam * Ai-1
算法输入:
节点相似度s(i,k)
节点的参考度p(k):
算法输出:
社团的个数M
算法伪代码:
N←size(S,1);A←zeros(N,N);R←zeros(N,N);//初始化信息
S=S+1e-12*randn(N,N)*(max(S(:))-min(S(:)));
lam←0.5;
for iter←l:100,
//计算责任度
Rold←R;
AS←A+S;[Y,I]←max(AS,[],2);
for i←l:N,AS(i,I(i))←-realmax;end;
[Y2,I2]←max(AS,[],2);
R←S-repmat(Y,[l,N]);
for i←l:N,R(i,I(i))←S(i,I(i))-Y2(i);end;
R←(1-1am)*R+lam*Rold;//责任度
//计算合适度
Aold←A;
Rp←max(R,O);for k←l:N,Rp(k,k)←R(k,k);end;
A←repmat(sum(Rp,1),[N,1])-Rp;
dA←diag(A);A←min(A,O);for k←l:N,A(k,k)←dA(k);end;
A←(1-1am)*A+lam*Aold;//合适度
end;
E←R十A;
I←find(diag(E)>O);M←length(I);//聚类中心
[tmp c]←max(S(:,I),[],2);c(I)←1:M;idx←I(c);
我们使用Java语言实现了上述算法,使用二维空间中20个随机生成的数据点,将P值设置为S矩阵的中值,最大迭代次数设置成1000,以社团发现求解算法进行计算,最终分类结果如图1所示。
算法运行过程中,我们针对不同的阻尼系数lam进行了实验,发现当lam值较小时会得到较快的收敛速度,但是具有比较大的振荡;当lam值较大时具有较小的振荡,但是具有较慢的收敛速度。
五、结语
本文使用自适应仿射传播聚类算法进行社团发现问题的求解,给出了算法的描述和完整的实现。自适应仿射传播聚类方法具有较快的计算速度,对噪声不敏感,不需要事先设定社团的数量,能够较好的解决社团发现问题。实际的求解过程中,相似度的选择,阻尼系数的设定,都是需要解决的问题,社团求解过程中的重叠问题也是需要处理的重要问题,这些都是下一步的研究方向。
参考文献
[1] NewmanM E J.The structure and function of comp lex networks[J]. SIAM Review.2003,45(2):167-256.
[2] 吴金闪,狄增如.从统计物理看复杂网络研究[J].物理学进展.2004,24 (1):18-45.
[3] 周涛,等.复杂网络研究概述[J].物理.2005,34 (1):31-36.
[4] GirvanM,NewmanM E J.Community structure in social and biological networks.Proc Natl Acad Sci USA[J].2002,99:7821-7826.
[5] Adamic A L,Adar E.Friends and neighbors on the web[J].SocialNetworks.2003,25(3):211-230.
[6] Redner S.How popular is your paper? An emp irical study of the citation distribution[J].Eur Phys J B.1998,4:131-134.
[7] Frey B J,Dueck D. Clustering by passing messages between data points[J].Science.2007,315(5814):972-976.