关键词： 复杂网络   社团检测   自主计算   社团脆弱性   结构属性  

摘要： 社团是指复杂网络中连接紧密或者具有相似属性的节点集合,通常,社团之间连边稀疏,社团内部边连接紧密。社团是网络系统的重要结构属性,社团检测有助于挖掘网络中的关键信息及分析网络结构特征。因此,社团检测方法的研究具有重要的现实意义。同时,网络中社团的安全性也变得尤为重要,对社团的脆弱性进行评估能够及时发现网络中的脆弱环节,并有助于制定有效措施避免网络遭受大规模破坏。所以对社团的脆弱性分析的研究也是必不可少的。基于上述问题,本文提出了基于自主计算的社团检测方法和一种新的社团脆弱性分析方法,并以真实世界网络作为研究对象,通过大量的仿真实验验证了方法的有效性。本文主要工作内容及创新成果如下:(1)基于自主计算的社团检测方法研究本文提出了一种新的基于自主计算的社团检测方法(AOCCD)。该方法基于自主计算(Autonomy-oriented computing,以下简称为AOC)系统,主要包括两个阶段:检测和合并。在检测阶段,系统中的自治体各自挖掘其附属节点的局部社团,通过局部相似度指标和局部模块度增益指标来决定哪个节点可以加入局部社团。在合并阶段,所有自治体已完成其社团检测任务,将具有相同社团标签的节点进行合并,可完成对社团的初步划分。最后,使用本文提出的合并策略将一些“小社团”进行合并。实验表明,AOCCD算法对网络社团的划分更准确,得到的社团质量更高,并优于部分传统算法。(2)考虑社团内部与外部特征的社团脆弱性分析研究综合考虑社团的内部特征和外部特征,本文提出了一种新的社团脆弱性分析方法。社团内部特征有割点的平均度,连接密度和边与边之间的权重;外部特征有社团之间的连边数和连边权重。本文通过上述五个特征定义了社团脆弱性指标,将社团脆弱性量化,社团的脆弱性值越高,该社团就越脆弱。通过在真实世界网络中进行实验验证了本文提出的社团脆弱性评估方法的可行性。本文提出的方法可以对社团脆弱性进行准确评估,及时发现网络中的脆弱环节,避免网络网络遭受大规模破坏。

关键词： 社团检测   种子扩展   二阶邻居   节点影响力   节点相似性  

摘要： 社团检测是当前复杂网络分析领域的一个研究热点,其目标是找到内部联系紧密而与外部联系稀疏的节点集合,从而挖掘社团之间的拓扑结构和功能单元之间的隐藏关系。基于种子扩展的社团检测算法因其具有较高的效率和有效性而被广泛应用于解决这一问题,然而部分算法需要依赖真实网络中的大量先验信息导致其在精确性和质量方面无法取得好的效果。针对上述问题,本文结合节点影响力和节点相似性对社团进行划分,主要内容如下:(1)针对当前种子扩展算法在选择核心节点时通常只考虑节点本身的属性或随机选择节点作为种子,可能导致算法性能不稳定的问题,本文提出一种基于二阶邻居重要性的种子扩展算法。本文首先研究了节点的二阶邻居对其影响的因素,并结合自身与其一阶、二阶邻居的属性和节点信息熵计算节点影响力高效地获得网络中的核心节点集合;社团扩展分两步进行,第一步将只与一个种子节点连接的邻居节点划分,第二步利用节点归属度指标对网络中未分配的节点进行划分,进一步提升算法的准确性;最后本文使用节点归属度和模块度指标对社团进行优化,该过程能够将没有现实意义的小社团合并,从而获得更准确的社团结构。此外,该算法具有较强的适应性,可以应用于不同类型网络中的社团检测,并且无需任何网络信息的先验知识。(2)由于重叠社团相较于非重叠社团更符合真实世界的复杂网络,为了进行重叠社团的检测,本文针对上一算法进行扩展,提出了一种基于二阶邻居重要性的重叠社团检测算法,该算法继承了上一算法中选取种子的策略,选取网络中能够代表社团的高质量种子节点集合;社团扩展采用改进的适应度函数最大化的贪婪策略对社团进行初步扩展,该过程中一个节点可以同时归属多个社团,若存在不属于任何社团的节点,引入节点归属度指标将节点进行二次划分。最后引入社团距离度量指标用于发现重叠的社团并将过度重叠的社团合并,消除过度重叠和冗余,从而优化社团划分结构。对多组人工和真实网络数据集进行了实验验证和对比分析,结果表明,所提出的两种社团检测算法在性能上优于对比算法,在精确度和质量方面取得了较好的效果。

关键词： 复杂网络   社团检测   多属性决策   多目标优化  

摘要： 现实世界中的系统可以被建模为复杂网络,利用结点和边表示系统中的参与者及参与者间的交互关系。社团是复杂网络的重要特征之一,通过对社团结构进行研究,探索结构特征与功能特性之间的对应关系,可以优化复杂网络和现实系统的功能。因此,社团检测对熟悉网络结构并充分发挥系统价值具有重要意义。多重网络(Multiplex network)是一种由多个单层网络构成的网络,是多层网络的一种特例。在多重网络中,每一层对应于一种交互类型,可用于表示相同实体之间的不同交互模式,能够更加完整地反映实际系统中的信息。在多重网络中进行社团检测通常需要聚合每一层中结点的连接信息,从而更加准确地检测出社团结构。本文在以往相关研究的基础上,基于多属性决策技术TOPSIS(Technique for Order Preference by Similarity to an Ideal Solution)提出了采用遗传策略的单层网络社团检测算法TMGA,以及采用层次融合思想的多重网络社团检测算法MTMGA和TLVA算法。(1)基于遗传策略的社团检测算法TMGA。该算法使用多属性决策技术中的TOPSIS方法综合单层网络中四种相似度的优势,得到能够衡量网络中结点相似关系的相似度得分T-Score,并将T-Score作为结点间边的权重,得到新的单层加权图。TMGA在该加权图上使用矩阵编码方式和NSGA-II算法的框架,首先初始化结点的社团归属及结点间的连边,利用归属矩阵和邻接矩阵进行编码,并基于矩阵运算设计新的交叉和变异方式,迭代地产生新的社团结构。同时,TMGA在加权模块度的基础上构建外部目标和内部目标作为适应度函数来衡量社团的质量。迭代终止后,TMGA选取第一帕累托前沿的解作为单层网络的社团结构。(2)基于层次融合思想的的MTMGA和TLVA算法。MTMGA和TLVA利用多属性决策技术TOPSIS融合多重网络不同层中结点的相似度,得到相似度得分M T-Score,把多重网络聚合为单层加权图。本文在该加权图上使用基于矩阵编码的遗传策略,把TMGA拓展到多重网络中形成了MTMGA算法,采用简化后的多重模块度和共享社团冗余连接率作为适应度函数,并选取第一帕累托前沿的解作为多重网络的社团结构。同时,我们在该加权图上基于加权模块度实现了TLVA算法,首先把加权图中的每个结点看作单独的一个集合,将结点移入模块度增量最大且大于0的邻居集合中。再把每个集合压缩为一个超结点,将集合内边的总权重作为结点自环的权重,不同集合间的多条边视为一条边,邻居集合间的边的总权重作为新的边的权重。重复以上步骤,得到多重网络的社团结构。本文在多个复杂网络上分别对TMGA、MTMGA和TLVA算法进行实验,并与其它算法比较社团检测的结果。通过实验表明,TMGA、MTMGA和TLVA算法相较于其它算法具有更加优越的社团检测能力。

关键词： 复杂网络   重叠社团结构   深度重叠结构   子社团结构   节点配对方式  

摘要： 在现实生活中很多复杂系统可以抽象成复杂网络,运用复杂网络理论可以很好的帮助理解系统特点。社团结构作为复杂网络最重要的特征之一,其揭示了网络中结构和功能的关系,反映出了网络的更深层次特点。目前现实生活网络随着信息的交流网络规模也越来越大,所以如何准确的找到和利用网络社团结构成为了目前复杂系统的热点研究问题。网络中社团是由个体选择的结果,本文从真实网络社团形成原因出发,定义节点相似度让节点通过选择最相似节点形成节点对从而形成社团。节点形成节点对后改变节点对的顺序,通过蒙特卡洛的结果发现节点会优先选择节点的度更大节点形成节点对,根据这一结果提出了基于最大节点的度和相似度配对算法。算法假设社团的形成是节点选择最相似节点的结果,并且具有更大相似度和度的节点对会优先形成社团,每一个节点可以对多个社团有选择权力,从而发现了网络中社团的重叠结构,合理的说明了重叠节点的物理意义,同时本文提出的算法能很好的发现网络的重叠社团结构。由于重叠节点和它所在社团的联系度相同,为了找到更多深层次的重叠节点,增加相似度级数,利用多级最相似度继续优化社团。找出了网络中的深度重叠结构和重叠社团的子社团结构,解释了网络是由节点对到小社团再到交叠社团的一个演变过程。本文的模型揭示了网络的深度重叠结构并发现了社团的子结构,对实际网络结构有很好的解释分析效果。考虑到节点不同选择配对方式对网络的社团结构会有影响,分别限制节点只选择一个节点和两个节点重新划分社团。本文首先限制节点只选择一个最相似节点,通过蒙特卡洛模拟,得到这种配对方式可以发现网络的小社团结构,这些小社团大多数处于网络的边缘位置。同时解释了网络社团结构会因为节点的选择而产生多样性的特点,这也是真实网络的重要特征之一。然后限制节点可以选择两个相似节点形成节点对,利用蒙卡发现了对于网络只需要部分数据就可以得到网络的稳定社团结构。当节点以节点的度大小为概率选择节点时,也会让节点更靠近网络的中心。本文通过分析两种不同的配对选择方式解释了网络多样性的原因,同时得到了节点配对方式对网络社团结构的影响。

关键词： 社团检测   重叠社团结构   节点向量   密度峰值   标签传播   归属度  

摘要： 在真实世界网络中,数据量往往较大、维度较高,这使得数据难以处理,并且所包含的社团大多重叠,而大多数已经存在的算法针对的是非重叠社团,基于改进的密度峰值和标签传播的重叠社团检测算法(DPCL算法).采用低维向量表示网络中节点信息,根据节点的局部密度和相对距离选出中心节点.将只与一个中心节点直接相邻的节点分配到该中心节点所在的社团内,对剩余节点通过计算归属度进行分配,从而实现对重叠社团进行检测;在真实世界网络和LFR基准合成网络上与其他社团检测方法进行比较,实验结果表明能够有效的检测重叠社团.

关键词： 社团检测   二分网络   动态距离   自我中心  

摘要： 为了在二分网络中能够更好地利用动态距离模型,提高动态距离模型的鲁棒性,提出一种新的局部非对称边缘聚类系数(local asymmetric edge clustering coefficient,LAECC),将自我中心(Ego-Leader)从单模网络扩展到二分网络,用来判断专属邻居节点对距离产生的影响,摆脱敏感参数.同时,提出一种在二分网络中基于Ego-Leader进行社团检测的增强动态距离模型(E-BiAttractor),E-BiAttractor不仅继承了BiAttractor在检测二分网络社团时的优异表现,而且通过引入Ego-Leader来代替敏感参数,优化了模型在二分网络上的鲁棒性,并提出相应的社团检测算法.最后在8个公开数据集上进行实验对比分析,验证了所提模型的有效性.大量实验表明,相较于几种已有的算法,E-BiAttractor具有良好的性能.

关键词： 社团检测   K阶图卷积   属性信息   稀疏性  

摘要： 挖掘属性网络中的社团结构有助于对网络节点进一步分析,具有重要的现实意义。图卷积神经网络能够有效地将属性网络的结构信息进行嵌入,获取节点的特征表示,从而可获得性能良好的社团结构。然而,现有图卷积方法大多使用固定的低阶图卷积,只考虑每个节点一阶或二阶内的邻居,没有充分利用节点关系,忽略了网络结构的多样性。另外原始网络结构的稀疏性无法克服,会降低社团检测的性能。为解决上述问题,提出一种融合属性信息与结构信息的K阶图卷积社团检测方法(KGCN),该方法可以有效地克服原始网络的稀疏性并利用节点的高阶结构进行社团检测。首先根据节点的属性信息对原始网络进行重构,缓解原始网络结构的稀疏性;其次考虑到高阶结构关联,采用K阶图卷积编码器对节点进行编码,获得节点的特征表示;最后使用谱聚类算法进行社团检测。实验结果表明,在四个真实数据集上,相比现有算法,KGCN方法取得更好的社团检测结果。

关键词： 复杂网络   社团检测   标准体系  

摘要： 传统标准体系往往采用"自上而下"的思维方式,在新技术和产业融合快速发展的背景下,传统模式无法从容应对海量标准数据信息.本文基于工业机器人领域的标准引用网络,通过设计数学模型引入BGLL社团发现算法来探索标准集合重新划分,后借助Jieba分词和TF-IDF关键词提取算法,识别划分结果中的标准主题,以此来丰富工业机器人标准体系结构图,为工业机器人领域的标准化工作提供有益参考,为标准数字化转型提供技术支持.

关键词： 社团检测   k核   加权图   紧密子图   贪婪策略  

摘要： k核查询是一种社团查询,由于其可以在线性时间内被有效计算,因此在社团检测中具有较广泛的应用。图中边的权值在很多场景下具有较强的语义关系,但现有研究较少考虑图中边的权值。为提升k核查询的效率,在k核的基础上定义加权图中的紧密k核子图查询(CRKSQ)问题,并使用归约方法证明该问题是NP-难的。基于贪婪策略设计启发式算法CRK-G,通过迭代删除节点为CRKSQ问题找到一个近似解。在此基础上,从降低图规模和减少迭代次数两方面研究CRK-G算法的优化策略,分别提出使用图压缩策略的算法CRK-C及使用单次多节点删除策略的算法CRK-F。在Bio-GRID、Email-Enron、DBLP 3个数据集上的实验结果表明,相对于CRK-G算法,CRK-C、CRK-F算法在查询速度上有较大的提升,且平均误差均在8%以内。

关键词： 动态网络   社团发现   增量   网络突变   累积误差  

摘要： 当前主流的动态社团检测算法通常基于社团结构平稳变化的假设,不能很好地处理网络突变和累积误差,提出一种增量式动态社团检测模型。将前一时刻的社团结构作为初始聚类结果,利用链路变化找出增量相关社团,利用网络变化度和社团稳定度局部调整初始聚类,得到符合当前网络拓扑的社团结构。在真实网络和合成的动态网络中的实验结果表明,所提算法可以准确地发现动态网络社团结构,能有效解决网络突变和累积误差等问题。