基于局部相似性的K—means谱聚类算法

西安理工大学学报Ｊｏｕｒｎａｌ　ｏｆ　Ｘｉ’ａｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ（２０１３）Ｖｏ１．２９　Ｎｏ．４　文章编号：１００６－４７１０（２０１３）０４－０４５５－０５　４５５　基于局部相似性的Ｋ—ｍｅａｎｓ谱聚类算法　王林　，高红艳　，王佰超　（１．西安理工大学自动化与信息工程学院，陕西西安７１００４８；　２．宝鸡文理学院物理与信息技术系，陕西宝鸡７２１０１６）　摘要：定义科学的局部相似性指数是基于局部相似性社团发现算法的关键，根据共有邻居信息定　义的局部形似性指数对直接相连接点对的相似性数值存在低估倾向，本研究将节点对的关联信息　加入到ｓｑ，ｒｅｎｓｅｎ局部相似性指数的定义中，结合Ｋ．ｍｅａｎｓ谱聚类算法对网络节点进行聚类。本研　究定义的局部相似性指数克服了传统局部相似性指数的缺点，且保持了原有的计算复杂性。在计　算机生成网络和实际网络上运行，并和经典算法做了比较，实验证明，所提算法能够较为有效、准确　地检测网络的社团结构。　关键词：局部相似性；谱聚类；Ｋ．ｍｅａｎｓ聚类　中图分类号：ＴＰ１５　文献标志码：Ａ　Ａｌｇｏｒｉｔｈｍ　ｏｆ　Ｋ－ｍｅａｎｓ　Ｓｐｅｃｔｒａｌ　Ｃｌｕｓｔｅｒｉｎｇ　Ｂａｓｅｄ　ｏｎ　Ｌｏｃａｌ　Ｓｉｍｉｌａｒｉｔｙ　ＷＡＮＧ　Ｌｉｎ　，ＧＡＯ　Ｈｏｎｇｙａｎ　，ＷＡＮＧ　Ｂａｉｃｈａｏ　（１．Ｆａｃｕｌｔｙ　ｏｆ　Ａｕｔｏｍａｔｉｏｎ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｘｉ’ａｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，Ｘｉ’ａｎ　７１００４８，Ｃｈｉｎａ；　２．Ｆａｃｕｌｔｙ　ｏｆ　Ｐｈｙｓｉｃｓ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｂａｏｊｉ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ａｒｔ　ａｎｄ　Ｓｃｉｅｎｃｅ，Ｂａｏｊｉ　７２１０１６，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｔｈｅ　ｃｏｒｒｅｌａｔｉｏｎ　ｉｎｆｏｒｍａｔｉｏｎ　ｏｆ　ｎｏｄｅ　ｐａｉｒｓ　ｉｓｉｎｃｏｐｏｒａｔｅｄ　ｉｎ　ｔｈｅ　ｄｅｆｉｎｉｔｉｏｎ　ｏｆ　ｓ＋ｒｅ￣ｅｎ　ＩｏｃａＩ　ｓｉｍｉ．　１ａｒｉｔｙ　ｉｎｄｅｘ，ｎｅｔｗｏｒｋ　ｎｏｄｅｓ　ａｒｅ　ｃｌｕｓｔｅｒｅｄ　ｂｙ　ｔｈｉｓ　ｓｉｍｉｌａｒｉｔｙ　ｍｅａｓｕｒｅ　ｃｏｍｂｉｎｉｎｇ　ｗｉｔｈ　Ｋｍｅａｎｓ　ｓｐｅｃｔｒａｌ　ｃｌｕｓ—　ｔｅｒｉｎｇ．Ｔｈｅ　ｓｉｍｉｌａｒｉｔｙ　ｉｎｄｅｘ　ｐｒｏｐｏｓｅｄ　ｂｙ　ｔｈｅ　ｐａｐｅｒ　ｏｖｅｒｃｏｍｅｓ　ｔｈｅ　ｓｈｏｒｔｃｏｍｉｎｇｓ　ｏｆ　ｔｒａｄｉｔｉｏｎａｌ　ｌｏｃａｌ　ｓｉｍｉｌａｒｉ—　ｔｙ　ｉｎｄｅｘ，ａｎｄ　ｍａｉｎｔａｉｎｓ　ｔｈｅ　ｏｒｉｇｉｎａｌ　ｃｏｍｐｕｔａｔｉｏｎａｌ　ｃｏｍｐｌｅｘｉｔｙ．Ｔｈｅ　ｐｒｏｐｏｓｅｄ　ｍｅｔｈｏｄ　ｉｓ　ｔｅｓｔｅｄ　ｏｎ　ｂｏｔｈ　ｃｏｍｐｕｔｅｒ－ｇｅｎｅｒａｔｅｄ　ａｎｄ　ｒｅａｌ－ｗｏｒｌｄ　ｎｅｔｗｏｒｋｓ，ａｎｄ　ｉｓ　ｃｏｍｐａｒｅｄ　ｗｉｔｈ　ｔｈｅ　ｔｙｐｉｃａｌ　ａｌｇｏｒｉｔｈｍｓ　ｉｎ　ｃｏｍｍｕｎｉｔｙ　ｄｅｔｅｃｔｉｏｎ．Ｅｘｐｅｒｉｍｅｎｔｌ　ｒｅｓｕｌａｔｓ　ｖｅｒｉｆｙ　ａｎｄ　ｃｏｎｆｉｒｍ　ｔｈｅ　ｆｅａｓｉｂｉｌｉｔｙ　ａｎｄ　ｖａｌｉｄｉｔｙ　ｏｆ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ｍｅｔｈｏｄ　ｔｏ　ｍｏｎｉｔｏｒ　ｃｏｍｍｕｎｉｔｙ　ｓｔｒｕｃｔｕｒｅ　ｏｆ　ｒｅａｌ　ｉｎｔｅｒｎｅｔ　ａｃｃｕｒａｔｅｌｙ．　Ｋｅｙ　ｗｏｒｄｓ：ｌｏｃａｌ　ｓｉｍｉｌａｒｉｔｙ；ｓｐｅｃｔｒａｌ　ｃｌｕｓｔｅｒｉｎｇ；Ｋ—ｍｅａｎｓ　ｃｌｕｓｔｅｒｉｎｇ　社团结构是复杂网络的重要特性之一，研究社　团结构有助于了解网络结构，分析网络特性，预测网　络功能　引，所以社团检测近年来成为学者们研究　的热点问题　。　邻居的节点对具有零相似性，这显然是不合适的。　因此，寻找一个计算简单，且能准确刻画网络结构的　相似性指数仍然是人们迫切需要解决的问题。　基于上述问题，本研究提出了一种新的局部相　似性指数，该指数以ｓｄｐｒｅｎｓｅｎ指数　为原形，考虑了　节点直接相连接对相似性的影响，采用Ｋ－ｍｅａｎｓ谱　聚类法对网络节点进行聚类，与基于传统的局部相　基于相似性的算法是一类重要的社团检测算　法，它利用网络的全局或者局部特性计算节点或边　的相似性，再结合传统聚类算法社团划分　。该　算法的关键是定义合适的“相似性指数”。一类相　似性指数是全局的，考虑了网络的全局信息，计算准　确，但运算复杂度高，而且引进了额外参数，实用性　不强。另一类相似性指数为局部指数　，采用节　点的共有邻居数或简单变形来衡量节点相似性，无　视节点是否直接相连，从而使直接相连的但无共同　收稿日期：２０１３－０４－２０　似性指数的社团发现算法和几种典型的社团发现算　法做了比较，在计算机生成的网络和实际网络上验　证，结果显示，所提的算法能够克服传统局部相似性　的缺点，继承传统局部相似性计算量小的特点，能够　准确，有效地检测人工合成网络和实际网络的社团　结构。　作者简介：王林，男，教授，研究方向为复杂网络、数据库等。Ｅ—ｍａｉｌ：ｗａｎｇｌｉｎ＠ｘａｕｔ．ｅｄｕ．ａｎ。　４５６　西安理工大学学报（２０１３）第２９卷第４期　１　基于局部相似性的Ｋ—ｍｅａｎｓ谱聚类算法　１．１相似性度量　０相似性。而在实际当中，同一社团内直接相连而　无共同邻居的节点对是普遍存在的，这些节点对的　相似性显然是不应该为０的。因此在定义节点相似　性时，应考虑两种情况，即：　１）两节点之间无边相连，如图１（ａ）所示的节点　ｉ，　；　求网络节点的相似性一般有两种方法，如果网　络可以嵌入到／７，维欧几里得空间，每个节点对应欧　几里得空间的一个点，就可以用每对节点之间的距　离来表示节点之间的相似性。如果不能嵌入到欧几　里得空间，则节点之间的相似性只能通过节点之间　２）两节点之间有边相连（这里考虑简单图，两　的邻接关系来推断，ｓ￣ｂｒｅｎｓｅｎ指数就是一种通过节　点的共有邻居数来描述节点之间相似性的局部相似　性指数，定义为：　ｊ一　ｉ：　ｋ　＋　ｋ　（１），　节点之间只有一条边），如图１（ｂ）所示节点ｉ，　。　为了能够准确地刻画所有节点对之间的相似　性，在节点ｉ，　之间添加一个辅助接点ｑ，如图１（ｃ）　所示，则节点　和　之间的边（ｉ，　）可认为是由辅助　节点ｑ连接的边（ｉ，ｑ）和边（　，ｇ）组成。这样，节点　ｉ，之间的边断开，反映在邻接矩阵Ａ中，就是　行　．　式中，Ｎ（ｉ）表示节点ｉ的邻居。分子表示节点ｉ与　节点　的共有邻居数，．ｊ｝　，　为节点　√的度。　对于不直接相连的节点ｓ西ｒｅ　ｅｎ指数能够较为　准确地评估它们的相似性。对于直接相连却无共同　列和．　行　列元素由１变为０，并且需要加人辅助节　点所对应的一行和一列。假设图１（Ｃ）所对应的邻　接矩阵为Ａ’，那么新加的行和列仅有Ａ’（ｉ，ｑ），Ａ’　（　，ｇ），Ａ’（ｑ，ｉ），Ａ’（ｇ√）四个元素为１，其余为０。　邻居的节点对，由于分子为零，所以ｓｄｐｒｅｎｓｅｎ赋予其　垂　售　（ａ）节点ｆ与　之间无边　（ｂ）节点ｆ与，之间有边　（ｃ）加辅助节点　图１一个简单的例子　Ｆｉｇ．１　ａ　ｓｉｍｐｌｅ　ｅｘａｍｐｌｅ　若ｌ网络的邻接矩阵为Ａ，贝　（１）式等价为：　２×（Ａ（　，　）＋∑（Ａ（　，Ｊｊ｝）×Ａ（ｊ，　）））　（２）Ｌ　　ｓ　————　——————　—————一—一　３　（５）　或为：　由于在社团发现过程中主要考虑节点对之间相　２×∑Ａ　×Ａ　ｓ　—似性值的排序，故可以省去乘数因子，得到相似性指　专ｌ一　（３）　数为：　添加辅助节点以后，将新的邻接矩阵带入（３）　式得到：　Ａ（　，　）＋∑（Ａ（　，　）×Ａ（ｊ，　））　ｓ　———　—————　———一—一　（６）ｏ　Ｊ　２×∑Ａ　×Ａ　ｉｊ　——　上式可以简写为：　ｓ　＝　ｋ—～（４）　■　（７）Ｌ　　２×（１＋∑（Ａ（　，　）×Ａ（ｊ，　））　———　．修正ｓｑｂｒｅｎｓｅｎ考虑了节点直接相连对相似性的　贡献，在计算复杂性上，修正ｓｃｂｒｅｎｓｅｎ指数与　ｓ　ｒｅ　ｅｎ指数具有相同的时间复杂性，为ｏ（ｎ　），所　以它更适合检测网络的社团结构。　１．２　Ｋ－ｍｅａｎｓ谱聚类算法　定义了网络节点的相似度以后，网络社团划分　＋　如此，第２）类情况可用表达式（４）进行计算。　所以任意节点对的修正ｓ　示为：　ｅ　相似性指数可表　王林，等：基于局部相似性的Ｋ－ｍｅａｎｓ谱聚类算法　问题就可以转化为聚类问题，可以用基于相似矩阵　的聚类算法进行划分。这里采用Ｋ—ｍｅａｎｓ谱聚类算　法对网络节点进行聚类＿１　，算法执行过程为：　１）根据上节定义的相似性指数计算相似性矩　阵Ｓ；　２）求相似性矩阵的特征值和相应的特征向量，　将特征值按顺序排列，根据相邻特征值之间的最大　距离估计网络的社团个数Ｃ；　３）取特征值前ｃ个最大值所对应的特征向量　组成新的向量　；　４）以＇，为原始数据对其进行Ｋ．ｍｅａｎｓ聚类；　５）用模块度验证估算的社团个数Ｃ的合理性，　计算社团划分的准确性。　该算法的时间复杂度由三部分组成，第一部分是　计算相似『生矩阵的复杂度为Ｏ（　。），第二部分是谱聚　类算法，计算特征向量时采用Ｌａｎｃｚｏｓ方法快速计算　前ｋ个最大特征值对应的特征向量，该方法的复杂度　约为０（ｋｍ），其中ｋ为社团个数，ｍ为网络节点数。　第三部分是Ｋ—ｍｅａｎｓ聚类算法的复杂度Ｏ（ｋｔｎ），ｔ为　迭代次数，ｎ为网络节点数。因为ｋ为常数，迭代次　数ｔ有限制总时间复杂度为Ｏ（ｎ　＋ｍ）。　２仿真　为了测试本研究所提算法的性能，笔者利用计　算机合成的网络和真实世界网络进行了社团发现　实验。　２．１计算机生成网络　所用的基准网络＿１ｕ由１２８个节点组成，划分为　４个社团，网络中节点的平均度为１６，其中社团之间　的节点度期望值为ｚ　，社团内节点度期望值为　ｚｉ　，让ｚ。　从ｌ到８连续增加，观察社团划分情况。　社团划分的准确性用归一化互信息（Ｎｏｒｍａｌｉｚｅｄ　ｍｕｔｕａｌ　ｉｎｆｏｒｍａｔｉｏｎ）来度量¨　，定义为：　ＮＭＩ（Ｘ，Ｙ）＝　一２∑　ＣＸ∑　ｘＮ０１￣ｇ（　）　———————　＿———————Ｌ　Ｌ　一　（８）　∑　Ｃｘ　Ｎ　ｌｏｇ（　）＋∑　Ｃｙ　ｌｏｇ（　）　式中，　为原始的社区划分，ｌ，为算法得出的社团划　分，ＮＭＩ（Ｘ，Ｙ）表示划分　与划分ｙ之间的接近程　度，取值范围为０—１，其值越大算法所得的社团结　构与真实社团越接近，当ＮＭＩ＝ｌ时表示所得结果　与真实社团划分完全一致。当ＮＭＩ＝０时表示算法　得到的划分与真实划分完全不同。　社团划分的ＮＭＩ曲线如图ｌ所示，由于生成的　４５７　基准网络具有随机性，对于每个ｚ。　值笔者重复做　了１００次实验。图２中每个点对应１００次实验的平　均值。由图２可知，当ｚ　。从零逐渐增加时，由于基　准网络的社团结构由清晰变模糊，所以ＮＭＩ曲线呈　递减趋势；当Ｚ　＝１—４时该算法的正确划分率为　１００％，Ｚ　。＜６时准确率在０．９以上。当ｚ。　继续增　加时，由于网络社团结构越来越模糊，社团检测准确　率剧烈下降。可见当社团结构明显时，该算法的准　确率是比较高的。　０　萋０　０　１　２　３　４　５　６　７　８　Ｚ。　社团划分准确性　图２算法准确度　Ｆｉｇ．２　Ｔｈｅ　ａｃｃｕｒａｃｙ　ｏｆ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　为进一步验证算法性能本研究做了两组实验，　首先将基于改进相似性指数的算法与基于原相似性　指数的算法做了比较，结果如图３所示。由图３可　知Ｚ。　＜４时两种算法的准确率都比较高，但当ｚ　继续增加的时候，改进算法的准确率明显高于原　算法。　Ｏ　萋ｏ　０　ｌ　２　３　４　５　６　７　８　ｚ。　不同相似性比较　图３不同相似性比较　Ｆｉｇ．３　Ｔｈｅ　ｃｏｍｐａｒｉｓｏｎ　ｏｆ　ｄｉｆｆｅｒｅｎｔ　ｓｉｍｉｌａｒｉｔｙ　其次，将本算法与ＧＮ算法（ＧＮ）和快速算法　（ｆａｓｔｇｒｅｅｄｙ）做了比较，结果如图４所示。　萋：　０　１　２　３　４　５　６　７　８　乙　算法比较　图４不同算法比较　Ｆｉｇ．４　Ｔｈｅ　ｃｏｍｐａｒｉｓｏｎ　ｏｆ　ｄｉｆｆｅｒｅｎｔ　ａｌｇｏｒｉｔｈｍｓ　由图４可见，当社团结构比较明显时（Ｚ。　＜　７），本研究算法性能高于ＧＮ算法和快速算法，当社　团结构模糊时（Ｚ。　＞７），由于本算法采用了节点的　４５８　局部信息，算法准确率低于ＧＮ算法和快速算法。　从算法的复杂度来看，本算法时间复杂度大于ＧＮ　算法，小于快速算法。　２．２真实网络　研究社团发现算法的目的在于检测社团个数未　知的真实网络的社团结构，所以还需要用真实网络　检测算法的准确性和有效性，下面笔者将用常用实　际基准网络Ｋａｒａｔｅ网和美国大学足球俱乐部网检　测算法。　Ｚａｃｈａｒｙ网络是检测社团发现算法的基准网络　之一　Ｊ　，反映了美国一所大学中空手道俱乐部３４　名成员之间的相互社会关系。该俱乐部在被研究期　间，由于内部争执而分裂成了１６名成员和１８名成　员的小俱乐部。该俱乐部的自然划分如图３所示，　图３中方形和圆形分别代表分裂后的小俱乐部中的　各个成员。图５为本算法得到的相似矩阵特征序列　图，图６为相应的模块度曲线。表１社团划分结果。　表１　ｋａｒａｔｅ网络社团划分结果　Ｔａｂ．１　Ｔｈｅ　ｒｅｓｕｌｔ　ｏｆ　ｃｏｍｍｕｎｉｔｙ　ｄｅｔｅｃｔｉｏｎ　ｏｆ　ｋａｒａｔｅ　ｎｅｔｗｏｒｋ　社团　所含节点　１　１，２，３，４，５，６，７，８，１１，１２，１３，１４，１７，１８，２０，２２　９，１０，１５，１６，１９，２１，２３，２４，２５，２６，２７，２８，　－　２９。３０。３１，３２，３３。３４　图５　Ｚａｃｈａｒｙ空手道俱乐部成员划分结果　Ｆｉｇ．５　Ｔｈｅ　ｒｅｓｕｌｔ　ｏｆ　ｃｏｍｍｕｎｉｔｙ　ｄｅｔｅｃｔｉｏｎ　ｏｆ　Ｚａｃｈａｒｙ　ｋａｒａｔｅ　ｃｌｕｂ　趔　降序排列的特征值序号　图６相似矩阵特征值序列图　Ｆｉｇ．６　Ｓｅｑｕｅｎｃｅ　ｄｉａｇｒａｍｓ　ｏｆ　ｓｉｍｉｌａｒｉｔｙ　ｍａｔｒｉｘ　从图６可知，最大特征向量距离为Ａ：一Ａ　，所　以预测社团个数为２，由图７可知，当社团个数Ｃ＝２　西安理工大学学报（２０１３）第２９卷第４期　时，模块度最大，为０．３７１５，所以预测时正确的。由　表１可知网络划分为两个社团，第一个社团１６个节　点，第二个社团ｌ８个节点，划分准确率为１００％。　Ｏ・３　Ｏ．２　ｔ　Ｏ・Ｏ　．０．０　社　个数　图７模块度值　Ｆｉｇ．７　Ｔｈｅ　ｖａｌｕｅｓ　ｏｆ　ｍｏｄｕｌａｒｉｔｙ　美国大学足球联盟网络是根据２０００年秋季常　规赛季的比赛计划构建的　］。网络中的节点代表　球队，边代表两个球队之间常规赛季的比赛，它共　包含１１５个节点和６１６条边。该网络通常由８～１２　个球队组成一个联盟（ｃｏｎｆｅｒｅｎｃｅ），同一个联盟球队　之间的比赛次数多于不同联盟的球队间的比赛次　数，每个联盟代表了一个真实社团。该网络自然划　分为１２个社团。采用本算法进行社团检测，社团划　分结果如表２所示，当社团个数为ｌ２时，所得模块　度最大为０．６００５，共有１１个节点被错误划分，划分　准确率为９０．４３％。　表２　ｆｏｏｔｂａｌｌ网络社团划分结果　Ｔａｂ．２　Ｔｈｅ　ｒｅｓｕｌｔ　ｏｆ　ｃｏｍｍｕｎｉｔｙ　ｄｅｔｅｃｔｉｏｎ　ｏｆ　ｆｏｏｔｂａｌｌ　ｎｅｔｗｏｒｋ　社团　所含节点　１　１，５，１０，１７，２４，４２，９４，１０５　２　２，２６，３４，３８，４６，９０，１０４，１０６，１１０　３　３，７，１４，１６，３３，４０，４８，６１，６５，１０１，１０７　４　４，６，１１，４１，５３，７３，７５，８２，８５，９９，１０３，１０８　５　８，９，２２，２３，５２，６９，７８，７９，１０９，１１２　６　１２，２５，２９，５１，７０，９１　７　１３，１５，１９，２７，３２，３５，３９，４３，４４，５５，６２，７２，８６，１００　８　１８，２１，２８，５７，６３，６６，７１，７７，８８，９６，９７，１１４　９　２０，３０，３１，３６，５６，８０，８１，８３，９５，１０２　１０　３７，５９，６０，６４，９８　１１　４５，４９，５８，６７，７６，８７，９２，９３，１１３　１２　４７，５０，５４，６８，７４，８４，８９，１１１，１１５　３　结论　（１）提出了一种新的网络节点相似性度量方　法，该方法在检测网络社团方面比传统局部相似性　指数更为准确，且计算复杂度不大；　（２）将该相似性和Ｋ．ｉＹｌｅａｎｓ谱聚类相结合，较　为准确而有效地检测实际网络社团结构。文中定义　王林，等：基于局部相似性的Ｋ—ｍｅａｎｓ谱聚类算法　的相似性指数也可以和任何基于相似性的社团发现　相结合以检测社团结构。　参考文献：　［１］Ｓｔｒｏｇａｔｚ　Ｓ　Ｈ．Ｅｘｐｌｏｒｉｎｇ　ｃｏｍｐｌｅｘ　ｎｅｔｗｏｒｋｓ［Ｊ］．Ｎａｔｕｒｅ，　２００１，４１０：２６８－２７６．　［２］Ｂｏｃｃａｌｅｔｔｉ　Ｓ，Ｌａｔｏｒａ　Ｖ，Ｍｏｒｅｎｏ　Ｙ，ｅｔ　ａ１．Ｃｏｍｐｌｅｘ　ｎｅｔ—　ｗｏｒｋｓ：ｓｔｒｕｃｔｕｒｅ　ａｎｄ　ｄｙｎａｍｉｃｓ［Ｊ］．Ｐｈｙｓｉｃｓ　Ｒｅｐｏｒｔｓ，２００６，　４２４：１７５—３０８．　［３］胡海波，王林．关于因特网自治系统的连接率的幂律关　系［Ｊ］．西安理工大学学报，２００５，２１（２）：２０４－２０６．　Ｈｕ　Ｈａｉｂｏ，Ｗａｎｇ　Ｌｉｎ．Ｐｏｗｅｒ　ｌａｗ　ｒｅｌａｔｉｏｎｓｈｉｐ　ｏｆ　ｃｏｎｎｅｃｔｉｏｎ　ｒａｔｅｓ　ｉｎ　ａｓｓ　ｏｆ　ｔｈｅ　ｉｎｔｅｒｎｅｔ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ｘｉ’ａｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，２００５，２１（２）：２０４－２０６．　［４］Ｓａｎｔｏ　Ｆｏｒｔｕｎａｔｏ．Ｃｏｍｍｕｎｉｔｙ　ｄｅｔｅｃｔｉｏｎ　ｉｎ　ｇｒａｐｈｓ［Ｊ］．Ｐｈｙｓ—　ｉｃｓ　Ｒｅｐｏｒｔｓ，２０１０，４８６：７５—１７４．　［５］Ｋｅｒｎｉｇｈａｎ　Ｂ　Ｗ，Ｌｊｎ　ｓ．Ａｎ　ｅｆｉｆｃｉｅｎｔ　ｈｅｕｒｉｓｔｉｃ　ｐｒｏｃｅｄｕｒｅ　ｆｏｒ　ｐａｒｔｉｔｉｏｎｉｎｇ　ｇｒａｐｈｓ［Ｊ］．Ｂｅｌｌ　Ｓｙｓｔｅｍ　Ｔｅｃｈｎｉｃａｌ　Ｊｏｕｒｎａｌ，　１９７０，４９：２９１－３０７．　［６］Ｎｅｗｍａｎ　Ｍ　Ｅ　Ｊ，Ｇｉｒｖａｎ　Ｍ．Ｆｉｎｄｉｎｇ　ａｎｄ　ｅｖａｌｕａｔｉｎｇ　ｃｏｍｍｕ—　ｎｉｔｙ　ｓｔｒｕｃｔｕｒｅ　ｉｎ　ｎｅｔｗｏｒｋｓ［Ｊ］．Ｐｈｙｓｉｃａｌ　Ｒｅｖｉｅｗ　Ｅ，２００４，　６９：０２６１１３．　［７］Ｚｈｏｕ　Ｔａｏ，Ｌｖ　Ｌｉｎｙｕａｎ，Ｚｈａｎｇ　Ｙｉｃｈｅｎｇ．Ｐｒｅｄｉｃｔｉｎｇ　ｍｉｓｓｉｎｇ　４５９　ｌｉｎｋｓ　ｖｉａ　ｌｏｃａｌ　ｉｎｆｏｒｍａｔｉｏｎ『Ｊ］．Ｔｈｅ　Ｅｕｒｏｐｅａｎ　Ｐｈｙｓｉｃａｌ　Ｊｏｕｒｎａｌ　Ｂ，２００９，７１（４）：６２３－６３０．　［８］Ｌｅｉｃｈｔ　Ｅ　Ａ，Ｈｏｌｍｅ　Ｐ　Ｍ　Ｅ　Ｊ．Ｎｅｗｍａｎ。ｖｅｒｔｅｘ　ｓｉｍｉｌａｒｉｔｙ　ｉｎ　ｎｅｔｗｏｒｋｓ［Ｊ］．Ｐｈｙｓｉｃａｌ　Ｒｅｖｉｅｗ　Ｅ，２００６，７３：０２６１２０．　［９］Ｓｏｒｅｎｓｅｎ　Ｔ　Ａ．Ｍｅｔｈｏｄ　ｏｆ　ｅｓｔａｂｌｉｓｈｉｎｇ　ｒｇｏｕｐｓ　ｏｆ　ｅｑｕａｌ　ａｍ—　ｐｌｉｔｕｄｅ　ｉｎ　ｐｌａｎｔ　ｓｏｃｉｏｌｏｇｙ　ｂａｓｅｄ　ｏｎ　ｓｉｍｉｌａｒｉｔｙ　ｏｆ　ｓｐｅｃｉｅｓ　ｃｏｎｔｅｎｔ　ａｎｄ　ｉｔｓ　ａｐｐｌｉｃａｔｉｏｎ　ｔｏ　ａｎａｌｙｓｅｓ　ｏｆ　ｔｈｅ　ｖｅｇｅｔａｔｉｏｎ　ｏｎ　Ｄａｎｉｓｈ　ｃｏｍｍｏｎｓ［Ｊ］．Ｂｉｏｌｏｇｙ　Ｓｋｒ，１９４８，５（１）：２３．２７．　［１０］孙吉贵，刘杰，赵连宇．聚类算法研究［Ｊ］．软件学报，　２００８，１９（１）：４８－６１．　Ｓｕｎ　Ｊｉｇｕｉ，Ｌｉｕ　Ｊｉｅ，Ｚｈａｏ　Ｌｉａｎｙｕ．Ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍｓ　ｒｅｓｅａｒｃｈ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｔｆｗａｒｅ，２００８，１９（１）：４８－６１．　［１　１］Ｇｉｒｖａｎ　Ｍ，Ｎｅｗｍａｎ　Ｍ　Ｅ　Ｊ．Ｃｏｍｍｕｎｉｔｙ　ｓｔｒｕｃｔｕｒｅ　ｉｎ　ｓｏｃｉａｌ　ａｎｄ　ｂｉｏｌｏｇｉｃａｌ　ｎｅｔｗｏｒｋｓ［Ｊ］．Ｐｒｏｃｅｅｄｉｎｇｓ　Ｎａｔｉｏｎａｌ　Ａｃａｄｅ—　ｍｙ　Ｓｃｉｅｎｃｅ，２００２，９９（１２）：７８２１－７８２６．　［１２］Ｄａｎｏｎ　Ｌ，Ｄｉａｚ—Ｇｕｉｌｅｒａ　Ａ，Ｄｕｃｈ　Ｊ．Ｃｏｍｐａｒｉｎｇ　ｃｏｍｍｕｎｉｔｙ　ｓｔｒｕｃｔｕｒｅ　ｉｄｅｎｔｉｃａｆｉｏｎ『Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ｓｔａｉｔｓｔｉｃｌａ　Ｍｅｃｈａｎ．　ｉｃｓ：Ｔｈｅｏｒｙ　ａｎｄ　Ｅｘｐｅｒｉｍｅｎｔ，２００５，（９）：０９００８．　『１３１　Ｚａｃｈａｒｙ　Ｗ　Ｗ．Ａｎ　ｉｎｆｏｒｍａｔｉｏｎ　ｆｌｏｗ　ｍｏｄｅｌ　ｆｏｒ　ｅｏｎｆｌｉｃｔ　ａｎｄ　ｉｆｓｓｉｏｎ　ｉｎ　ｓｍａｌｌ　ｇｒｏｕｐｓ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ａｎｔｈｒｏｐｏｌｏｇｉｃａｌ　Ｒｅ—　ｓｅａｒｃｈ，１９７７，３３（４）：４５２－４７３．　（责任编辑李虹燕）