关键词： 网络   社团结构   重叠社团   社团检测  

摘要： 网络,数学家们称其为图,它为许多复杂系统的结构提供了一个很好的抽象,从社会网络、计算机网络,到生物网络以及物理系统的状态空间。在过去的几十年里出现了许多确定网络系统拓扑结构的改进实验,但对实验产生的数据进行科学的分析,仍然存在本质的挑战。目前的社团检测中主要存在两个问题:一是不知道网络中有几个社团;二是网络中的顶点可能属于不同的社团,也就是社团中存在重叠结构。为了了解各种重叠社团检测算法的思想、实现步骤、优缺点比较、算法应用,文中对邻域重叠社团检测算法进行了深入的分析,以k-means算法分析了经济网络,同时采用Silhouette指标解决了最佳聚类数的问题,并通过仿真实验证明了此算法的可能性。

关键词： 复杂网络   社团   中心性   核矩阵   特征谱分   模块密度中心性  

摘要： 论证了社团检测函数模块密度的优化进程能转化为核矩阵的特征谱分.基于核矩阵最大特征值对应的特征向量,提出了一种新的中心性方法,称为模块密度中心性方法.与以往中心性度量方法不同,这种方法以模块密度检测复杂网络中的社团结构为基础,度量了第一个节点到它分配社团上的贡献,对社团的贡献越大,该节点的中心性值越高,反之亦然.通过合成网络和标准数据集网络,验证了该方法,并同其他中心性方法进行了比较,实验表明提出的模块密度中心性方法对网络中关键节点有更好的解和稳定性.进一步在计算机产生的两个大的随机网络和来自现实世界的两个大的复杂网络中,研究了模块密度中心性方法的统计分布.结果表明了提出的中心性方法能够刻画复杂网络的拓扑结构属性.

关键词： 复杂网络   社团检测   中心性度量   算法  

摘要： 近来，研究人员提出了许多在复杂网络中检测评估社团与中心性度量方法。这些方法为各领域的研究人员理解真实系统的构成，功能及动态演化进程提供了强有力的工具。然而，复杂网络拓扑结构的千差万别决定了中心性度量及社团检测本身是一种非常困难问题，而且对网络的划分已经证明是一种NP难问题，因此如何评估与检测网络社团与中心性，提出更加准确的检测与度量算法并对检测出的模块与中心性顶点进行功能解释仍是当前挑战性的工作。 为此，针对刻画复杂网络的中心性及社团结构两种重要性指标，本文主要研究网络中心性度量方法及社团结构检测的聚类算法，以及它们在现实世界网络中的应用： （1）在复杂网络结构分析中，中心性分析已经被证实是一种非常有价值的方法。该分析方法用来检测网络中的关键元素以及依据节点的重要性对网络元素进行排序，以便实验能够跟踪到有重要意义的候选节点。为了支撑这种分析我们讨论了多种经典中心性方法，并且在人工网络和实际网络中展示了它们的应用。这些方法的运用显示了在一个网络中有某种较强的关联，但在另一个网络中有较弱的关联。为此，我们对模块密度函数进行了关于核矩阵的特征谱分的优化进程，基于核矩阵最大特征值对应的特征向量，提出了一种新的结构化中心性方法，称为模块密度中心性方法。这种方法描述了每一个节点到它分配社团上的贡献。通过人工合成网络和标准数据集网络，展示这种方法的应用，并同其它标准方法进行了比较，实验结果显示该方法在网络中心性度量上具有较好的准确性及稳定性。同时在计算机产生的两个大图和来自真实世界的两个大的网络中，我们调查了模块密度中心性方法的统计分布，结果表明了提出的方法能准确反映复杂网络的拓扑结构性质。 （2）为有效地检测复杂网络中的社团结构，对评估与发现社团的模块密度函数（即D值）进行了优化。通过模块密度函数的优化进程，论证了模块密度函数被优化框定到广阔的谱分聚类方法中的矩阵松散最大化，并且提出了一种新的谱分算法，并对算法时间复杂度进行了分析。该算法允许自动选择最优的社团结构数目，在经典的计算机产生的随机网络及真实世界网络中检验了该算法。特别地，当网络中社团结构变得模糊时，实验结果显示这种新的算法在发现复杂网络社团上比基于模块密度的直接核方法及基于模块函数（Q）的谱分方法更加有效。 （3）为在权重化的网络中检测社团结构，我们推广模块密度函数D到权重形式（WD），并优化权重的模块密度函数到谱分聚类形式及权重的核聚类形式，同时，证明了基于权重化的模块密度函数的谱分聚类方法和核聚类方法在数学上的等价性，利用这种等价性，提出了一种新的基于特征向量核聚类检测复杂网络社团方法，并对算法的时间复杂度进行了分析。该方法能在边与顶点同时权重化的复杂网络中检测社团结构，并且比直接的谱分聚类方法或直接的核聚类方法检测社团更加准确。 （4）针对复杂网络结构特点，提出了一种新的半监督核聚类检测网络社团算法。通过半监督聚类HMRF模型对模块密度函数D进行了半监督聚类优化，同时论证了模块密度函数的半监督聚类与核k-means方法的等价性，同时基于模块密度的核算法也被提出来，在此基础上提出了一种新的半监督核聚类检测复杂网络社团算法。在经典的计算机产生的网络和已知社团结构的真实世界网络上同其它方法进行了比较，实验结果表明，该方法比未加入半监督的算法具有较高的准确性。 本文研究复杂网络中心性度量及社团结构检测相关算法，这些方法能帮助人们理解复杂网络的构成，功能特性及对复杂网络控制、预测、变化、演化具有现实的指导意义，从而为各领域研究人员针对具体问题制定更加可行的方案。

关键词： 大规模网络   社团结构   模块度优化启发式算法   社团检测  

摘要： 近年来,社团结构的研究已经取得和积累了一些优秀的思想和成果,尤其是大规模网络的社团检测在研究复杂网络结构与功能中有着举足轻重的作用。但社团检测依然存在几个主要的问题：1.对于给定的一个网络,在划分社团前,我们不知道其能划分成几个社团；2.有些算法往往对特定的网络有效,当其分析其它网络时,可能就没有那么完美；3.寻找结构与功能的联系在实际网络尤其是大规模网络中的应用较少。 针对以上几点问题,本文做出了如下几方面贡献： 1.大规模网络社团结构的表现形式：局部社团划分关注于子图,而其中的强社团和弱社团在划分社团时得到了广泛的应用。社团的全局划分基于空模型,是在我们期望的顶点的度与原始网络中顶点的度保持一致的约束条件下,让其边随机连接得到的。基于顶点相似度的社团划分是根据顶点相似度的分析,将没有直接连边的顶点划分到一个社团。特别地,大规模网络社团结构中的重叠社团划分可以通过归一化互信息,描述顶点在社团中的隶属度。 2.大规模网络社团检测算法：派系逾渗算法,是通过对完全子图的处理划分出重叠社团；局部优化算法,通过“局部信息”的发现,在不了解全部网络信息的情况下,探测网络的部分达到社团划分的目的；信息论算法,以通信过程作为框架,并运用了归一化互信息,通过寻找最大互信息的值而达到划分社团；线性规划算法,通过寻找最优的模块度而划分社团。此外,分析顶点与其它的块内顶点之间存在相似度而划分社团也是一种新的研究方向,块结构模型就是使用此原理达到划分社团的目的。 3.运用模块度优化启发式算法划分空手道俱乐部网络、大学足球俱乐部网络和区域贸易网络等,并对其结构和功能做出一定的分析。特别地,针对贸易网络中自由贸易区往往表现为一个社团的特点,我们以221个国家或地区为研究对象,对贸易协定与地域之间的关系做了大量的实证研究。首先,从世贸组织网站上采集了区域贸易协定中国家之间贸易的数据;其次,通过模块度启发式算法进行社团划分,共得出7个主要的贸易区,其中欧盟自由贸易区的社团表现极为明显；最后,从社团结构的表现形式推断实际区域间的贸易情况。 本论文研究得到了国家自然科学基金项目的支持,项目名称《开放式空间加权网络的拓扑演化及其优化设计》,项目编号：11075057。

关键词： 可视化   复杂网络   社团   骑墙节点   层次化   重叠社团  

摘要： 近年来，复杂网络研究受到了不同学科研究人员的广泛关注，其发展极大的促进了人们对现实复杂网络系统的理解。复杂网络研究者普遍认为网络中存在社团结构，即整个网络是由若干个群或团构成的，在同一个群内节点之间的连接非常紧密，而各个群之间的连接却比较稀疏。揭示网络中的社团结构对于了解网络结构及分析网络特性具有极为重要的意义。目前，虽然复杂网络可视化能以直观的方式表达网络节点之间的关系且已日渐成为复杂网络分析必不可少的工具，但是对于复杂网络社团结构的可视化工具特别是针对层次化重叠社团结构的可视化工具却较少。 针对该问题，本文从复杂网络的社团结构出发，对网络中普遍存在的层次化重叠社团结构进行了深入的研究，侧重点在于基于社团检测的大型网络可视化方法。本文首先尝试对现行国内外常用的复杂网络可视化工具进行了总结。其次，本文探讨了网络社团的层次性及重叠性，针对真实网络的社团结构一般同时具有层次性及重叠性的事实，本文尝试将社团的层次性及重叠性同时进行研究并提出了一种适用于稀疏网络的快速层次化重叠社团检测算法。最后，基于对社团结构及现行复杂网络可视化工具的深入了解，本文在基于社团检测算法的基础上，提出了一种层次化社团划分与骑墙节点显示的可视化方法，并用Java开发出了一套应用于大型复杂网络的可视化平台Visualizationbased on Community Detection (VCD)。 本论文所作的主要贡献如下： 1.对比分析了复杂网络可视化领域比较有代表性的工具，鉴于目前学术界并没有对复杂网络可视化给出一个统一的标准，本文引进了CIShell框架，并对网络可视化工具的使用及开发进行了总结； 2.提出了一种适用于稀疏网络的快速层次化重叠社团检测算法，该算法循环的把网络中连接较为紧密的节点进行合并，聚集向上直至得到最优的模块度并将原始网络划分为若干具有层次性的社团。与一般的层次化社团检测算法不同，该算法在每一次迭代过程中允许节点归属于一个或多个社团以此发掘网络的重叠社团结构； 3.提出了一种层次化社团划分与骑墙节点显示的可视化方法，该方法在使用基于模块度指标优化的社团划分算法检测层次化重叠社团结构的同时，通过节点及连边的关系分别对网络社团与骑墙节点进行抽象显示，避免了大型网络可视化研究中经常面临的节点与边的重叠堆积问题； 4.本文的可视化平台综合采用了圆形布局与聚类布局，能模拟网络层次化社团结构及骑墙节点结构的动态演化，并将移动平台上使用甚广的Cover Flow技术应用于可视化中，提供用户不同的可视化效果，其中，基于层次化社团划分的可视化效果充分展示了社团间的关系，而基于骑墙节点检测的可视化效果充分展示了节点的多维社团属性。该平台还提供了丰富的交互功能，帮组用户从不同层面查看网络结构信息。

关键词： 蚁群算法   搜索偏离   选择策略   社团检测  

摘要： 蚁群算法是一种求解复杂问题的元启发式算法,它是意大利学者M. Dorigo, ***等人于20世纪90年代初,受到自然界中蚂蚁在觅食过程中所表现出来的路径寻找模式的启发率先提出的。从M. Dorigo首先设计出了蚂蚁系统（Ant System, AS）开始,许多国内外学者对这类算法进行了不断的改进,到目前为止已近形成了一套成熟的框架,由于蚁群算法所表现出全局性、稳健性等优点,蚁群算法的成功不仅表现在处理各种组合优化问题上,而且也体现在处理优化题时所取得的极佳的性能。它已广泛的应用在各行各业,并且取得了非常不错的成果。 由于蚁群算法到目前为止主要成功大多是在实验层次上,虽然它的性能在不断的提高,但是在理论上还未像演化算法、遗传算法、模拟退火等算法那样具有严格的理论基础。对蚁群算法理论方面的研究,目前主要集中在它的收敛性证明、欺骗性问题、时间复杂度估计等方面。虽然初步取得了一些理论成果,但还存在着一些非常重要的问题亟待解决,如搜索偏离性的问题。蚁群算法在求解一些问题的过程中存在着两种搜索偏离：一种是正搜索偏离,一种是负搜索偏离。产生这种情况的主要原因是源于算法本身或者问题本身的性质。我们期望的情况是蚁群趋向于正搜索偏离,它可以引导蚂蚁的搜索向着最优解方向前进。但是,在许多情况下蚁群会产生负搜索偏离,它会使我们在求解问题的时候最终不能收敛到全局最优解。如果不能够对这种偏离进行估计和避免,我们在用蚁群算法求解一些优化问题时,我们却不能意识到自己所得到的解可能不是一个最优解,这在许多实际应用中是十分有害的。 本文中主要对蚁群算法的搜索偏离性进行了全面的研究,提出了反馈性偏离的概念,提出了一种衡量偏离大小的标准。我们提出了一种改进的蚁群算法用来避免搜索偏离。为了纠正搜索偏离所产生的负作用,加强解群体的多样性,我们提出了三种改进的蚂蚁路径选择策略,以增加解的多样性,使改进的算法能够有效的避免搜索偏离。最后我们还将蚁群算法应用在了社团检测上。 本文的研究工作和主要研究成果有： （1）在已经发现的蚁群优化算法的两种搜索偏离（即表征性偏离、构建性偏离）之外,我们提出了第三种偏离,即反馈性偏离。我们给出了反馈性偏离的定义,并且举例说明了反馈性偏离的存在。我们针对这三种偏离提出了一种衡量偏离大小的的统一的评价标准,并对该评价标准进行了测试,用实验证明我们的评价标准的合理性和有效性。 （2）提出了一种BAACO （Bias-Avoiding ACO）算法来避免蚁群算法产生的搜索偏离。我们分别对传统的蚁群算法和BAACO算法在不同问题上的收敛性进行了理论证明,实验结果也充分说明了我们改进的蚁群算法可以避免搜索偏离,最终收敛于全局最优解。 （3）为了纠正搜索偏离所产生的负作用,加强解群体的多样性,我们提出了三种改进的蚂蚁路径选择策略,以增加解的多样性,使改进的算法能够有效的避免搜索偏离。我们以n-digital问题为例,用实验来验证三种选择策略的有效性。实验结果表明我们提出的方法可以有效地增加解的多样性,克服了搜索偏离产生的影响。 （4）我们将改进的蚁群算法用于解决对复杂网络的社团检测问题,我们用人工合成的数据集,和真实数据集对算法进行了测试,试验结果表明我们的改进的蚁群算法都能获得非常高的准确性。

关键词： 动态网络   增量方法   密度扩展   社团检测   社团演化分析  

摘要： 复杂网络作为一种描述和分析现实复杂系统的重要工具而广受关注，学者们已经对网络的物理意义和数学特性等方面进行了深入地研究。复杂系统是随着时间不断变化的，将不同时刻的系统状态进行采样建模便形成了本文研究的复杂动态网络。对复杂动态网络进行社团检测和演化分析，有助于提高人们对整个网络特性和发展趋势的认识，具有重要的理论和实际意义。 复杂动态网络往往具有多个时刻，用传统的方法需要对每个时刻分别进行社团检测，然后分析社团之间的关系，这样不仅容易在相邻的时刻产生很大偏差的社团划分，还导致很高的时间复杂度。增量方法将前一时刻的社团检测结果作为下一时刻的输入，可以有效地降低时间复杂度，同时还可以保证前后时刻的社团检测结果具有较好的一致性。本文提出了一种增量和密度相结合的社团检测方法，对大部分增量相关节点进行基于社团归属度的调整，对新增节点进行局部的基于密度的扩展，克服了一般增量方法认为在不同时刻社团数目固定和不能产生新社团的缺陷。 本文在人工合成数据和真实网络数据进行实验，结果表明本文提出的算法可以在近似增量方法的时间复杂度，取得比增量方法更好的社团检测效果，具有良好的社团发现能力，可以用于大规模复杂动态网络的社团研究。此外，本文对真实网络中得到的社团结果，进行整体的社团演化分析，并对长期保留的社团进行节点生命周期的分析，发现了一些具有特定意义的社团结构。

关键词： 复杂网络   健壮社团   贝叶斯网络  

摘要： 健壮社团是复杂网络社团结构中稳定部分,健壮社团发现是非常困难的;提出了一种基于贝叶斯网络推理的健壮社团发现算法,把健壮社团发现问题当做推理问题,构造一个贝叶斯网络,根据结点的度来设置贝叶斯网络相关参数,然后将某些内部联系特别紧密的网络结点设为证据结点,在贝叶斯网络中进行信度传播,得到在已知证据的情况下其余结点属于该健壮社团的概率,最后得到复杂网络中的所有健壮社团;对足球俱乐部网络(115个结点)和随机网络(128个结点)的测试结果表明所提方法能有效地检测出复杂网络中存在的健壮社团,具有较好的应用价值。

关键词： 复杂网络   社团结构   近邻传播   信号传递   节点相似度  

摘要： 社团结构是众多复杂网络的统计特性之一,挖掘网络中存在的社团结构日益受到人们的普遍关注。网络中的社团结构检测本质上类似于传统机器学习领域的聚类分析,其关键问题在于如何定义网络中节点间的相似度。首先提出了基于节点相似度的节点分裂算法SGN,相比传统的基于边界数(betweenness)的节点分裂算法GN,SGN在速度和精度上都有明显改善;接着,在利用各种节点相似度计算方法得到节点间的相似度之后,采用几种经典的聚类分析算法对网络进行社团划分,在模拟数据和真实数据上的实验表明:基于网络拓扑结构信息的signal和regular方法优于基于网络节点局部信息的Jaccard方法,而且对于复杂网络社团划分问题,如果选择好的网络节点相似度构造方法,已有的基于相似度矩阵的聚类分析算法都能快速有效地对网络社团进行划分。

关键词： 复杂网络   社团结构   社团检测   随机游走   有向网络   无向网络  

摘要： 复杂网络研究作为一个新兴的学科方向,极大地吸引了来自不同学科研究人员的广泛关注。对复杂网络的定性和定量特征的研究,有助于揭示复杂网络表示下的不同复杂系统中普遍存在的一般规律,在生物科学、社会科学等诸多学科中具有重要意义。社团结构是复杂网络的一个关键结构规律,因此准确分析复杂网络的社团结构是复杂网络研究中的一个非常重要的课题。 在复杂网络社团结构的分析研究中,模块度度量(及其变种)起了很重要的作用,催生了一大类重要的社团结构分析方法。但是这类通过对模块度度量(及其变种)优化来获得网络社团划分的方法存在分辨率问题,从而极大地限制了基于模块度方法的有效性和应用广度。 另一方面,目前社团结构分析研究主要集中在无向网络上,系统地直接分析有向网络社团结构的研究还远远不及对无向网络社团结构的分析研究。实际上,当前有向网络社团结构划分的普遍做法是通过简单地忽略有向网络中边的方向,将有向网络当成无向网络分析。这种方法在大多数情况下由于忽略了有向网络中边的方向包含的重要拓扑结构信息,从而无法正确有效地划分网络的社团结构。另外,在有向网络上扩展多数无向网络社团结构的分析方法往往不是简单的工作。 本论文从模块度度量的相关问题出发,将无向二元网络上模块度优化时的分辨率问题的分析扩展到无向加权网络中,并在此基础上提出了一种结合网络预处理的增强型模块度优化社团结构分析方法。通过分析无向网络上的模块度优化产生分辨率问题的条件,提出通过有效地获得关于社团之间边的信息来处理模块度优化时可能产生的分辨率问题。基于网络上的动力学过程反映网络的潜在结构这一事实,利用无向网络上的随机游走过程获取关于社团内部边和社团外部边的信息,并通过边的迭代重加权操作使得网络边的权值不断向社团内部集中,而社团之间的边权值越来越小,从而有效地克服模块度优化时的分辨率问题。实验分析表明,这种结合了网络预处理的无向网络社团分析方法极大地增强了基于模块度优化的无向网络社团结构分析方法的有效性和应用广度。 针对传统的有向网络社团结构分析方法简单忽略边的方向将使得社团划分不准确的问题,提出了一种基于有向网络嵌入的有向网络社团结构分析方法。该方法通过在有向网络上扩展无向网络的网络嵌入分析,从有向网络嵌入目标函数关联的拉普拉斯矩阵中分离出包含了边的方向信息的对称矩阵作为有向网络对等的无向加权网络的邻接矩阵,并导出一种关于有向网络社团结构划分的新模块度定义。一方面,新模块度度量进一步解释了有向网络社团的另一种物理内涵:同一社团内的结点是最大程度保持了有向网络局部结构的相邻结点集合;另一方面,它建立了有向网络与某种无向网络的联系,这种联系表明有向网络的社团结构可以通过应用已有的无向网络社团结构分析方法可靠并且有效地在所导出的无向网络上分析得到。 进一步扩展了基于有向网络嵌入的有向网络社团结构分析方法的分析思路,提出了一种基于边的方向信息抽取的有向网络社团结构分析方法。该方法基于具有社团结构的有向网络上的流运动将更加容易地在社团内部结点之间进行的事实,通过有向网络上的PageRank型随机游走过程有效地抽取有向网络边的方向包含的信息,并采用适当的相似性函数将其转化为边的权值与有向网络中边的互联性集成共同定义有向网络的社团结构。在抽取足够多的关于边的方向信息后,通过忽略边的方向将有向网络的社团划分问题等价为所导出的无向加权网络的社团划分问题,在保持社团结构划分准确性的同时有效地简化了有向网络社团结构划分问题的分析,避免了无向网络分析方法常常难以直接扩展到有向网络社团结构分析中的问题。 在分析前述关于无向网络和有向网络社团结构分析方法的可统一性基础上,提出了一种基于网络结点间消息传递的社团结构分析的一致框架。通过随机游走将网络结点表示成向量空间中的点,并以此有效地定义表达结点属于同一社团可能程度的相似性。利用affinity propagation算法的消息传递机制将网络的社团结构划分问题转换成社团领导者的推选过程。在实际网络和标准测试网络上的分析表明,这种消息传递的网络社团结构分析框架能够:(i)有效地处理分辨率问题,即有效地分析那些通过模块度优化会出现分辨率问题的网络的社团结构;(ii)在一个一致的框架中分析有向网络和无向网络的社团结构;(iii)揭示网络中可能存在的多级社团结构。