2023年7月29日发(作者：)

在网络理论研究中，数量巨大的节点以及节点之间复杂的交互关系构成了复杂网络和复杂网络的网络结构。用数学语言表达，即一个图有着足够复杂的拓扑结构特征[1]。复杂网络中的一种普遍现象就是社区现象，它表达了社区中的个体具有某一方面共同特征的性质。社区发现在很多学科有重要应用，如在计算机学科中，增强网络销售功能、提高网络服务质量等；在社会学中，发现动物社会组织结构、揭示政府职能构成和运行方式、发现某一领域的科学家群组等；在生物学领域功能基因聚类等。

近年来，科学家们提出了关于社区发现的很多新方法。本文首先介绍了几种常见的复杂网络以及其的特性。在此基础上介绍了基于迭代二分法(Iterative

Bisection)的Kernighan—Lin算法、谱二分法（Spectral bisection），基于去边方法的G-N算法、Radicchi算法，层次聚类法（Hierarchical Clustering）和W-H算法。分析了这些算法的时间复杂度等因素，指出了它们的优势和不足，并且还给出了这些算法的适用范围。

本文的主要研究内容是基于网络中节点间紧密度的层次聚类社区发现算法。在层次聚类算法中，传统的节点间紧密度的计算方法主要是基于网络的拓扑结构，如余弦相似性（cosine similarity）、欧拉距离和皮尔逊系数（Pearson correlation

coefficient）等。本文节点间相似度的计算是基于节点之间信息交流来往的频率，即节点间边权值的大小来衡量节点的紧密度。两个节点之间交流越频繁，说明这两个节点的紧密度就越高，同属于一个社区的可能性就越大。将计算出来的紧密度值存储与紧密度二叉堆中。同时把节点之间的相似度计算扩展到社区之间，更新紧密度二叉堆中的值，利用二叉堆中的值，合并社区，直到社区的合并结果满足某一条件为止。实验表明，该方法能较好且合理的发现社区结构。

关键词：社区发现；复杂网络；社区结构；层次聚类

第1章 绪论

1．1研究背景和意义

最近几年，大多数国家对复杂网络的研究都趋于狂热。随着计算机对数据的存储和处理的能力越来越强，以及大规模系统的数据库的兴起，使我们真正认识了网络的特征数据，发现真实网络既不是规则的，也不是随机的，而是复杂的，并且呈现一定规律的。

在信息时代，网络的社区发现存在更加普遍，发现技术应用更加方便，其服务价值和商业价值更大。研究在线社会网络离不开社会网络的分析方法，尤其是社区可为信息推送、个性化服务等提供基本数据。

所以，在复杂网络中进行社区发现意义非比寻常。大量与社区发现相关的论文都被刊登上了《Physical Review E》《PNAS》《Nature》《Science》等世界顶级的学术期刊，WWW、CIKM、SIGIR、SIGKDD、ICDM、ECML PKDD 等著名的工作组以及越来越多的国际会议都在研究探讨社区发现的问题。

社区发现技术在数据挖掘和探查性分析中是一种非常重要的技术。研究大型复杂网络，更加关注搜索和发现潜在的网络社区，这是研究中更重要的方面。主要涉及的领域有：市场学、数据挖掘、社会网络分析、统计学、机器学习、空间数据库技术和生物学等领域，其应用非常广泛。

在线社会网络相比其他在线网络而言，则是更能影响人们现实生活关系的网络。心理学家和社会学家研究大尺度社会网因其发展也有了较大的提高，对他们在这些网络中寻找新形式的集体或个人行为有许多帮助。社会学家分析非在线社会网络会借鉴在线社会网络，或者研究在线社会网络在新的社会行为特征，参考在线社会网络拓扑结构研究的基础。信息社会的一些急需回答的问题在社会网络分析的一些初步应用上有了答案。例如：Bany在其文献上用社会网络分析的思想和方法研究了现代社会中人际关系的变化特征。在线社会网络的研究有跟现实社会网络密切相关的动力学，网络演化规律，结构特性等方面的主题。

最近几年，关于复杂网络的研究中，复杂网络社区发现算法的研究设计已成为重中之重。

首先，社区发现技术的实用价值非常重大。例如，在社会网络中，社区代表是真实的社会团体，社会团体内部的每个人都具有相同或类似的背景和兴趣；在引文网络中，若干个论文的集合组成一个社区，且每个社区中的论文代表的是一个相同的主题；在万维网中，社区发现的结果是一些网站的集合，但是每个网站 集合讨论主题都是相同或类似的[2][3]；在电子电路网络或者生物化学网络中，社区发现的结果是一些功能单元，同一类功能单元被划分到同一个社区中 [4]。发现这些网络中的社区不仅为个性化服务、信息推送，提供基本的理论根据，而且有助于加深我们有效的理解和帮助这些网络的开发。在如今的信息时代，随着越来越普遍存在的社区，以及越来越方便的发现技术，社区发现技术的商业价值更是越来越大。

其次，社区发现技术的发展在一定程度上影响了对复杂网络的研究。在实际网络世界中，很多处都有复杂网络，它对社区发现技术有很多影响。而且复杂网络和社区发现技术彼此之间存在非常紧密的关联。过去的一些日子里，众多学者发现这些网络都是由若干个“社区”构成的，经过认真分析研究之后，发现这些网络共同具有一个性质，即这些网络具有一定的物理意义和数学特性，具体地说来，虽然社区之间的节点连接相对较少，但是社区内部节点之间的连接却十分紧密。社区发现技术的发展，使我们对大型复杂网络有了更加清楚的了解，同时社区发展技术也从另外一个角度推动了我们对复杂网络的研究。

最后，社区发现技术对于理论研究具有非常高的学术价值。广义上说，我们可以通过研究所发现的社区内部结构较为紧密的社区，利用社区发现的结果以及思路，以不同的眼光去研究其他领域。以专家推荐为例，社区发现技术可以很方便地帮助我们在某一研究领域找到关系十分紧密的专家。不过，从发现的效率、效果上来看，目前我们还有很多工作需要去做，因为目前的社区发现技术都具有局限性。特别是最近几年，许多研究社区发现的技术和方法都被应用到各行各业，其方法的优势和劣势经过实际的验证之后也被完全地暴露了出来。目前，社会领域中的社区发现，在许多国家已经成为学者的研究重点对象，因为社会网络规模对社区发现方法的效果和效率有较大影响，网络规模越大，影响也随之增大。

以万维网为例，我们按照社区来阐述万维网的一些优点：

第一，万维网中的所有社会活动的代表是社区，我们通过了解存在于万维网中的知识信息来深入研究社区的方式，并了解网络信息组织结构的发展状况；社区为内联网和因特网的相关服务提供了很好的门户。

第二，社区可以为用户提供一些可靠的有价值信息。社区可以帮助用户挖掘自己感兴趣的信息，通过对网络社区信息进一步挖掘，不仅可以发现对我们个人推荐的指导，而且还可以使我们可以进行方便的智能搜索和浏览信息。

第三，作为社会性网络的万维网，社区代表了万维网的社会活动。该技术有着非常重要的作用，例如在一些特殊的领域，以犯罪侦查为例，从侦查犯罪的视角出发，我们可以利用公安机关里已经记录的嫌疑人交往数据，通过对这些数据的有机分析，将犯罪学的知识和社区发现技术相结合，加入一些人工处理过程， 经过计算机最后的分析，我们就可以得到一些黑社会组织等犯罪团伙的信息，从而减少了公安机关犯罪侦查的工作难度。

最后，消费者可以轻易地在相关的销售商中准确地找到社区的概念。我们可以知道社区各个商家感兴趣的特定客户，有利于我们进行筛选，通过发现的社区来评估因特网的社会性和知识性，如果用户对某个方面感兴趣，也可以研究这些用户的组成形式。例如在电信业务行业，我们可以通过社区挖掘出一些客户间的紧密联系，并为客户提供有针对性的服务，可以更好地提高企业的效率。

总而言之，社区发现技术有着非常重要的研究意义，它已经成为社会网络分析、信息检索和数据挖掘等许多科学领域关注的重点。

1．2国内外研究概况

复杂网络中的社区发现具有相当大的理论和现实意义，当前科学家已经提出和发现了许多社区探测方法。

基于图论中二分法算法的主要思想是将图中的节点划分为给定数目的若干个子集，要求划分后各子集间连边数目最小，从而使得子集中节点间连边数目最大。该问题已被证明为NP难题，所以人们提出了各种以求得问题的近似解的算法。在各种算法中，Kernighan-Lin算法和谱方法(spectral method)是两种典型的算法。

二十世纪七十年代初期，Kernighan和Lin提出了采用试探优化方法来发现网络中的社区结构，该算法基于贪婪算法原理，简称K-L算法[5]。算法基本思想是，引入效益函数Q，计算交换网络中不同社区之间的节点或者将节点划分到其他社区中效益函数Q的值，选取使Q值最大的网络划分。如果网络中节点数量非常大，则该算法的时间复杂度很高。

其中，谱方法将社区划分问题转化为优化二次型问题，通过计算图的拉普拉斯矩阵的第二小特征向量来优化预定义的“截”函数[6]。二十世纪九十年代，Pothen等提出一种划分网络为两个社区的二分法，该方法基于图的拉普拉斯矩阵的谱特征[8]。算法应用第二小特征值所对应的特征向量，将社区中的节点根据特征向量中每个值的正负将对应节点划分。

Girvan和Newman2002年在社区发现中引入边介数的概念，然后基于边介数对网络中节点进行分裂，该算法即为GN算法[7]。算法实现社区划分的基本思想是将网络中介数最大的边依次移除，通过去边实现社区发现。2004年Newman将GN算法扩展到加权网络[8]。Newman基于贪婪原理提出一种与去边方法相对 的凝聚算法，该算法依次计算社区间的模块度，并使它连续增大，复杂度为mnn，称为快速算法[9]。Newman、Moore和Clauset等人基于Newman快速算法，提出了一种新的贪婪算法即CNM算法[10]。CNM算法采用二叉堆数据结构存储社区之间的模块度值，其复杂度为nlog2n。2006年基于模块度矩阵，Newman提出一种谱社区划分算法[11]，并于两年后把该算法扩展应用到有向网络中[12]。

Tyler等人在2003年发现，为提高GN算法的计算速度，从网络中的某个节点集内的节点出发，然后计算边介数算法速度有明显提高，进而提出了一种更高效率的算法[13]。

2003年，Wu和Huberman将电阻网络性质应用到社区发现中，提出W-H算法，该算法可以确定包含指定节点的社区[14]。算法将网络中的边想象成导线，导线以电阻值为单位。在网络中任意选择两点加上电位差，求解Kirchhoff方程，可以确定某个电位值处的节点，然后根据某个节点所处电位的所属范围即可确定所属社区。

2005年，Latapy和Pons基于随机游走策略提出了一种社区划分算法。在该算法中，规定初始每个节点都为一个社区，然后根据某种游走策略，使节点逐步向与其所在社区之间的平方距离均值最小的社区游走，划分到新的社区，逐步计算，逐步更新社区之间的距离[15]。

基于随机游走的动态社区发现算法，可以借助随机游动来进行[16]，提高统计结果的精度。李强等人[17]提出：样本数据集（图顶点）可以被看作是随机游走的agent，根据某些随机游走规则，它每一步移动的方向为在所有邻接点中随机选取一个移动单位距离ΔU，图形的尺寸和形状会随时间不断变化。随着样本点的连续移动，同类样本点逐渐聚集在一起，不用类样本点彼此远离，从而自动形成集群。

Zhou[18]使用随机游走来定义节点对之间的距离、整体吸引子和局部吸引子概念，且很明显社区一定是最小子图。这种方法的时间复杂度为O(n3)。将算法应用于Zachary的空手道俱乐部实验中，表明了该方法的有效性。Zhou[19]也提出了节点间的相异度度量方法。图最初是作为一个单独的社区，相异度小于阈值的节点中的被划分到同一社区，分区在划分的过程中逐渐减小。这个算法的时间复杂度仍然是O(n3)。

Hu等人[20]设计了一种基于节点之间的信号处理图聚类技术，节点对应于同一个社区的邻接向量，这些向量由模糊k-means聚类来划分。最佳聚类为向量在 同一个社区的平均最短距离何不同的社区中的平均最长距离。算法的时间复杂度为O( T(+ 1) n2 )，是图中度的平均值。

Van Dongen

[21]利用Markov聚类算法，模拟扩散过程。从随机矩阵R开始，

元素Rij表示随机矩阵的i到j的随机游动的概率。矩阵R的每一列元素总和为1。算法每次迭代包括以下两个步骤扩张和膨胀。若干次迭代后，具有优化模块的矩阵趋于稳定。即使是稀疏图，进过迭代，矩阵也会变成稠密图矩阵。该算法的时间复杂度为O（n3）。

目前要划分社区的网络处理的都是带正值的网络，但是还有些符号社会网络，除包含正联系外，也含有负联系。1996年，Doreian和Mrvart在充分研究符号后，利用贪婪策略政策和局部搜索方法，提出了一种对符号网络的社区发现方法[22]。Yang等在2007年，基于代理的启发式方法，提出了一种划分符号社会网络的方法，该算法被叫做FEC算法[23]。

无论是运用经典的图论方法，还是基于社会学分裂、聚类算法，都是将网络中的节点划分成不同的社区，社区间不存在重叠节点。但是，在现实中，社区之间常常存在相互关联，并且有重叠。也就是说，多个社区乐意共享相同的节点。所以，如果按是否存在重叠节点来划分，社区发现主要分为非重叠和重叠社区发现两方面[24][25]。而非重叠社区发现的发展更加相对成熟，利用非重叠社区一些方法进行改进，进而应用与重叠的社区发现。CONGA[26]将重要节点复制为多个节点，然后将每个节点划分到合适的社区，从而发现重叠社区结构。

Baumes等人基于局部优化的思想，给出了一些局部优化函数，这些函数基于边密度评价社区结构，并按照一定策略对所有社区进行局部优化，将最终的优化结果作为社区发现的结果[27][28]。由于一个节点可能通过不同的优化过程中加入社区，因而可以实现重叠社区发现。

Palla等人2005年在文献中提到上述问题；并给出了一种基于派系的重叠社区发现算法（Clique Percolation Method）CPM，该方法可以找到重叠的社区结构，并应用到蛋白质网络、通讯网络和合著网络的结构分析中[29]。有学者很快将派系过滤算法加工应用到二分图[31]和有向加权网络中[30]，在此基础上Kumpula等人[32]提出了派系过滤的快速实现算法。然而，派系过滤算法在实际应用中依赖参数K的选择，选取不同的K值得到的网络社区结构具有很大的差别，因此存在一定的局限性。

2007年Gregory将GN算法应用于点介数，提出了一种分裂复制点介数最高的节点的社区发现算法Conga[26]，算法在采用传统的GN算法进行社区发现的基础上，首先分裂复制出最高点介数的节点的多个副本，社区发现完成后再合并分裂的节点。由于被分裂的节点最终划分到了不同的社区，从而实现了重叠社区的 发现。

Evans等利用边图与点图相互转化的思想，将初始网络中的边看做点来处理，将点图转换成边图，然后进行社区发现，最后再将边图还原成原来的点图[33]。将边图中的节点还原为边后，可以发现不同社区间的某些边可能与同一个节点有连接，该节点可以被认为是重叠节点。文献[28]利用边图转换的思想采用图谱分割的方法同时得到了多个社区。

2009年，V. Nicosia等人[34]扩展模块度的定义到有向网络，使模块度更具有一般性，得到模块度为Quv，并提出了节点属于各个社区的隶属系数(belonging

coefficients)，使得重叠社区的判断具可行性，但是该方法在共享边对各个社区的贡献权重的判断上还存在随意性。

Shen Hua-wei等基于凝聚的思想同样提出一种能够探测重叠性和层次性的方法EAGLE[35]，该方法凝聚的对象不是网络中的节点，而是网络中的极大团。极大团指不能被划分为子团的最大节点集。

Lancichinetti等基于适应度函数局部最优化的思想，提出一种既可以找到重叠社区又可以发现层次结构的LFK算法[36]。在算法过程中某些节点可以同时被划到多个社区中，从而实现重叠的发现，还可以调整α的大小实现社区层次性的发现。

2010年，王莉提出了一种基于共享邻居节点的社区发现方法EAGLE，该方法可以发现分层重叠社区[37]，方法主要确定的节点的邻居域关系来发现重叠的社区，而不是研究网络中直接相连的节点间的关系。该方法考虑节点的邻居域关系重叠，因此具有重要的指导意义。

在极大团思想中，社区被定义为一系列相邻的k 完全图的集合，CPM 的基本思想是社区是由k 完全图在其多个邻接k 完全图上滚动而来的。Kumpula 等人[38]对CPM 进行了优化，提出了时序性极大团过滤算法( sequential CPM，SCP) 。该方法不仅加速了极大团过滤算法，而且成功地将极大团思想应用到了加权网络中。在此基础上，Shen 等人[39][40]将极大团思想与层次聚类方法相结合，提出了EAGLE 算法。该算法将网络中大于某一阈值的k 完全图凝聚为谱系树，通过cover 评价社区质量，选取切割点以得到最佳社区结构。算法的优点是能预测网络的动态变化，能找到网络中的重要社区。缺点是不能揭示网络层次结构，寻找极大团复杂度较高，发现过多的重叠。

层次聚类算法主要是利用相似度计算进行社区发现，它认为处于同一社区内的两节点应该等价或者相似度很高，因此，如何衡量两个用户节点之间的相似度成为层次聚类社区发现的关键。目前典型的两种方法是基于节点属性相似性社区发现算法和基于共有邻居相似性社区发现算法。[41] 文献[42]基于“六度分割”理论以及Dijkstra算法，提出了一种新的社区发现算法。基于六度分割理论可以保证所找到的两个节点之间的路径不会太长，最大值为六。首先找到网络中两个节点之间的所有路径，将找到的所有路径按从端到长的顺序进行排列，其中根据Dijkstra算法找到的是最短路径Pathmin。设定一1Pathmin个阀值，其中小于长度的路径中的节点划分一个社区。

此方法的不足，由于此方法是基于“六度分割”假设原理设计的，当起始人和目标人为同一个研究领域的研究员时，发现的人群为同一领域的可能性较大，但当研究员从事不同多个领域研究时，找到的人当然也是“五花八门”此外，如果数据规模庞大，将所有研究员两两组队来发现所有的社区，那样工作量是巨大的。此算法的优点是准确度较高，能揭示网络的层次结构，优化后可发现大规模网络中的重叠社区。缺点是对于不好的划分，不能回溯地进行修正。

2.1复杂网络

在网络理论的研究中，复杂网络是由巨大数量的节点和节点之间复杂的连结关系共同组成的网络结构。用数学语言表达，即一个图有足够复杂的拓扑结构特征。简单网络与复杂网络相比，不具备复杂网络的结构特征，并且这些特征经常出现在现实世界网络结构中。复杂网络的研究是现如今科学研究的一个热点，现实中各种高复杂度的系统，如互联网网络，神经网络和社会网络都与复杂网络的研究有着密不可分的关系。

2.1.2复杂网络的重要性

有许多科学家感兴趣的系统是有多个独立的部分或成分组成的。如由数据把电脑连接起来的因特网，由认识和社会关系连接的人组成的社会网络。

这些系统的很多方面都值得学习。有些人关注的是其中单个成分的本质，如一台电脑是怎样工作的，或者一个人是怎样感觉并反应的。而有些人关注个体之间的连接或交集的本质，如互联网使用的通信协议，人类友情的不断变化等。这些相互影响相互作用的群体还有第三个方面，这方面经常被忽略但是对于研究系统的行为表现来说又是最总要的，即在系统内成分间的连接的模式。

网络是把一个系统精简成一个抽象的结构，这个结构仅仅体现了这个网络的基本连接模式，它是显示网络的简化。网络中的结点和边可以用附加的信息来表示，如名字或强度，可以用来获得系统更多的细节。但是在简化的过程中，会丢 掉很多信息，这既有它的坏处也有它的好处。

过去很多年，许多领域的科学家开发了一系列的工具如数学的、计算机的、统计学的来分析、建模以及理解这些网络。这些工具在网络的简化抽象形式下进行分析和计算，理论上可以应用于任何代表了一个系统的网络图中。因此如果有一个你感兴趣的系统，并且可以被转换成网络的形式，那么就有上百种已经开发好并且为人所熟悉的方法可以用来分析这个系统。当然并不是所有的方法都能得出有效的结果，这取决于要分析的系统和要分析的特定问题。但是，毫无疑问一个试定的网络系统问题已经存在了一种方法解决。

2.3复杂网络分析

复杂网络有若干统计特征。其中包括小世界效应，小世界效应具有大的簇系数和小的平均距离，网络中节点之间的平均距离对数依赖于网络中的节点数。无标度性质，即网络中节点度服从幂率分布，具备幂函数或指数函数的形式，幂函数曲线具有右偏性，网络中节点度的分布区间非常小，所有节点与节点度均值相差不大。网络的聚集性或网络传递性，是指两个节点是同一个节点的相邻节点，那么它们有较大概率仍然是相邻节点。

2.3.1中心性

在网络中节点的度是指连接它的边的数目。如在一个关于友谊的社会网络中，一个单独个体的度是他在这个网络中朋友的数目；在因特网中，度可能是一台电脑的数据连接数，如路由器或其他设备等。在很多情况下，一个网络中拥有最高度数的节点，即拥有最大连接数的节点往往在这个系统中扮演了很重要的角色，因此关注网络中节点的度能引导我们发现这个系统很多重要的特征。

(1)度在社会网络文学中有时候叫做度中心性，强调它作为中心性度量的用处。例如，在社会网络中，一个人与很多人有联系，我们自然而然的就会觉得他有很大的影响力，能更接近与某些信息，更有权威。

(2)简单的度中心性的自然延伸为特征向量中心性。我们可以把度中心作为对每一个节点的邻居节点都有的“中心性点”。但并不是所有的邻居都是等价的。在许多情况下，网络中的节点的重要性被连接到它的网络中的本身很重要的其他顶点增加了。这久是特征向量中心性的意义。例如：一个节点p有三个朋友，且他的三个朋友比较重要，另一个节点q也有三个朋友，但他的三个朋友重要性都比较低，所以，p的特征向量中心性比q高。在一个网络中，很多情况下，一个节点的重要性与它所连接的自身重要的节点有关。 (3)中心地位的一个非常不同的概念是中介中心，用于衡量一个顶点位于其他顶点之间的路径的程度。中介中心性高的节点，在网络中凭借自己对节点之间传递的信息的控制，可能有相当高的影响力。具有高中介中心性的节点的移除，将切断许多其他顶点之间的通信，因为它们位于很多节点之间的通讯路径上。如果一个节点处在其他越多节点的通讯路径上，则该点的中介中心度就越高。

(4)网络的另一个重要的中心性是接近中心性。它测量了一个节点到其他节点的平均距离。当一个节点与其他节点的平均最短路径很短时，接近中心性是一个比较小的值。这样的顶点可能更容易获取其他顶点中的信息或对其他节点有更直接的影响力。在一个社会网络中，例如，一个人用与他人之间有较小的平均距离，别人可能会发现，他的意见在社会上会比别人意见更迅速地传达给他人。

无标度模型有Albert-laszlo Baradasi和Reka Albert在1999年首次提出，现实网络的无标度特性源于众多网络所共有的两种生成机制：

（1）网络通过添加新节点而连续扩张；

（2）新节点择优连接到具有大量连接的节点上；

3.1引言

网络一个实用的价值就是网络中的簇或者社区。我们大多数人都非常熟悉网络中已经存在的社区，比如天涯社区，某大学的论坛等，在实际生活中还要很多看不见的社区存在，如在大的松散的网络中紧密联系的朋友群。朋友网中，可能存在派系、朋友圈、或者各种各样的朋友帮派，在这些组织之内成员之间联系紧密，但在组织之间联系很弱或者几乎不联系。如果是包含明显的划分或兴趣爱好的社区，我们想要了解这些社区，最好的做法就是把它们看成一个网络，划分社区。一个大的网络划分成多个社区的过程涉及不同的社区层次，划分社区的依据是网络中的数据，划分出的社区能帮助我们了解整个网络的结构组成。

图分割或社区发现都是指将网络中的节点按照网络中边的类型划分为组、簇或社区。但进行的划分都是组内节点紧密连接，组建只有很少几条边连接。图分割从十九世纪六十年代开始一直就是计算机科学的一个经典问题。这个问题就是把一个网络中的节点划分成给定数目的非重叠组，使组之间边的数目最小。

社区发现用来搜索网络中自然存在的分组，不论它们的数量或大小，是主要用来发现和理解大规模网络的结构的一种工具。社区发现最普遍的应用就是作为分析和理解网络中节点的工具。社区发现的目标是找到网络的自然分割。分组的大小不确定，在原则上从一个分组到另一个可能变化很大。一个给定的网络可能 分成几个大组，很多小组，或很多不同大小的混合物。在复杂网络中发现社区，实用价值重大。如在网络图中的节点的集群可能表明相关网页群体；在代谢网络中节点的集群可能表示网络内的功能单元。

3.2迭代二分法(Iterative Bisection)

在实践中，大多数图的分割方法基于迭代二分法。下面介绍两种迭代二分法，其中一个为基于贪婪算法的Kernighan-Lin算法。该算法为达到较优的网络划分，对所划分的子网内和子网间的边数进行优化。

3.2.1Kernighan—Lin算法

Kernighan—Lin由Brian Kernighan和Shen Lin在1970年提出，是最简单且最有名的图二分启发式算法。K-L算法的主要思想是：首先将网络划分成给定大小的两个组，交换满足条件的不同组间的节点对，使得组间连接最稀疏，组内连接最紧密。

3.2.2谱二分法（Spectral bisection）

从式3.2可以看出Laplace 矩阵中所有行元素与列元素的和都为0，因此，该矩阵总有一个特征值为0，且其对应的特征向量1。此时对应的分割粒径：

Rn1n2n2 (3.4)

拉普拉斯算子的第二特征值2不为0，当且仅当前网络是连通连接的。第二特征值2基于这个原因，有时称为网络的代数连通度(algebratic connectivity)

[46,47]。如果网络没有连通，且第二特征值2为零，在这种情况下，两个最小特征值是相同的，并且对应的特征向量是不确定的，任何两个特征向量具有相同的特征值的混合也是一个特征向量。然而这并不是一个严重的问题。如果网络不是连接的，有不止一个分组，那么通常我们对分割一个特定组件比较感兴趣，如最大的组成部分，或者将所有分组独立划分。

根据2中的值，所有正值对应的节点属于一个社区，所有负值对应的节点属于一个社区，据此将网络的节点划分为两个社区。因为从理论上可以证明，同一分组内的节点对应于2中的值近似相等。[48,49]代数连通度2是对切割尺寸的一个直接测量，且正比于它。代数连通度是网络容易划分程度的的测量。如果网 络具有良好的切割，则它较小；如果没有，则较大。

3.3.2 Radicchi算法

该算法与G-N算法原理相同，都是基于去边，与G-N算法不同的是，Raciddhi算法引进了边聚集系数（Edge Clustering Coefficient）指标。Radichhi提出了关于基于中介性的算法的变形。算法的基本原理是一样的，都是识别除社区之间的边，并且移除它们来得到社区结构。Radichhi发现位于很少连接的社区之间的边属于边组成的环的概率非常小，所以要求两条临近的边属于同一个分组中。因此识别网络中社区之间的边的一种方法就是寻找属于数目非常小的短循环的边。R发现长度为3或者4的环能得出最好的结果。重复去除属于很小数目的这种循环的边，最终能发现网络中包含的社区。因此，将1条边的边聚集系数定义为包含该边的三角环所占比例：

Cijzij1min(ki1,kj1)[50] (3.6)

其中ki表示节点i的度，kj表示节点j的度，zij表示网络中包含该边的三角环的个数。式3.6中的的分母表示包含该边的最大可能的三角环的个数。

这个算法很好的一个特性是它的速度。计算一条边所属的短循环是在局部范围内，并且对于所有的边来说进行这种计算的范围也就是整个网络的大小。因此，在最坏情况下，算法的时间复杂度为n个数量级。

该算法的不足是算法的计算依赖于网络中边所在的三角环，对于一个三角环很少的网络，算法实验结果比较差。经实证研究，非社会网络中三角环数量较社区网络较少，因此，Radicchi算法更适合应用于社会网络。

2，比基于边介数的G-N算法快了一3.4层次聚类法（Hierarchical Clustering）

层次聚类是社会学家研究社区发现所采用的的主要方法之一。算法首先定义一个相似度xij，依次计算网络中每对节点之间xij的值，依据xij值的大小，在网络中的节点间依次加上一条边。在此需指出，初始网络结构影响节点对间相似度的计算，而算法所加上的边与xij有关。

层次聚类并不是有很多变量和可选结果的一个算法种类。层次聚类是一种凝 聚技术，算法从网络中独立的节点开始，将它们组合起来形成群组。这跟前面讲的几种社区发现算法完全相反，前几种算法都是分裂方法，我们从整体视觉看待网络，然后将它分成几部分。

层次聚类的基本思想是基于网络结构，定义节点之间的相似度或连接强度，然后将距离最近的或最相似的节点组合成分组。下面看几种从不同角度定义网络中节点之间相似度的方法。

3.5W-H算法

将网络中的每条边想象成电阻为单位值的导线，且在网络中任意选择的2个节点上加上单位值的电位差，通过求解Kirchhoff方程，可以得到每个节点处的电位值。Wu和Huberman认为，如果网络可以被分解成2个社区，选定的2个节点属于不同的社区，所以潜在的电位波谱在连接2个社区的两端，将产生一个较大的差距。因此，我们首先确定一个潜在的最大间隙电位波谱的价值，然后根据各个节点的电位值决定节点所属社区。

3.6网络分析评价

上几节所介绍的集中网络划分算法均无法自己停止，即无法判断算法进行到哪个步骤所得的网络划分结果是最好的。为此Girvan和Newman[51]定义了一个评价网络分解满意度的指标，称为模块度（Modularity）。模块度是用来衡量一个网络所划分社区之间连接程度的指标。严格来说，模块度的值要比1小，且为正值。

类似于K-L算法，可以利用网络的模块度来设计出网络分解的贪婪算法[52]。

网络一个实用的价值就是网络中的簇或者社区。我们大多数人都非常熟悉网络中已经存在的社区，比如天涯社区，某大学的论坛等，在实际生活中还要很多看不见的社区存在，如在大的松散的网络中紧密联系的朋友群。朋友网中，可能存在派系、朋友圈、或者各种各样的朋友帮派，在这些组织之内成员之间联系紧密，但在组织之间联系很弱或者几乎不联系。如果是包含明显的划分或兴趣爱好的社区，我们想要了解这些社区，最好的做法就是把它们看成一个网络，划分社区。一个大的网络划分成多个社区的过程涉及不同的社区层次，划分社区的依据是网络中的数据，划分出的社区能帮助我们了解整个网络的结构组成。

上一章介绍了几种经典的社区发现算法，并且介绍了它们的应用范围和复杂度，由于社区发现的精度以及算法的复杂度，大大限制了它们在各方面的应用。很多网络节点并不只是简单的存在连接，他们之间的连接往往都带有权值，如Internet，一个比较中心的网页可能被其他网页多次访问到，那么在访问网页与被访问网页之间连接的数目就带有权值；再如，交友网络，人们在了解彼此的过程中，一来一去的问候和询问，他们之间交流的次数也带有权值，权值也高，说明两个人交往越密切，两个人的同质性就更大。

在此，提出一种基于网络中节点间紧密度的社区发现算法。该算法属于社区发现中层次聚类的范畴，层次聚类算法以节点之间的相似性作为度量指标。算法在网络中节点数不太大的情况下，时间复杂度非常好。实验结果表明该算法的实际应用效果也非常好。

社区发现可以发现人类社会网络中的社区，可以发现生物新陈代谢的社区，可以发现技术网络的社区，社区发现算法以这些模型为研究对象。现有的社区发现算法多从网络的拓扑结构角度来考虑社区划分，网络中节点之间交流频率这一重要指标常常被忽略。

目前层次聚类算法基于如果节点属于同一个社区，那么节点之间相似度很高的思想，主要利用节点之间的相似度来发现社区。因此，网络中节点之间的相似度计算问题成为层次聚类算法社区发现的重点。目前基于相似度的社区发现算法主要有节点属性相似性和节点共有邻居相似性两种。[53]

基于节点属性相似性的社区发现算法(NAS)基本思想是：对任意两节点计算属性相似度，并以此为依据判断两节点是否处于同一社区。NAS算法仅仅利用了节点属性的相似度来衡量衡量节点之间的紧密程度，这样就忽视了节点所在网络的拓扑结构。

基于节点共有邻居相似性的社区发现算法(CNS)基本思想是：利用两个节点共同拥有的邻居个数与两个节点拥有的邻居数总和的比值来计算节点间的相似 度。CNS算法在计算的时候忽略了这样一个事实：B是A的好朋友，B也是C的好朋友，但是他们和B之间的亲密程度不同，所以CNS算法计算出来的节点紧密度也不太准确。

1. 10，12,5,11,17,6,7,18,22,20,13,14,4,8,1,2,3,23,19,29,21,25,26,32,15,27,16,9,31,28,30,24,33,34

(3)基于节点联系算法

文献通过发现网络图中的超级密集核心区来得到网络社区的核心区，并以核心区为中心，通过添加联系紧密的节点得到我们的社区结构，然后对社区结构进行必要的合并和调整，以此得到最终的社区结构。依据社区内节点的联系边数定来义社区是否紧密，并把社区内联系边数与社区外联系边数之差的大小作为社区结构划分好坏的衡量标准。通过基于节点联系的算法，得到两个社区。节点 10，29 被错分到社区 1 中。

4.3.2 Sade恒河猴网

In1972，Sade发表了一项关于16个恒河猴的网络研究，其中包括9只母猴和7只公猴，不包括未成年猴子。社会学家们从猴子间的相互梳理毛发行为推断与研究猴子们之间的关系。实验不仅记录了在观察期间一只猴子为另外哪些猴子梳理毛发，而且记录了梳理的频率。实验结果就是一个比简单的二元邻接矩阵包含了更多信息的加权网络。梳理行为在猴子之间形成了一个有向的网络，如果猴子A给猴子B梳理毛发，则认为A到B之间有一条边，并且这个方向被认为是与猴子在群体中的地位有关。