关键词： 社团结构   模块密度   核k-means   谱分方法   特征向量的核方法  

摘要： 为在权重的复杂网络中检测社团结构,推广模块密度函数到权重形式,并优化权重形式的权重密度函数到谱分聚类形式及权重的核聚类形式.证明了基于权重密度的两类聚类方法在数学上的等价性,利用这种等价性,提出了一种新的基于特征向量核聚类检测复杂网络社团方法.实验结果表明,这种方法比直接的谱分方法或直接的核方法检测社团更加准确.

关键词： 社团结构   模糊关系   熵   聚类  

摘要： 提出一种基于最小熵的社团结构检测算法。首先用模糊关系表示交互网络,一种基于熵的测度来确定模糊关系的隶属度,且熵越小,节点越相似。然后提出一种新的模糊关系合成规则,通过应用该规则,模糊关系被转换为最小关系。最后,通过熵的值把这个最小模糊关系划分成一个个社团。在人工网络与真实网络中的测试结果表明,该算法可以有效地识别社团结构。

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

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

关键词： 社团结构   模体结构   复杂网络测度量   社团划分算法  

摘要： 随着复杂网络理论研究的不断深入,复杂网络中社团结构的特性广泛应用于生物学、物理学、计算机图形学和社会学中,探索网络中的社团结构具有很重要的现实意义。随着对网络拓扑性质的深入研究,人们发现模体结构在网络中的存在性,模体是网络的基本结构之一,其大小介于单个节点和社团之间,在研究社团性质时需要考虑模体结构的存在性。 本文研究复杂网络中基于模体的测度量及社团结构划分,主要包括以下内容。 (1)用Rand-ESU算法对规模大小不同的9个网络进行模体检测分析,验证了模体在网络中的存在性。对Dolphin网络、Social网络和Science网络进行详细的模体分析,包括模体的种类、结构特征等。提出基于模体的顶点度和边度的定义,研究基于模体的顶点度和边度与传统定义的相关性,通过相关性研究验证新提出的定义的合理性。 (2)给出基于模体的社团的定义、基于模体的模块度的定义,提出基于模体模块度的改进GN算法,用Dolphin网络进行仿真分析,通过与真实网络中划分出的社团的对比研究验证改进GN算法的优越性。 (3)提出基于模体的边聚类系数的定义,在此基础上提出基于模体边聚类系数的社团发现算法,用股票网络进行实证分析,研究股票网络的模体结构,用基于模体边聚类系数的社团发现算法对股票网络进行社团划分,对股票网络进行蓄意攻击和随机攻击,通过对比网络受攻击前后社团划分的差异性验证该算法的稳定性。 本文提出了基于模体的复杂网络测度量和社团结构检测算法,实验结果表明研究网络测度理论和社团结构理论时考虑模体结构是有意义的。

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

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

关键词： 社团结构   模块密度   二谱分聚类方法  

摘要： 近年来,复杂网络中的社团发现越来越受到研究人员的关注并且许多方法被提了出来。为有效地检测复杂网络中的社团结构,优化了评估与发现社团的模块密度函数(即D值)。通过模块密度的优化进程,证明了模块密度函数能写成模块密度矩阵迹的最大化表达形式。利用模块密度矩阵的谱分分解,提出了一种新的二谱分的聚类检测复杂网络社团方法。在LFR标准人工模型网络中验证了二谱分方法的有效性。实验结果显示这种新的方法在发现复杂网络社团上有较高的准确性。

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

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

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

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

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

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

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

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