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

摘要： 社团结构是复杂网络的一项基本特性,对复杂网络中社团结构特别是重叠社团结构的检测,是复杂网络理论研究的一项重要且充满挑战的课题。对当前常用的重叠社团检测算法进行了分析和归纳,阐述每类算法特点,并介绍用于评价算法性能的一些基准图,对复杂网络重叠社团检测领域未来的研究方向提出了一些思考和建议。

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

摘要： 近年来,由于社交网络的发展和大数据时代的兴起,大规模复杂网络社团检测已成为研究热点之一。社团检测作为复杂网络研究中一项基础而又重要的工作,旨在挖掘网络中一组节点集合,这些集合内部的节点连接紧密,而集合之间的节点连接稀疏。然而在现实世界网络中经常存在一些节点可能会同时属于多个社团的情况,即重叠社团结构。因此,对重叠社团结构的检测更加重要且具有应用价值。随着网络科学的不断发展,许多复杂网络的规模甚至包含数百万数量的节点和数十亿条边。对如此大规模的复杂网络进行重叠社团挖掘一直是该领域内的难点之一。基于此,本文对大规模复杂网络重叠社团检测问题进行了深入研究,提出了一种基于弱团渗流思想的重叠社团检测算法。此外,为了解决数百万数量级的超大规模复杂网络重叠社团检测问题,本文还提出一种基于局部邻居信息的快速重叠社团检测算法。这两种算法均是以检测大规模复杂网络重叠社团结构为目的,相比较其他重叠社团检测算法,本文所提算法计算效率更快,社团检测精度更高。本文的主要研究工作如下:(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精度性能上都明显优于其他几种重叠社团检测算法。

关键词： 复杂网络   社团检测   节点重要性   模块度   标签传播  

摘要： 社团结构是网络中相同属性节点的集合,揭示了复杂网络中的隐藏属性和交互规律。识别和分析网络中的社团结构有助于更深入的了解复杂网络的内在规律,探究网络中个体的未来演化动态,预测复杂网络的发展规律,因此,开展对社团结构检测的研究具有重要的理论与实际意义。模块度优化算法和标签传播算法是现有的两种较为典型的社团检测算法。二者在初始化时都是将各个节点视为一个独立的社团,这影响了模块度优化算法第一阶段的性能;另外,由于标签传播算法在计算时选择目标标签的随机性,导致社团检测结果不准确,算法的鲁棒性较差。针对以上两个算法存在的问题,本文结合复杂网络的节点重要性提出了相应的改进算法:(1)基于节点重要性的改进模块度优化社团检测算法:首先,对网络进行预处理,合并度值为1的节点;然后,对网络中节点进行重要性排序,以序列中若干重要节点作为中心进行扩展,形成网络的初始社团结构;最后以初始社团结构作为节点形成新图,以模块度为衡量标准将新图的节点进行相互合并得到最终社团结构。基于4个真实网络以及1个人工合成网络,选取了MDD算法等7种常用节点重要性排序算法对网络节点进行重要性排序,与基本模块度优化算法及其它典型算法相比,结果表明改进模块度优化算法能够更为有效地检测出网络中的社团结构,对于真实网络检测的模块度值和NMI值都优于其它算法。(2)基于模块度和节点重要性的改进标签传播算法:算法初始时不为节点分配标签,而是将网络进行准确和快速的初始划分,对划分在一起的节点分配相同的标签,减少了标签数量;根据节点重要性排序的结果更新标签,避免了不重要节点对标签更新的影响;选择标签时如果有多个待选标签,以待选标签对应节点的重要性为依据进行选择,避免了原算法的随机性。基于4个真实网络和1个人工合成网络的实验结果表明,与原算法及其它检测算法相比,改进算法能够有效改善原算法不稳定和正确率低的问题,能够获得稳定的社团检测结果,且检测结果的模块度值和NMI值都优于其它算法。

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

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

关键词： 社团检测   密度   中心点扩张   复杂网络  

摘要： 现实生活中的很多复杂系统都已被抽象成为复杂网络来进行研究。随着各种复杂系统的数据量持续攀升,未来将会有更多的复杂系统加入到复杂网络的行列。复杂网络最为典型的特征就是社团结构,社团对应的是复杂网络中的单元结构。社团检测的目的就是准确地发掘复杂网络中的社团单元结构。成功的社团检测能够指导我们揭示出复杂网络内部深层次的规律,对复杂网络进行社团检测研究具有重要的现实意义。许多社团检测算法已经被提出,这些算法基本可以归类为基于模块度优化的社团检测算法、基于标签传播的社团检测算法、基于层次聚类的社团检测算法、基于中心点扩张的社团检测算法和基于密度的社团检测算法。为了更精确地检测出社团结构,本文深入研究了上述算法,并着重对中心点扩张算法进行了改进。本文主要改善了由于选取的中心点太少而导致社团检测效果不佳,选点经常不能覆盖所有社团,同时时间复杂度较高,未对重叠节点处理以及没有从全局的角度考虑中心点的选取等问题。本文首先提出了基于全局密度影响的中心点扩张社团检测算法(DenISeC)。DenISeC从网络的全局角度出发,计算每个节点从网络中移除后的网络所有节点的密度之和变化,将其作为节点对网络的密度影响值,将密度影响值超过一定阈值的节点视为中心点,将中心点组成的初始社团当作核心社团。依据节点与核心社团的相似性将网络中的其他节点按照层次划分到各个社团中。然而,DenISeC的准确率依旧有待提高,针对这一问题,本文提出了基于密度层次的中心点扩张社团检测算法(DenSeC)。DenSeC算法将度数最小的节点当作每个社团的边缘点,从边缘点出发递归地找出边缘点邻域内密度最大且高于当前节点密度的点,递归停止时到达的节点就是核心点。核心点组成的初始社团被当作网络的核心社团。网络中其他的节点将根据节点与核心社团的相似性划分到各个初始社团中。本文提出的算法在多个数据集上与参照算法对比了社团检测效果,实验结果表明DenSeC算法提高了中心点扩张算法在各个网络上的准确率,DenISeC算法更加合理地选中了复杂网络中的中心点,并且在时间复杂度上有所改善。

关键词： 复杂网络   技术交易网络   社团结构 社团检测  

摘要： 国内外学者已经成功的将复杂性科学的一些思想应用于刻画和解释技术交易网络,但是这些尝试主要停留在宏观层面,针对技术交易网络中观及微观层面的定性定量研究还少见报道。相比而言,通过对网络中社团结构的深入细致分析,可以更全面深刻的掌握系统结构本身存在的规律,有利于构建良好的技术交易模式,促进技术交易活动的顺利进行。本文将复杂网络社团结构检测算法应用到技术交易行为的研究过程当中,以实际交易数据拟合网络生成模型,通过技术交易网络对社团检测算法进行实证与分析。主要展开以下方面的具体工作:(1)技术交易网络模型的构建。在构建出复杂技术交易网络之后,提取网络静态特性及动态特性,对网络结构进行初步理解。(2)分析多种社团检测方法并进行实证。分别对层次聚类算法、模块度优化算法、谱聚类算法以及流传播算法四类社团检测算法进行分析。通过对比模块度、时间复杂度等社团划分评价标准发现:模块度优化类算法对于技术交易网络的切合程度较高。(3)深入分析技术交易网络中重要节点及典型社团,发掘网络内部结构规律。首先,对多种中心性进行加权获得新的中心性评估标准;其次,通过重要节点所在社团的演化研究发现:社团内部主要通过重要节点吸引外部节点融入到社团当中。通过对网络内部社团聚类后的结果发现,节点度大的社团向外分枝较多,节点度小的社团内联系较为紧密。本文通过研究与实证相结合,以北京市技术交易网络为基础进行社团划分,发现使用模块度优化类算法在时间复杂度及划分结果等方面均具有较好表现,且通过算法发现的社团内部结构规律能够在一定程度上为对技术交易市场的管理提供指导与支持。

关键词： 异构信息网络   社团检测   同构信息网络   低维表征   推荐系统  

摘要： 异构信息网络是一种拥有多种类型的结点与链接的复杂网络,这些结点与链接蕴藏着丰富的语义信息,给当前数据挖掘领域带来了更多的研究机会与挑战。近年来,研究者们针对异构信息网络,分别在相似性度量、图聚类、链路预测以及推荐等方向做出了许多成果。本文以异构信息网络为研究对象,主要在社团检测和推荐系统两个方面进行研究。传统的异构信息网络中社团检测的方法主要有基于排序、基于路径与多视角学习三种类型,前两者多根据概率图模型来求解模型,后者则主要利用多视角学习方法来解决异构网络中的问题。而基于异构网络的推荐系统则可以看做是基于多源信息融合后的推荐,主要以融合策略和融合信息来提高推荐性能。与之不同的是,本文以全新的角度(将异构信息网络挖掘转化为同构信息网络挖掘)出发,借助信息在元路径上的有效传播,提出一种分解技术,能够在无信息损失的前提下将原始异构信息网络分解为一系列同构信息网络。同时基于该分解策略,本文分别提出了一种异构信息网络的社团检测算法HomClus与一种融合用户与项目信息的推荐方法CSR。这三者构成了本文的核心内容,本文的主要贡献如下:第一、提出了异构信息网络的基于元路径的分解策略。该策略主要利用元路径反映实体间的不同关系的本质,针对目标类型实体,通过简单的矩阵操作得到不同路径下目标类型实体的关系权重矩阵——也就是同构信息网络。且该过程对目标类型而言没有信息损失。因此,对异构网络的相关研究问题都可以简化为在目标类型的同构网络上的研究问题,从而更容易被解决。第二、提出了基于异构信息网络的分解策略的社团检测算法HomClus。该方法在第一个贡献成果的条件下,首先将异构信息网络转化为一系列同构信息网络,并整合为统一的网络结构。其次,使用非负矩阵分解快捷地将节点转化为向量,即将整个网络投影到低维子空间中。最后,采用高效的聚类方法如基于同步的聚类方法对低维子空间中的“节点”进行聚类,从而检测出原始网络中潜在的社团结构。实验表明,HomClus算法与领域内的前沿算法相比有很大的优势,如算法直观简洁,参数不敏感,同时也验证了异构信息网络分解策略的有效性与实用性。第三、提出了基于异构信息网络的分解策略的推荐算法CSR。该方法针对推荐系统中典型的实体对象——用户与项目,利用异构信息网络的分解策略,将用户的异构信息、项目的异构信息同时转化为同构信息。并受当前较为流行的基于渐近因子模型的推荐方法与相似性正则化的启发,将用户信息、项目信息以及评分信息三者以集体相似性正则化一致逼近的形式有效地融合在一起,最后产生高质量的推荐结果。

关键词： 互联网数据中心   社团检测   网络流行为分析   复杂网络  

摘要： IDC以其标准化的机房设备、优质的网络带宽、全面的监控管理等集中的一站式服务,大大减低了中小企业信息化建设的成本,为传统企业参与“互联网+”进行服务转型提供了便捷。这些企业的广泛需求,也推动了IDC的迅猛发展和高速建设。然而,现在IDC的建设相对独立,没有全面规划和统一部署,造成运营商网络资源利用不平衡,降低了服务效能。因此,需要一种行之有效的办法帮助网络运营商和网络规划者识别网络中IDC,从而优化网络资源配置和部署。根据这种需求,本文提出了一种基于流行为特征的IDC识别方法。本文的总体思想是从大量用户的网络流量中,提取和选择一组能有效区分数据中心IP地址的特征参数,然后结合机器学习技术将IP地址划分为数据中心IP和非数据中心IP,再构建数据中心IP地址的网络,最后使用社团检测技术对网络进行划分,进而完成IDC的识别。本文的研究成果如下:(1)本文通过对数据中心服务器IP流量和非服务器主机IP流量的特点进行对比分析,得到六种反映服务器和非服务器间差异的流量特征属性,进而从中提取出一组包含24种流量特征的特征参数集。并完成了特征参数集中参数的分类性能测试,发现部分流量特征参数对数据中心IP分类效果较好,表明该特征参数集具备区分服务器IP和非服务器IP的能力。(2)本文通过构建数据中心IP的连接网络,引入社团检测技术,将IDC识别转化为网络中的社团发现问题。通过分析IDC的网络特性和功能特点,总结得出基于流连接的IDC网络具有社团结构,然后利用共引网络的思想,结合流的连接特征构建数据中心IP连接图,使用社团检测算法进行社团挖掘,实现了IDC识别的目标。最后,本文以数据中心特征参数集为输入,分别用两种机器学习算法—C4.5决策树算法和朴素贝叶斯算法进行分类,都取得了较好的效果。同时使用两种社团检测算法—BGLL算法和Infomap算法,验证了本方法的有效性。

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

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

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

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