关键词： 社团结构   标签传播   随机游走   模块度   信息熵  

摘要： 网络科学为解决现实生活中各种各样的复杂问题带来了新的视角。真实网络系统通常具有一些非平凡的拓扑特性,如重尾度分布、高聚集系数、同配异配性、社团结构和层级组织等。其中,社团结构是复杂网络最突出的特性之一,即网络中存在一些内部连接紧密的群组,而群组与群组之间的连接较为稀疏。社团结构的检测在物理学、生物学、社会学和计算机科学等领域具有重要的理论意义和广阔的应用前景,近年来吸引了很多不同领域研究者的关注。本文介绍了社团检测的基本概念和方法,探讨了聚类意义以及如何测试和比较各种方法,讨论了社团检测在真实网络中的应用,并深入研究了三种基于传播动力学的社团检测方法。具有创新性的研究成果有以下三个方面:1.基于网络随机游走动力学特征和信息熵最小化,提出了一种新的社团检测方法-LPAf。它基于以下思想:如果按照网络的社团结构对其节点进行二级编码,则网络上随机游走的平均描述长度(加权信息熵)将会显著减小。平均描述长度是网络划分的函数,对于同一个网络,较好的划分对应较短的平均描述长度。通过改进原始标签算法的多数投票规则,使平均描述长度在标签扩散过程中逐渐减小,可以精确且有效地检测社团结构。在合成网络和真实网络上的测试结果表明,LPAf具有较强的鲁棒性、较高的精确度,以及较低的时间复杂度。2.基于社团内节点互相相似且连接紧密的特征,提出了一种高效的多分辨率社团检测方法-MLPA。在MLPA中,相似的节点首先聚集到一起形成许多元社团。然后,这些元社团通过比较其内部凝聚力与外部吸引力,决定是否与其它元社团进行合并,这个过程一直进行直到所有元社团都满足定义。MLPA既不需要知道社团结构的任何先验信息,也不需要优化任何目标函数。在合成网络和真实网络上的测试结果表明,与其它几种流行的算法相比,MLPA具有较高的准确度和极低的时间复杂度。通过调节分辨率参数,可以观察不同尺度的社团,进而揭示网络的层级结构。为了进一步验证MLPA的有效性,利用它对大肠杆菌的转录调控网络进行了详细的分析,结果表明检测到的模块具有很强的结构和功能的一致性。3.基于局域标签传播过程,提出了一种高效的动态社团检测方法-ALPA。许多真实网络是随时间演化的,而传统方法将它们视为静态的,即通过聚合一段时间内的数据而构建的,这种处理方式会丢失网络及社团的演化信息。如果希望实时跟踪网络的社团,静态方法通常非常耗时,因为即使网络的结构发生极小的改变,它们也必须重新计算整个社团结构。网络演化愈快,静态方法的耗时缺陷愈发明显。与传统方法不同,ALPA通过一个局域的标签传播过程来更新当前的社团结构。局域的标签传播过程有效利用了社团结构的历史信息,因此通常只会影响网络中很小一部分节点,这使得ALPA能够快速地响应网络结构的变化。在合成网络和真实网络上的测试结果表明,ALPA能够成功地识别并且追踪动态网络中的社团。此外,和其它常用方法相比,ALPA拥有更高的准确度和更低的时间复杂度。

关键词： 复杂网络   社团检测   多目标进化   复杂网络归减   混合编码  

摘要： 现实世界中存在大量的复杂系统,这些复杂系统通常被抽象的描述为复杂网络,如生物网、神经网络、因特网、万维网和社会网络等,复杂网络通常具有社团结构特性。研究复杂网络的社团结构有助于更好了解网络系统,并能挖掘出网络系统的潜藏功能,因此检测复杂网络的社团结构是个值得研究的课题,具有非常重要的理论意义和现实价值。最近几十年来,研究者们提出了大量的复杂网络的社团检测算法,进化算法由于具有良好并行性、全局搜索以及对任何函数类可用等特性,因此基于进化算法的社团检测方法成为解决复杂网络社团检测问题的重要方法之一,然而这些算法在非重叠社团检测和重叠社团检测领域值得进一步研究。因此本文提出了基于复杂网络归减的社团检测多目标进化算法和基于混合编码的重叠社团检测多目标进化算法。本文的主要研究工作如下:(1)本文提出了基于复杂网络归减的社团检测多目标进化算法(RMOEA)。当前的社团检测多目标进化算法在小型网络上有着很好的社团检测能力,然而这些算法在大型网络上无法表现出很好的社团检测能力。主要原因在于这些算法没有考虑到网络规模越大,多目标进化算法的搜索空间也会越大。因此本文提出了基于复杂网络归减的社团检测多目标进化算法,算法的主要思想是通过逐步归减复杂网络的规模,逐步减小进化算法的搜索空间,从而提高多目标进化算法的搜索能力。复杂网络归减的策略贯穿整个RMOEA:在进化前利用复杂网络中连接紧密的节点容易被划分到一个社团的特性,对复杂网络进行规模减小,称为预归减;在进化过程中利用种群个体之间存在相同局部社团的特性,对复杂网络进行规模减小,称为进化归减。最后利用了容错处理来纠正减小复杂网络规模过程中的错误点。在人工生成的基准网络数据集和真实网络数据集上与当前的社团检测进化算法进行比较,实验结果表明RMOEA算法可以很好的检测出大规模复杂网络的社团结构。(2)本文提出了基于混合编码的重叠社团检测多目标进化算法(MRMOEA)。当前的社团检测多目标进化算法在非重叠社团上有着很多的研究成果,然而在重叠社团上的研究成果屈指可数,主要原因在于能解码成重叠社团结构的编码很少。因此本文提出了基于混合编码的重叠社团检测多目标进化算法,算法的主要思想是,通过混合编码解决重叠社团检测问题。其中提出混合编码的基因由候选重叠点和非重叠点混合组成,候选重叠点采用离散编码(0或-1),非重叠点采用向量编码。基于混合编码,提出了挖掘候选重叠点的方法以及提出了粒子群的学习方式来产生子代。在真实网络数据集上与当前的重叠社团检测算法进行比较,实验结果表明,MRMOEA算法可以很好的检测复杂网络的重叠社团结构。

关键词： 社团检测   有向网络   相似度   CNM算法   MapReduce  

摘要： 社团结构是复杂网络研究的热点,近些年来提出了许多社团检测算法,但目前提出的大多数算法主要适用于无向网络的社团结构挖掘,对于有向网络这些算法往往难以取得较好的社团检测效果。另外,大规模数据量的产生使得传统的社团检测算法不能满足计算效率以及数据存储等方面的需求。因此,寻找大规模有向网络的社团检测算法对于社团的研究具有重要的意义。本文主要工作如下:(1)对复杂网络的理论基础、社团的概念以及Hadoop技术进行了详细的介绍,分析了一些具有代表性的社团检测算法并指出其各自的优缺点;深入研究了社团检测的研究现状和所面临的问题。(2)研究基于相似度的有向网络社团检测算法,该算法利用网络的方向信息指导节点相似度的计算,从而把有向网络的拓扑结构信息转化为代数值,然后利用相似度改进CNM算法,结合CNM算法本身的优点提高了算法的准确性和适用性。(3)针对传统社团检测算法在单机环境下不能有效处理大规模网络的局限性,使用MapReduce分布式编程模型对本文的算法进行并行化,使得大规模网络数据的社团检测得以实现。基于相似度的有向网络社团检测算法利用相似度改进CNM算法,使得算法与网络的拓扑结构相关,并且利用方向信息指导相似度的计算,使得有向网络社团检测得以实现。在单机和分布式环境下分别进行实验,结果表明本文的算法具有较高的准确性,对大规模网络数据的处理具有高效性。

关键词： 复杂网络   社团结构   亲密度   二分网络  

摘要： 社团结构指的是复杂网络内部聚合的情况。复杂网络的聚类情况对研究复杂网络的网络行为、拓扑结构和信息传播与挖掘都有十分重要的意义。所以,近几年,越来越多的学者投身到复杂网络的社团结构检测中,同时,大量的算法也被提出。而不同的网络,由于其网络特性的差异,其社团结构的检测方法也存在不同,且存在一定的问题。如在重叠社团检测上重叠界限要求过于严格,而对于有向加权网络和二分网络的社团检测,研究过程中则可能存在信息丢失等问题,需进一步的探究。为此,本文针对不同的网络提出了三种不同的基于相似度的社团结构检测算法,主要工作和创新点如下:(1)提出了一个基于关键节点的重叠社团划分算法。算法通过对复杂网络的节点进行预处理,筛选出其中的关键节点,并形成以关键节点为中心的核心区域,随后吸收与该核心区域关系紧密的节点以形成初始社团,再根据吸收度扩大社团。算法利用了一种初始网络筛选方法和最新的吸收度函数对重叠社团进行检测。实验结果表明了该算法能有效地检测出网络的社团结构,且算法时间复杂度相对较低。(2)提出了一种基于非对称亲密度的有向加权网络的社团检测算法。通过对有向加权网络节点间的关系特点的研究,给出了一种既能体现节点对间直接关系又能体现其间接关系的亲密度参数,并将其设计和引申至社团间的亲密关系。利用节点间的关系对网络进行聚类分析,最终根据最优模块度选择出最终的划分结果。通过对比试验发现了该算法的优越性和亲密度参数设计的合理性。(3)提出了一种二分网络社团结构检测算法。通过分析二分网络中节点间的互连特点,设计出分别体现二分网络中同种类型节点间与异种类型节点间的亲密度关系。利用该亲密度关系分析和聚类节点,形成多个子社团,再通过社团间的关系参数,进一步合并子社团,以形成最终的社团结构。实验结果很好的反映了算法和参数设计的优越性,并能有效地检测出网络的二分社团结构。本文设计和实现了针对不同网络所提出的三种不同的基于网络中节点间的亲密关系的社团检测算法,研究不断地深入、递进。其中基于关键节点的重叠社团划分方法和非对称亲密度的算法针对的是单分网络,而第三种算法则应用于二分网络。针对不同的网络,本文使用不同的评价参数进行分析,最终实验结果也表明算法设计的有效性和优越性。

关键词： 复杂网络   社团结构   疾病传播   周期切换  

摘要： 网络科学的兴起开辟了复杂系统建模、分析的全新领域。网络中传播动力学研究对揭示传播机制、提供预防策略具有重要的指导作用。网络模型的动力学分析不仅仅是简单的数学模型的照搬,其离不开拓扑结构的分析、检测;反过来特殊网络结构也能简化动力学分析过程。社团是网络中特殊结构之一,可以影响传播速率、路径等传播特性。另外,网络传播也受到个体自适应行为以及网络的周期切换的影响。本文对上述问题进行初步研究,主要研究工作如下:第一章,引言介绍了网络复杂性、主要研究方向以及基本概念。还介绍了网络中社团结构的定义以及检测算法类型以及评价标准,网络个体建模的SIS模型相关内容和双层网络的特殊结构及其周期切换模型;第二章,研究了基于节点相似性指标的自适应切换算法。将社团检测分为两个部分,算法分别依靠单一和双重相似性指标对网络中强弱社团进行划分。最后,根据典型真实网络和GN、LFR基准网络对算法准确率进行分析,并检验了算法主要参数的鲁棒性;第三章,基于N-intertwined模型构建出连续时间的SIS模型,分析出模型传播阈值条件和线性系统零解的稳定性,从而得到原系统零解全局稳定性。通过数值模拟,研究了社团对网络疾病传播的影响,以及个体局部自适应性对最终染病人数的影响;第四章,研究了双层网络上的切换模型,并在理论上得到两个结论:一是独立系统均稳定时切换系统零解局部稳定性不会随周期长度和驻留时间改变;二是得到稳定、不稳定独立系统均存在时切换系统局部稳定的充分条件。通过数值模拟验证了驻留时间、传染率恢复率和谱半径对最终染病人数的综合影响,并为疾病传播初期提供有效预防策略。

关键词： 社团检测   复杂网络   模块度   隐藏社团   层次结构  

摘要： 随着对复杂网络性质的物理含义和数学特征的持续深入研究,研究人员发现很多实际网络都具有内紧外松的社团结构。揭露复杂网络中的社团结构,对于理解网络结构和分析网络性质都是非常重要的。社团结构分析在社会学、计算机图形学、生物学、物理学中都有非常广泛的应用,而社团检测算法是找到这些社团结构的重要手段,对社团检测算法的研究是非常有意义和必要的。基于模块度的极值优化算法虽然时间复杂度较低,速度较快,但是无法保证一定能得到全局最优解。另外,这类算法无法找到复杂网络中较小且仍然十分重要的社团结构。本文旨在解决基于模块度优化算法由于分辨率极限问题检测出的社团结构过大、无法在大型网络中找到小的社团结构这个弱点,利用在真实网络中挖掘隐藏社团结构的算法框架Hicode(Hidden Community Detection),提出了挖掘多层递归叶子结构的社团检测算法。以模块度最大化的Mod为基算法,通过在原网络中提取每个显式社团和隐式社团对应的子网络,并利用Mod算法进一步提取该子网络中的社团结构,从而得到多层子社团结构。通过对比实验,所提出的递归社团结构挖掘算法很好地解决了基于模块度优化算法的缺陷,有效地找到隐藏在强社团之下的弱社团结构,也在很多数据集上超越了现有的经典社团检测算法。

关键词： 社团检测   谱聚类   演化聚类   动态协同训练  

摘要： 社团结构作为复杂网络的普遍特征对分析复杂系统具有重要意义。由于真实网络是动态变化的,动态社团检测方法近年来获得广泛关注。本文提出一种多相似性协同训练谱聚类方法用于动态网络社团检测,该方法首先协同训练多种相似矩阵构造新的相似矩阵,然后通过演化聚类思想融合历史信息。最后,将提出的动态社团检测方法应用到人工生成数据集和真实网络中验证方法的有效性和准确性。本文的主要研究工作如下:(1)提出一种多相似性谱聚类方法用于静态网络社区结构检测。目前存在多种度量节点间相似性的方法,不同的度量方法可能会导致聚类结果有较大差异。本文借助协同训练思想融合已有的多种相似性度量方法,构造出新的相似性矩阵。(2)在实际复杂网络中,网络节点及节点间关系具有时变性,现存的动态社团检测算法多采用两步策略或演化聚类。本文基于演化聚类框架,提出了一种动态协同训练方法以融合动态网络中的多种相似性度量。(3)为了更好运用到真实网络中,提出了一种直观的方法自适应选择演化聚类中的平滑参数。并将提出的动态协同训练方法扩展到结点和社区个数可以随时间变化的情景中。(4)将上述方法应用到人工生成数据集和真实数据集中,对比了经典的基准模型,实验结果表明提出的方法大多情况下都可以得到较好的实验结果。

关键词： 网络聚类   重叠社团结构   局部社团   线性时间复杂度  

摘要： 近年来,由于社交网络的发展和大数据时代的兴起,大规模复杂网络社团检测已成为研究热点之一。社团检测作为复杂网络研究中一项基础而又重要的工作,旨在挖掘网络中一组节点集合,这些集合内部的节点连接紧密,而集合之间的节点连接稀疏。然而在现实世界网络中经常存在一些节点可能会同时属于多个社团的情况,即重叠社团结构。因此,对重叠社团结构的检测更加重要且具有应用价值。随着网络科学的不断发展,许多复杂网络的规模甚至包含数百万数量的节点和数十亿条边。对如此大规模的复杂网络进行重叠社团挖掘一直是该领域内的难点之一。基于此,本文对大规模复杂网络重叠社团检测问题进行了深入研究,提出了一种基于弱团渗流思想的重叠社团检测算法。此外,为了解决数百万数量级的超大规模复杂网络重叠社团检测问题,本文还提出一种基于局部邻居信息的快速重叠社团检测算法。这两种算法均是以检测大规模复杂网络重叠社团结构为目的,相比较其他重叠社团检测算法,本文所提算法计算效率更快,社团检测精度更高。本文的主要研究工作如下:(1)本文提出了一种基于弱团渗流的重叠社团检测算法。k-团渗流方法是当前最常用的重叠社团检测算法之一,其基本思想是将社团结构定义为由一系列共享很多节点的完全连通子图组成。k-团渗流方法需要检测网络中所有k-团(即,k-clique),然而k-团的检测是NP完全问题,因此基于k-团渗流方法的时间复杂度很高。为了提高重叠社团检测算法在大规模复杂网络上检测重叠社团的效率和准确性,本文利用网络中的局部拓扑信息快速挖掘网络中的弱团。本文将弱团定义为由网络中两个关键节点及其公共邻居组合而成,由于仅仅利用节点的邻居信息,因此检测弱团要比检测k-团高效很多。同时在渗流过程中,提出新的相似度指标来衡量两个弱团之间的相似性,并以此来判断两个弱团是否应该合并,以提升算法的准确性。在新的相似度指标中不仅考虑了两个弱团之间共享的节点数目还统计了弱团之间边的连接数目。在LFR基准数据集和真实网络数据集上的实验结果表明,与现有几种重叠社团检测算法相比,基于弱团渗流的重叠社团检测算法在计算效率和发现重叠社团质量方面都具有明显优势。(2)本文提出一种基于局部邻居信息的快速重叠社团检测算法。随着社交网络的兴起和互联网时代的发展,目前复杂网络的规模变得越来越巨大。为了能够在数百万数量级这种超大规模复杂网络中检测重叠社团结构,本文提出了一种基于局部邻居信息的快速重叠社团检测算法,称之为OCLN(Overlapping Community detection by using Local-Neighborhood information)算法。OCLN 算法的基本思想在于首先利用网络中节点的内部度数和外部度数这些局部结构快速扩充社团,随后根据社团中每个节点的局部邻居信息在该社团中的贡献度计算节点的隶属度指标。从社团中删除掉一些隶属度较低的节点,提高算法的准确性。由于整个算法全部利用网络的局部结构,因此OCLN算法的时间复杂度为线性,即O(n+m),n为网络中节点的数目,m为边的数目。通过对LFR基准网络和大规模真实网络上的实验分析表明,OCLN算法在算法运行时间和NMI精度性能上都明显优于其他几种重叠社团检测算法。

关键词： 社会网络   影响最大化   结构洞   贪心算法   社团检测  

摘要： 互联网技术的发展推动了各种社交网络(Facebook,Twitter,新浪微博等)的蓬勃发展,社会网络中丰富的信息数据的挖掘以及通过社会网络进行的营销活动都给社会网络的研究带来了前所未有的挑战和机遇。网络营销是基于个人通过社会关系对周围朋友,家人或者同事进行影响力扩散而产生的“口碑”营销模式,在影响力扩散过程中,挖掘社会网络中最有影响力的用户变得十分关键。在这个背景下,影响最大化问题的研究变得炙手可热。影响最大化问题就是从社会网络中选出少量节点作为种子节点,从种子节点开始传播,在社会网络中获得最大的影响收益。目前已经提出很多社交网络中的影响最大化算法,例如各种贪心算法,启发式算法等,目的都是降低影响最大化算法的时间开销,提高算法的结果精度。然而,现有算法中鲜有考虑社会网络中节点的结构特征,例如结构洞节点具有鲜明的结构特征,与普通节点相比传播能力更强。忽略节点的结构特征的影响最大化算法的结果精度不够理想,而且利用结构特征可以有效的降低算法的时间开销。针对上述影响最大化研究中的挑战和问题,本文从以下两个方面进行研究:(1)研究基于结构洞理论的影响最大化算法。提出SG(Structure-based Greedy)算法降低影响最大化算法的时间开销,改善影响传播范围。SG算法的基本思想是为原始社会网络建立拉普拉斯矩阵,通过求解费德勒向量确定结构洞节点。本文综合考虑节点的结构特征和影响力,采用过滤的方式筛除非结构洞节点和影响力特别小的节点,缩小种子选取的候选集空间。在缩小的候选集中贪心的选取能够获得最大传播范围的种子节点。本文通过实验验证,本文提出的基于结构洞理论的影响最大化算法和现有算法相比,在算法时间开销和算法结果质量方面都具有明显的优势。(2)研究高效的结构洞发现算法和社团划分的关系。已有的结构洞发现算法主要开销在于计算节点的结构洞值,在大规模社交网络中,结构洞值的计算开销相当可观。本文提出借助社团划分的思想降低结构洞值的计算开销。首先将原始社会网根据节点的相似度进行粗糙划分得到简单社团结构,然后根据社团结构确定结构洞节点,最后计算结构洞节点与已有社团的相似度值作为节点的结构洞值。此外,在已知社会网结构洞节点的前提下,本文提出基于“二步”信息流理论的新的社团划分方法 SCD(Structure-based Community Detection)。SCD 算法的基本思想是首先将原始的社会网根据节点相似度获得粗糙社团结构,然后在粗糙社团中确定网络中的结构洞节点,最后从结构洞节点出发,根据“二步”信息流理论检测潜在社团,根据潜在社团与粗糙社团的相似度对比发现新社团。本文通过真实实验验证了提出的基于结构洞的社团检测算法的正确性和精确性都有很大的改进。

关键词： 复杂网络   社团检测   AP聚类   并行化  

摘要： 复杂网络作为生活中电力系统、通信网络和万维网等复杂系统的高度抽象,复杂网络社团结构表示着网络中的节点聚合的趋势,是复杂网络的一个重要的拓扑属性。社团检测可以有效认识复杂网络的结构和功能,进而对网络中的行为模式进行预测和分析,对复杂系统的研究与应用具有重要的意义。现有的大多数复杂网络社团检测算法都在追求算法的准确度,而忽略了时间复杂度高的问题。本文针对目前社团检测算法在处理大规模数据时在速率上不足的问题,设计了一种在Hadoop平台下进行的社团检测的并行化方法。本文主要工作如下:1.本文对复杂网络的基础知识和现有社团检测算法进行了研究。简述了复杂网络基本理论,介绍了社团检测算法的研究现状,重点介绍了几种流行的社团检测算法的基本思想和计算过程。2.由于可以通过相似度将复杂网络的社团检测问题转化为相似节点的聚类问题,本文对AP聚类（Affinity Propagation Clustering）进行了深入的研究,针对传统AP聚类在计算相似度时用欧氏距离而没有考虑到复杂网络的集聚特性的问题,本文采用一种改进的Jaccard系数来计算复杂网络节点之间的相似度。3.针对社团检测AP聚类在处理大规模数据速度慢的问题,结合大数据分析工具Hadoop,设计一种分步并行化的AP聚类社团检测方法,将AP算法整个过程分步进行并行化来实现社团检测的AP聚类算法的并行化。在PC机上搭建Hadoop集群,在不同规模的数据集上对本文设计的计算方法进行测试。实验中分别对本文设计的方法在算法准确度和方法性能上进行的测试,结果表明,本文方法在进行社团检测时具有良好的准确度和计算性能,尤其是在大规模数据集中,本文方法能够取得较好的加速比。