复杂网络社区挖掘——改进的层次聚类算法-AET-电子技术应用

复杂网络社区挖掘——改进的层次聚类算法

来源：微型机与应用2011年第16期

郑浩原，黄战

（暨南大学信息科学技术学院计算机科学系，广东广州510632）

摘要： 社区挖掘算法研究是复杂网络分析领域的热点问题。传统层次聚类算法在复杂网络社区挖掘过程中，需要计算所有顶点对之间的相似度。针对这一缺点，在详述了常见相似度计算方法和顶点重要性度量方法的基础上，将ego角色的探测过程引入层次聚类算法，而后只计算其他顶点与ego顶点之间的相似度，提高了社区挖掘效率。最后在不同类型的现实网络中验证了算法的有效性。

关键词： 无线网络复杂网络社区挖掘层次聚类

Abstract：

Key words :

　复杂网络表示现实世界中具有网络结构特性的诸多系统,它通常具有显著的社区结构，同质顶点聚集在同一社区，异质顶点分布于不同社区，表现为社区内部顶点之间连接边稠密，社区之间连接边数量相对稀疏[1]。社区挖掘是复杂网络分析领域的热点问题，可以将现有的社区挖掘算法归纳为三大类[2]：基于优化的算法、启发式算法以及其他算法。基于相似度的层次聚类算法[3]属于其他算法，这类算法不需要任何先验知识就可以有效地发现复杂网络中的社区结构。当前的层次聚类算法的主要缺点是需要计算所有顶点对之间的相似度，时间复杂度为O(n2)，n表示图中顶点数量，不适用于大规模网络分析。针对这一缺点，受到社交网络分析相关方法的启发，本文提出一种改进的层次聚类算法。
   社交网络分析[4]是复杂网络分析的一个分支，社交网络中有一类Ego Networks，表现为有一个中心结点(即ego)，图中所有其他结点（称为alters）与中心结点直接连接，alter之间也有边相连。社会学理论[5]指出，关系紧密的角色之间相似度偏高，如果两个角色之间共同点越多，则这两者就越有可能是朋友或者具有紧密的联系。当与某确定角色比较，角色A与角色B的相似度值接近时，可以认为角色A与B具有某种同质性。基于这一理论，对层次聚类算法进行改进，在探测出网络中扮演ego角色顶点的前提下，计算其他顶点与ego的相似度，而不是计算所有顶点对之间的相似度，此种情况下，算法时间复杂度为O(n)，计算负荷与网络规模呈线性相关。实验结果表明，该算法可能在准确性上稍有不足，但是能有效降低网络分析规模、计算复杂度和大致发现网络中的社区结构。
1 算法准备
1.1 相似度计算
   相似度[3-4]是对图中顶点之间的相似或者相异程度的度量，是层次聚类算法的核心概念，可以大致将现有的相似度计算方法分为三大类：
   第一类，可以将顶点嵌入到n维欧式空间中，通过给顶点分配合理的n维坐标，将网络聚类问题转化为空间点聚类问题。给定两个顶点，A=(a1，a2，…，an)和B=(b1，b2，…，bn)，则可以利用各种距离度量方法计算两者的距离。例如，欧几里得距离：

2 改进的层次聚类算法
   用于表示现实网络系统的复杂网络通常具有的层次结构特征，即较大的社区结构包含较小的社区结构。层次聚类算法能有效地发现这种层次结构，被广泛应用于社交网络分析、生物工程、市场分析等领域。层次聚类算法可以分为两大类：
   (1)凝聚方法：采用自底向上的策略，首先将每个对象作为簇（cluster），然后合并这些原子簇成为更大的簇，直到所有对象都在一个簇中，或者满足某终止条件。
   (2)分裂方法：采用自顶向下的策略，首先将所有对象置于一个簇中，然后逐步细分为越来越小的簇，直到每个对象各为一簇，或满足某终止条件，例如达到了希望的簇数或每个簇的直径都在某个阈值内。
   由于分裂方法很少使用，本文讨论的算法采用自底向上的策略。通常可以用树状图（dendrogram）表示层次聚类的过程，如图1所示。
   层次聚类算法将网络划分为几个社区取决于在什么位置分割树状图，如图1中横线位置将产生两个社区结构。实际网络中通常依据模块性标准来确定最佳的划分位置。
   传统层次聚类算法在确定相似度计算方法后，计算所有顶点对之间的相似度。本文在传统方法的基础上，引入ego角色探测过程，根据复杂网络具体特征，首先确定相似度计算方法，然后确定ego角色的探测方法，一旦扮演ego角色的顶点被确定，则只计算图中所有其他顶点与ego顶点之间的相似度，这种情况下，时间复杂度取决于ego探测过程，例如，选定Degree Centrality作为ego探测策略，总的时间复杂度可表示为O(n)。可见，在大规模网络分析中，改进的层次聚类算法具有较大优势。算法步骤如下。
Input:Graph G=(V,E), V include all vertexs, E include all edges
Output:Communities C1, C2, C3,……
Declare:score(v) // score of vertex v according to the ego vertex compute method
        similarity(v1,v2) //similarity between v1 and v2
Begin
//step1:basic step for detecting communities in C
;Define similarity compute method
;Define ego vertex compute method
for?坌v∈V do
   compute score(v)
endfor
v(ego)=MAX(score(v1), score(v2),……);Find ego vertex v(ego)
for ?坌v∈V\v(ego) do
   compute similarity(v, v(ego))
endfor
start to cluster vertexs based on similarities
produce C1’, C2’, C3’,……
//step2:continue to detect subgroup in groups have been found
if do not satisfy the end conditon then
   for ?坌C∈{C1’,C2’,C3’,……} do
        run step1 procedure in C
   endfor
else
   output the final result C1,C2,C3……
endif
end
   该算法可以有两种应用用途：在较理想的情形下，例如复杂网络表示的是现实的EgoNetworks，则算法能有效挖掘网络中的社区结构；对于准确度要求很高以及复杂网络规模巨大、特征不明确的情形，本文算法可作为网络预处理过程，用于降低网络分析规模，此时算法只产生规模合适的粗糙的社区，再运用其他准确度较高的算法，划分出更精确的社区。
3 实验分析
3.1 EgoNetworks中的算法应用
   该EgoNetworks数据采集自社交网站人人网，包含了一个Ego角色和49个alter角色。图中顶点代表一个个体，边表示个体之间的好友关系。由调查得知，该网络包含三个同学群体，一个陌生人群体，一个亲密好友群体。运用改进的层次聚类算法，成功地挖掘出了网络中包含的五个社区，算法采用的相似度计算方法是顶点间海明距离，ego角色在初始状态是已知的，第一次迭代后利用Degree Centrality探测新的ego角色。图2描述了模块度Q值随社区个数变化的分布图，x轴表示社区数量，y轴表示对应的Q值。
   由图2可见，当Q值取最大0.363时，对应的社区个数为5，此时划分质量最高，网络中社区结构图如图3所示。

3.2 “Zachary空手道俱乐部网络”中的算法应用
Zachary空手道俱乐部网络[8]是测试社区挖掘算法的经典网络，该网络描述了美国一所大学空手道俱乐部的34名成员之间的关系，其中包含了两个已知的社区结构。图4的划分结果来自Girvan-Newman算法，不同社区用不同颜色顶点区分。

本文算法在选定Degree Centrality和海明距离分别作为ego角色探测和相似度计算策略后，划分结果如表1所示。

表1中，除了10,12,32,28四个顶点划分有误，其他都正确。在这种非EgoNetworks中，根据网络特征选取恰当的相似度计算和ego角色探测方法很重要，实验中选择了较简单的方法，虽然在准确性上有不足，但是时间复杂度只有O(n)，较传统方法的O(n2)，在大规模网络中，改进的层次聚类算法优势明显。
社区挖掘是复杂网络分析的重要手段之一。本文总结了复杂网络中常用的顶点间相似度计算方法和顶点重要性度量方法，在此基础上，对传统的层次聚类算法进行改进，引入网络中“ego”角色的探测过程，并在现实的EgoNetworks以及经典实际网络中验证了算法的有效性。虽然改进的层次聚类算法能很好地提高社区挖掘效率，但是在准确性上仍有不足之处。如何提高算法准确度以及如何根据具体的网络特征，制定合适的相似度计算和“ego”角色探测方法是以后研究的主要工作。
参考文献
[1] GIRVAN M，NEWMAN M E J.Community structure in social and biological networks[C].Proc.Natl.Acad.Sci.USA 99，2002：7821-7826.
[2] Yang Bo, Liu Dayou, Liu Jiming, et al.Complex network clustering algorithms[J]. Journal of Software, 2009,20(1)：54-66.
[3] FORTUNATO S.Community detection in graphs[C].arXiv：0906.0612，2010.
[4] HANNEMAN R A，RIDDLE M.Introduction to social network methods[M/OL].Riverside，CA：Universityof California，Riverside,2005.http://faculty.ucr.edu/~hanneman/.
[5] ADAMIC L A，ADAR E.Friends and neighbors on the web[J].Social Networks, 2007,25(2): 211-230.
[6] NEWMAN M E J.Mathematics of networks[M].In The New Palgrave Encyclopedia of Economics, 2nd edition.Palgrave Macmillan, Basingstoke, 2007.
[7] NEWMAN M E J，GIRVAN M.Finding and evaluating community structure in networks[J].Physical Review E, 69,2004.
[8] ZACHARY W W.An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research, 1977, 33(2):452-473.

原创声明：此内容为AET网站原创，未经授权禁止转载。

相关内容