关键词： 社团检测   节点影响力   标签传播   种子扩展  

摘要： 现实世界中的复杂系统可使用网络科学的方法将其抽象为复杂网络,复杂网络的重要特征之一是社团结构的存在。通过社团检测算法挖掘复杂网络中的社团结构可以深入了解网络结构特性、探索网络上节点间更深层次的联系。目前,复杂网络中的社团检测研究成果已广泛地应用于不同领域的网络中,如社交网络、合作网络、生物网络和交通运输网络等。节点影响力是网络中节点的一个重要特征,对网络中节点影响力的研究,可以促进其他网络科学领域的发展。本文提出了一种节点影响力计算方法,然后基于该方法改进了两种社团检测算法并将其应用于甘肃省媒体融合技术与传播重点实验室的子课题中。主要研究内容如下:(1)节点在网络上重启随机游走后的平稳概率可以很好地表示节点间的相关性,但是由于其高复杂度而无法适用于大型网络。本文综合考虑算法复杂度和算法性能,提出了一个基于局部重启随机游走的节点影响力计算方法NILR(Node Influence based on Local Random Walk with Restart):将节点的游走范围限制在其一阶邻域子图内,以节点处于稳态时的概率分布表示邻居节点对其的互影响力,再根据节点对其邻居节点的互影响力和来表示节点在网络中的影响力。(2)为了解决原始标签传播算法LPA(Label Propagation Algorithm)存在的不稳定问题和提升算法性能,本文提出了一个基于NILR的标签传播社团检测算法NILR-LPA(NILR based Label Propagation Algorithm)。算法使用本文提出的NILR方法进行预计算,以节点影响力升序的方式序列化节点标签更新顺序,在标签传播过程中设置一个参数选择传播标签的邻居范围,以传播节点标签的互影响力和指导标签选择。同时还提出了一个后处理方法,进一步提高算法准确度。最后通过在人工网络和真实网络中的对比实验验证了算法的有效性。(3)选取更具代表性的种子节点和更准确的社团扩张策略是种子扩展算法的研究重点。本文提出了一个基于NILR的种子扩展社团检测算法NILR-SE(NILR based Seed Expansion)。算法首先根据NILR方法计算的节点影响力,选取出覆盖范围广的种子节点集合,然后利用节点间互影响力定义节点间相似性并以此指导社团扩张得到初始社团结构,最后结合标签传播算法的思想,根据初始社团结构初始化节点标签,使用修改的NILR-LPA算法合并社团,以提高算法检测的社团结构质量。与NILR-LPA相比,NILR-SE不需要调节参数,标签收敛速度加快,在一些真实网络的实验中,能取得更好的效果。(4)将提出的NILR-SE算法应用于新闻内容的个性化推荐。根据用户阅读新闻数据构建用户偏好网络,使用NILR-SE算法检测出兴趣相似的用户群体,根据群体特征提出一种个性化推荐机制。同时社团结构结果也可作为课题中其他研究任务的数据基础。

关键词： 肺腺癌   多层组学网络   社团检测   关键基因   多目标优化  

摘要： 肺癌是近年来中国致死率最高的癌症,其中肺腺癌是肺癌最常见的亚型。肺腺癌分期有Ⅰ、Ⅱ、Ⅲ、Ⅳ期,随着肺腺癌分期数的增加,患者的生存率显著下降。准确识别肺腺癌的关键基因能够在降低肺腺癌早筛成本的同时提高诊断的准确性。高通量测序技术的发展和组学数据的积累为肺腺癌关键基因的识别提供了数据基础。基于单一组学数据的关键基因识别方法会割裂生物功能,而基于多层组学网络社团检测的关键基因识别方法能够在融合多种组学数据的同时,挖掘肺组织的基因模块,从而提高肺腺癌关键基因识别方法的稳定性和准确性。本文研究基于多层组学网络社团检测的肺腺癌关键基因识别方法,用于肺腺癌患者的生存分析和诊断。主要研究成果如下: 构建了基于高通量测序数据的肺组织多层组学网络,融合肺腺癌相关的四种组学数据。分别构建基因共表达网络、转录因子共靶向网络、微RNA共靶向网络和蛋白质相互作用网络。提取四个单层网络的共有基因,构建反映肺腺癌组织与正常肺组织功能差异的多层组学网络。此外,为解决各层网络密度过高的问题,设计了边过滤算法。实验结果表明,与传统的边过滤方法相比,本方法过滤后的网络密度至少降低31.68%。 提出了基于多目标优化重叠社团检测的肺组织基因模块挖掘算法,挖掘具有重叠特性的肺组织基因模块。实验结果表明,本方法可以提高肺组织多层组学网络基因模块的挖掘性能,在肺腺癌组织与正常肺组织的多层组学网络中分别挖掘到165和183个基因模块,与现有算法相比具有较好的分布均匀度。 提出了基于基因模块的肺腺癌关键基因识别算法,设计了基于差异性基因模块和重叠节点的关键基因识别算法,提高了肺腺癌关键基因的识别率。实验结果表明,本方法识别到的关键基因均与肺腺癌关系密切,10个关键基因中的9个具有肺腺癌生存分析的显著性差异,优于推荐检测基因,且在GSE10072和GSE75037数据集上的肺腺癌诊断准确率均达到96%,准确率与推荐检测基因的准确率相近。

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

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

关键词： 社团检测   网络嵌入   深度学习   重叠社团   图卷积网络  

摘要： 随着大数据技术的愈发成熟,网络数据集复杂程度不断提高,复杂网络方向的研究受到了学者们的更多关注。社团检测是复杂网络中的重要研究方向,其目的是在复杂网络中找到连接更加紧密的节点集合。而随着深度学习技术在复杂网络方面研究的普及,越来越多的复杂网络传统问题可以获得新的解决方案。其中,网络嵌入由于其可以将图数据映射到低维向量上这一特点从而避免了直接处理复杂的非线性结构的网络数据,因此可以很好地适应对复杂数据集的后续处理以及复杂网络上的相关研究。然而,现有的基于网络嵌入的社团检测算法还存在以下问题:(1)部分网络嵌入算法训练得到的节点嵌入向量在训练过程中没有考虑社团信息,因此得到的节点嵌入在聚类之后得到的社团划分结果不是很好。(2)大部分算法无法很好的将网络结构信息映射到网络嵌入向量这个过程与社团检测联系起来进行考虑,从而在应对一些网络连接结构复杂、社团结构不明显的数据集时,社团划分结果较差。(3)目前的网络嵌入算法对于重叠社团检测的考虑不够充分。为了更好的应对这些问题,论文提出了基于多聚类损失函数的网络嵌入方法(GEMMC)以及基于改进GCN的深度网络嵌入方法(DGEMOC)分别来处理非重叠社团检测以及重叠社团检测任务。论文的主要工作如下: (1)现有的部分嵌入方法在应对社团检测任务的时候通常只使用单一聚类损失函数来指导训练。在实际的任务中,往往会出现在部分的网络数据集中由于聚类损失本身的缺陷从而造成社团划分结果较差的情况。本文提出的GEMMC方法在训练过程中,同时添加聚类距离损失函数以及高斯混合模型的损失函数来指导嵌入向量的训练,并最终得到节点嵌入向量以及聚类嵌入向量,通过聚类方法可以得到社团划分。另外为了解决社团结构不明显时社团划分结果较差的问题,还对算法的节点采样方式进行了改进,在采样节点的过程中以一定概率可以直接得到与当前节点相似度最高的邻居节点。通过这种方法可以有效提高社团划分的质量。 (2)传统的图嵌入方法由于自身的局限性在处理重叠社团检测任务时的表现很难令人满意。本文提出了一种基于图卷积神经网络的图嵌入方法DGEMOC以更好的完成重叠社团检测任务。在实验中,对传统的GCN编码器进行了改进,加入了图扩散卷积,残差连接和基于相似度的卷积矩阵来优化模型并通过编码器得到隶属度矩阵,伯努利-泊松解码器根据损失函数不断对编码器生成隶属度矩阵的过程进行优化,最终选取合适的阈值在最终生成的隶属度矩阵上获得重叠社团划分结果。 (3)为了验证文中所提算法的性能,论文采用归一化互信息(NMI)和模块度作为评估社团检测的指标分别在LFR人工网络和多个现实图中与同类型的相关算法进行比较来评估GEMMC的性能,除此之外采用重叠归一化互信息(ONMI)和Omega指标作为评估重叠社团检测的指标在LFR人工网络和现实数据集中与相关算法进行比较以评估DGEMOC的性能。实验结果表明,GEMMC和DGEMOC在社团检测表现中发挥良好,在多数情况下能明显优于同类相关算法。

关键词： 社团检测   节点引力   种子扩展算法   标签传播算法   个性化推荐  

摘要： 复杂网络是由节点和节点之间的复杂关系构成的网络结构,是对现实世界中的各种复杂系统的抽象,社团结构是复杂网络的显著特性。社团检测算法可以揭示网络的拓扑结构,挖掘复杂网络中的潜在信息,可广泛应用于个性化推荐、公共安全、社会科学等领域,具有重要的研究意义。本文针对常见的种子扩展算法和标签传播算法中存在的问题,提出了两种改进算法。本文的主要研究内容和成果如下:(1)针对种子扩展算法种子节点挑选欠佳和社团扩展方法不当等问题,本文提出一种基于CRITIC法和节点引力的种子扩展算法(Seed Expansion Algorithm based on CRITIC and Node Gravitation,SECNG)。该算法首先使用CRITIC法对节点的介数中心性、接近中心性、度中心性客观赋权,定义了节点综合重要性(Node Comprehensive Importance,NCI),并按照该重要性指标的递减顺序来挑选种子节点。然后提出了基于节点综合重要性的节点引力和社团引力的概念,在社团扩张阶段,按照NCI的递减顺序,将未划分社团的节点扩展至对它社团引力最大的社团。最后本文提出了基于模块度增量的社团优化方法,每次迭代时将模块度增量最大的两个社团合并,进一步提升了算法的准确度。(2)针对标签传播算法的高随机性问题,本文提出了基于节点影响力和节点引力的标签传播算法(Label Propagation Algorithm based on Node Influence and Node Gravitation,LPANING)。该算法首先基于Page Rank和度中心性定义了节点影响力(Node Influence,NI)这一指标,并按照该指标的递减顺序对节点进行排序从而确定标签初始化及标签更新的顺序。然后定义了基于节点影响力的节点引力(Node Gravitation based on Node Influence,NGNI),当节点具有多个候选标签时,选择与该节点引力最大的节点的标签。最后算法根据社团相似度将小规模社团进行合并,从而提高了算法的稳定性和准确性。相关实验表明,论文提出的SECNG算法和LPANING算法在多组人工网络和真实网络上均有良好的表现。(3)论文将上述两个算法应用于某省的科技计划项目中。根据阅读行为构建融媒体内容阅读数据中的用户复杂网络,结合社团检测算法对用户进行个性化推荐,在注重用户喜好的基础上促进主流价值观的传播。

关键词： 社团检测   局部扩展   高阶结构   关系强度   中心性度量  

摘要： 现实中的很多复杂系统可以被抽象为复杂网络。社团是复杂网络中重要的结构特征。社团内部的节点彼此连接紧密,而不同社团之间连接稀疏。研究复杂网络的社团结构特征对于探索和揭示复杂系统的功能特性具有重要意义。目前社团检测算法的研究已经取得了长足的进展,但同时也存在很多不足之处。其中,在基于种子的局部社团检测方法中,种子节点选取方式、社团扩展方式以及社团边界节点处理方式还需要进一步研究。本文使用邻居间结构特征来检测社团,主要的研究内容包括以下两个方面。针对网络中连接紧密且相似度高的邻居节点不能合理划分到相应社团的问题,本文提出了一个局部视角下基于高阶三角形的社团检测算法LEHT。该算法首先依据节点与其邻居节点之间的局部关系,为每个节点依次构建高阶三角形。若该节点与邻居节点构成多个高阶三角形时,使用本文定义的三角形相似度计算该节点构建的高阶三角形的稳定性,选择稳定性最大的三角形作为该节点的高阶三角形。迭代此过程,直到所有满足高阶三角形的节点都有唯一的高阶三角形,高阶三角形中的节点形成初始社团。接着,对于高阶三角形中的每个节点,若该节点满足所属的高阶三角形与邻居节点的高阶三角形之间有多个公共节点且连接紧密,就将两个高阶三角形合并。迭代此过程,直到将所有满足条件的高阶三角形都进行合并为止,初始社团的扩展完成。最后,对于不能构建成高阶三角形的节点,计算该节点在社团中的邻居节点的接近中心度,把该节点加入到邻居节点接近中心度最大的社团,形成最终社团。在真实网络和LFR基准网络上,将LEHT算法与五个经典算法的实验比较分析,结果表明算法LEHT的性能表现更好。针对局部社团检测算法对种子节点选择敏感和对社团扩展的不稳定问题,本文提出了一种基于高阶结构与关系强度的社团检测算法HTRS。该算法首先定义了一种高阶结构motif度,根据每个节点的motif度把节点划分为高阶节点和边缘节点,根据高阶节点的局部邻接密度自适应地确定社团的核心节点。通过核心节点与其连接紧密邻居节点构成的多个高阶结构motif,使用关系强度rs1选择其值最大的高阶结构motif作为初始社团。接着,在高阶扩展阶段,根据高阶节点与社团内节点连接的个数不同,继续细分为两种扩展方式。当社团内两个节点与社团外的一个高阶节点构成高阶结构motif时,通过收益函数将此高阶节点扩展到社团中。对于社团内一个节点与社团外两个高阶节点构成高阶结构motif,通过关系强度rs2将此高阶节点扩展到社团中。迭代此过程,直到将所有的高阶节点加入到社团为止。最后,在低阶扩展阶段,该算法定义了一种关系强度rs3,它同时考虑了边缘节点连接到社团内节点数量与节点的影响力两个因素来确定该节点归属的社团。把边缘节点加入到关系强度rs3值较大的邻居节点所在的社团,形成最终的社团。在真实网络和LFR基准网络上的实验结果表明,HTRS算法能够以高精度和高稳定性地检测社团。综上所述,本文提出的LEHT与HTRS算法都使用了邻居节点间的高阶结构特征,通过局部扩展的方法来检测社团。LEHT算法解决了紧密相邻的节点不能合理划分社团的问题,HTRS算法解决种子节点选取导致社团扩展不稳定的问题。本文的算法检测到了质量高且鲁棒性强的社团。它们对于检测社团结构提供了一个可行的解决方案。

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

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

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

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

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

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

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

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