关键词： 动态网络   进化方法   局部优先   重叠社团   时序演化  

摘要： 作为一种对现实中大规模复杂系统的抽象工具，复杂网络得到了广泛的关注。现实世界中的复杂系统往往随时间缓慢变化，动态网络作为刻画复杂网络动态性的有效手段，具有很高的研究价值。目前对复杂网络进行分析的方法主要集中在社团检测上。对动态网络进行社团检测，有助于人们认识网络特性以及发展趋势，具有重要的理论和实际意义。 传统的动态网络社团检测算法通常在每个时刻对网络快照进行划分，试图找到“模块性”较高的社团结构，然后分析社团之间的关系。这种方法忽视了动态网络的时序性，难以发现社团结构的演化性。同时，传统的社团检测算法通常以一种“自顶向下”的视角对网络进行划分，这种方法通常难以发现小于一定规模的小社团。然而，现实中这些小社团可能具有一些实际的功能和意义。另一方面，现有的动态社团检测算法通常不能检测到社团的重叠结构，而重叠性作为社团结构的重要特征，很有研究的必要。综上所述，本文提出了一种基于进化和局部优先的动态社团检测算法，对每个节点抽取其EgoMinusEgo子图，在其上使用标签传播算法进行局部社团划分，之后以一种“自底向上”的视角不断合并局部社团直至得到网络的一组划分。在执行合并策略时，引入了覆盖率和分布率两个指标分别代表当前社团拓扑结构与历史信息两个方面，使用进化聚类框架来平衡这两个指标，从而使得到的社团具有时序演化性。 本文在真实网络数据上对提出的动态网络社团检测方法进行了实验。实验结果表明本文提出的基于进化和局部优先的社团检测算法能够有效地检测到社团的重叠结构，同时能够检测到具有实际意义的小规模社团结构。而与其他局部优先的算法相比时，本文的算法得到的社团结构更好，同时在相邻时刻间具有更紧密的联系。

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

摘要： 模块度优化的启发式快速算法常常用来检测复杂网络中的社团结构。较之其余的社团检测方法,该算法在计算时间上更具优势,而且用模块度衡量发现检测社团的质量很高。运用模块度优化启发式算法划分空手道俱乐部网络、大学足球俱乐部网络和区域贸易网络等,并对其结构和功能做出一定的分析。特别地,针对贸易网络中自由贸易区往往表现为一个社团的特点,以221个国家或地区为研究对象,对贸易协定与地域之间的关系做了大量的实证研究。首先,从世贸组织网站上采集了区域贸易协定中国家之间贸易的数据;其次,通过模块度启发式算法进行社团划分,共得出7个主要的贸易区,其中欧盟自由贸易区的社团表现极为明显;最后,从社团结构的表现形式推断实际区域间的贸易情况。

关键词： 社团结构   模块密度   对分划分方法  

摘要： 在许多领域,例如社会科学,技术科学及生物科学,复杂网络中的社团发现是一项重要任务。这些社团结构暗含着系统功能方面的信息并用来帮助人们理解网络的功能及增长机制。谱分优化了由李等人最近提出的一种用来评估和发现社团的模块密度函数。提出了一种对分算法,该算法使用模块密度矩阵的主特征向量迭代来检测网络社团结构。在一个经典的计算机产生的随机网络中检验了算法。当社团结构变地模糊时,实验结果显示这种新的算法在发现复杂网络社团上是有效的。

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

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

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

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

关键词： 社团结构   模块密度   核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。