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

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

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

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

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

摘要： 蚁群算法是一种求解复杂问题的元启发式算法,它是意大利学者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方法,而且对于复杂网络社团划分问题,如果选择好的网络节点相似度构造方法,已有的基于相似度矩阵的聚类分析算法都能快速有效地对网络社团进行划分。

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

摘要： 为有效地检测复杂网络中的社团结构,优化模块密度函数,展示模块密度函数怎样被优化框定到谱分聚类问题,提出一种谱分算法,进一步对该算法进行时间复杂度分析。在一个经典的真实世界网络中检验该算法,并与基于模块密度的直接核方法及基于模块函数的谱分方法做比较。特别地,当网络中社团结构变得模糊时,实验结果显示,该谱分算法在发现复杂网络社团上是有效的。

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

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

关键词： 社团检测   谱分析法   近邻传播   局部社团发现   可视化实验平台  

摘要： 摘要 随着复杂网络理论研究的不断深入及在各领域的应用,其所具有的社团结构特征吸引了广泛的关注。寻找和分析复杂网络的社团结构对于反映和理解整个网络的构成和功能有重要的意义。本论文主要研究社团结构检测问题,提出了基于谱分析法和近邻传播的算法、基于局部发现的算法两种检测方法,并建立了可视化实验平台。 论文对传统的Normal矩阵谱分析法及近邻传播算法进行了研究。传统的Normal矩阵谱分析法在网络社团结构不明显的情况下难以得到理想的结果,针对这个问题,论文提出了一种基于谱分析法和近邻传播的社团检测算法。该算法采用近邻传播算法对多个Normal矩阵特征向量的元素进行聚类分析,根据聚类结果来获得整个网络的社团检测结果。这种基于谱分析法和近邻传播的算法在无需预先知道社团数目的前提下对于社团结构不明显的网络也具有较好的检测效果。 论文针对目前部分算法时间复杂度较高、无法对大规模网络进行检测的问题提出了一种基于局部发现的社团结构检测算法。论文设计了一个用于快速寻找指定节点社团成员的局部社团检测算法,通过对该算法进行扩展,不断将检测出的局部社团成员从网络中移除来进行网络整个社团结构的检测。这种基于局部发现的社团检测算法在不需要预先知道社团数目的基础上具有较好的时间复杂度,并且检测效果也比较理想。 论文设计和实现了一个可视化实验平台,该平台能够对社团检测结果进行可视化显示,并计算相应数据。使用该平台将论文提出的两种算法与GN算法、CNM算法进行对比,实验数据表明,基于谱分析法和近邻传播的算法在无需预先知道社团数目的基础上无论网络的社团结构是否明显都具有较好的检测效果,基于局部发现的算法具有很好的计算效率、无需知道社团数目并且检测效果也令人满意。

关键词： 复杂网络   社团结构   模块密度   社团检测  

摘要： 近年来，复杂网络逐渐成为描述与分析现实复杂系统的重要工具而备受关注。复杂网络的大规模性、强耦合性、局部性等特点促使研究人员通过局部特性来刻画与研究整体特性。其中，社团结构作为一种局部研究方法在计算机科学、生物信息学和社会学等多个领域都有重要的意义。 在社团检测算法中如何有效量化社团划分结果及如何设计出高效、准确的算法是两大关键问题所在。为了解决社团量化的问题，Newman等在对比真实网络与随机网络的基础上提出了模块度函数。尽管最大化模块度函数属于NP-难问题，但绝大多数算法都是基于优化模块度函数。针对于模块度函数存在的分辨极限问题，李等通过对比社团内部边和外部边密度提出了模块密度函数，并证明了该测量标准可以在很大程度上克服分辨极限问题。但是模块密度只能应用于无权图。在真实网络中，给每一个节点赋予相同的权重并不合理。为了克服该缺陷，本文提出了一种泛化的模块密度。并设计出基于优化加权模块密度的模拟退火算法。实验结果表明该测度更加有效的刻画网络社团结构。 为了进一步拓展泛化的模块密度的应用，本文提出了一个基于泛化模块密度函数的可以对蛋白质相互作用网络的功能模块进行检测的算法，并开发出相应的可视化软件。实验结果表明该算法不仅可以快速检测出蛋白质相互作用网络中的功能模块，同时可检测出具有重叠结构的蛋白质功能模块。