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

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

关键词： 社团检测   结构信息矩阵   节点相似度   复杂网络   动态网络  

摘要： 随着时代的发展,越来越多的由人或物组成的复杂系统和关系被建立起来,它们当中的大部分都可以用复杂网络模型来描述和概括。网络中的节点和边分别表示这些复杂系统中的实体和实体之间的联系。社团是复杂网络的一个重要特征,同一个社团内部的节点联系紧密,而不同社团中的节点之间的联系相对稀疏。社团检测是复杂网络研究领域中一个热门的研究方向,它的目标是将复杂网络中关系紧密的节点划分在一个社团之中。随着时间的推移,现实世界网络的拓扑结构会发生变化,由此形成了动态复杂网络。现实世界中的动态网络的相邻快照的变化是平滑的,一般不会非常剧烈,即两个相邻快照之间的社团结构应该是相似的。因此动态网络中社团检测的目标是在动态网络的每个快照上得到高质量的社团结构,并在此基础上兼顾相邻快照的社团结构的接近程度。研究复杂网络中的社团检测问题对于许多领域都有着十分重要的意义。已经有许多研究者在社团检测领域中进行了大量的研究,开发出了大量的算法。通过详细深入的研究,本文基于网络结构信息矩阵提出了一种静态网络中的社团检测算法和一种动态网络中的社团检测算法。(1)静态复杂网络中基于结构信息矩阵和非负矩阵分解的社团检测算法SIMNMF(Community Detection Algorithm Based on Structural Information Matrix and Non-negative Matrix Factorization in Static Complex Networks):该算法利用网络的中心节点与其邻居之间的联系信息,构造一种新的结构信息矩阵,并将此矩阵与其他两种体现网络结构信息的矩阵相融合,进行非负矩阵分解获得社团结构。在真实的社团结构中,一个社团的中心节点的邻居与该中心节点处在同一个社团的可能性较大,如果它们不处在同一个社团中,则意味着此邻居周围存在一个与其关系更加紧密的中心节点。相较于其他普通节点,中心节点在网络中的此类信息是已知的,因此,可以利用中心节点与其周围的节点的关系为非负矩阵分解的过程提供指导,使得获得的社团结构的质量更高。该算法首先通过一种快速的社团检测算法获得网络中的中心节点集合,通过中心节点与其邻居节点的联系信息构造成一个中心节点信息矩阵,再通过将中心节点信息矩阵与网络的节点相似度矩阵和网络的邻接矩阵进行融合,构造成一个新的结构信息矩阵。最后,将此矩阵进行非负矩阵分解,通过得到的社团归属度矩阵获得社团结构。(2)动态复杂网络中基于迁移的节点相似度矩阵的社团检测算法m NSMA(Community Detection Algorithm Based on Migrated Node Similarity Matrix in Dynamic Complex Networks):该算法在第一个快照上直接计算节点相似度矩阵,并且在相邻的快照上通过节点相似度矩阵作为载体进行信息的传递,在每个快照上通过m NSMA中包含的静态算法NSMA获得社团结构。NSMA算法首先通过节点相似度矩阵和引入的一种新的投票方法获得种子节点,然后通过种子节点获取初始社团结构,再进行社团合并,最后调整部分节点的社团归属,获得最终的社团结构。在之后的快照上,算法将前一个快照的网络结构信息及社团结构信息聚合到当前快照的节点相似度矩阵中,并在当前快照中使用此节点相似度矩阵通过NSMA算法获取社团结构。通过上述的方法,最终得到所有快照的社团结构。为了验证以上两种算法的有效性,本文对两种算法都分别在人工合成网络和真实网络上进行了大量的实验,并将实验结果与多种算法进行详细的对比。最终实验结果表明,本文提出的SIMNMF算法在多数网络上都能获得高质量的社团结构,而m NSMA算法不仅能够在大多数动态网络上获得高质量的社团结构,并且能较好地提升相邻快照的社团结构的接近程度。

关键词： 社团检测   种子扩展   概率图模型   引文网络  

摘要： 随着计算机科学与技术的发展,如何从复杂的数据和网络中找到数据之间的逻辑关系,抽象出网络的数据价值是一个很重要的课题。近年来文献中涌现了大量社团检测算法将网络划分成不同的社团结构,基于马尔科夫随机场的社团检测方法在复杂网络中的社团结构检测方面具有很大的潜力,但是仍然存在准确性和效率不高,模型选择过拟合或欠拟合,算法复杂度高等一些问题。所以本文结合概率图模型和信念传播算法,提出了两种改进的基于概率图模型的社团检测算法,并将算法应用在实际项目中。主要的研究工作如下:(1)提出基于种子节点和信念传播的局部优化算法LOSN-BP,使用本文改进的启发式算法KSIE来挑选出种子节点,减少单一指标挑选种子节点带来的准确性不高的问题;社团扩张阶段,将模块度函数映射到能量函数中,改进BP算法中的消息传播机制,以种子节点为根节点,沿两层邻居节点构建概率图模型传播,挑选边缘概率最大的节点并入社团;为了保障算法的收敛性,本文使用计算几何中的拉普拉斯矩阵来调整概率图模型,确保算法能够在有限的时间内收敛到正确的结果;为了提高算法的准确性,在社团划分的后处理阶段,本文基于模块度最大化的策略和社团相似度来重新划分社团,进一步优化社团划分的质量。在不同类型的网络数据集上进行对比实验,验证了LOSN-BP算法的有效性。(2)提出基于Markov和信念传播的全局优化算法GOMK-BP,该算法将节点的相似性和重要性指标映射到能量函数中,同时优化改善了模型性能,结合指数函数和加权和的形式使算法达到更好的模型拟合效果;算法使用的概率图模型是全连通的马尔科夫随机场,为了提高算法效率和准确性,本文改进了传统的消息传播算法,使用压缩感知的方式加速算法的收敛;由于采用全连通的马尔科夫随机场可能会受到高计算复杂度的影响,本文调整了模型结构,引入稀疏连接以平衡计算效率和模型性能。在多组人工网络和真实网络上进行验证,结果表明了GOMK-BP算法确实能检测到高质量的社团结构。(3)将本文提出的算法应用到“英文中亚研究学术成果的文献网络和话语分析”项目中,根据某一领域文献或作者之间的引用关系构建网络。通过本文提出的算法进一步探索该领域的研究热点、趋势以及核心领域,识别出该领域的学术话语主导者,从而有效服务于话语模式分析,助力学术研究。

关键词： 复杂网络   社团   节点相似性   多尺度   分辨率极限  

摘要： 网络科学是一门新兴的科学,网络把真实世界中方方面面的问题抽象为元素和元素之间的联系。抽象的结果往往错综复杂,不能用简单的数学规律来归纳,具有这种拓扑结构即复杂网络。社团属性是复杂网络中继小世界和无标度性质后的一个重要特征。因此,社团检测是有理论和现实意义的。社团并不是只有单一尺度的,往往一个大社团中包含更多的小社团,换言之,社团的结构具有多层次性。为了探索网络的多尺度特性,开展了本文的研究。本文的工作主要分成两个方面:(1)基于节点相似性的多尺度社团检测。通过选择3个节点相似性指标,基于本文使用的节点相似性社团探测算法,来研究网络的多尺度特性。在文中,指出社团层次性与相似性阈值的变化范围有关,通过调节该范围,可以得到不同尺度下的社团结构。通过在真实网络数据和人造网络数据上进行实证分析。分析不同指标的具体社团检测特性,发现每个指标得到的结果是有差异的,通过深入分析每个相似度指标在多尺度社团识别优势和劣势。(2)利用模块度函数F2约束的Louvain算法检测社团。无论是一些多尺度社团检测方法还是基于Newman模块度函数Q的社团检测算法,都无法回避社团检测的分辨率极限问题。为了克服分辨率极限问题,提出了一种新的模块度函数F2,从理论上证明,本文提出的模块度函数F2比其他目标函数Q、D、F和M能更好检测社团结构。通过在网络数据集和其他目标函数进行实证分析,结果表明本文的算法是切实可行的。最后,通过比较带模块度函数F2约束和不带约束的情况对比,比较社团检测的效果,发现带模块度函数约束的Louvain算法有更好的表现。

关键词： 属性图   社团检测   图信号处理   自监督聚类  

摘要： 图结构被广泛地应用于计算机科学及其相关领域,图以显式且灵活的方式表达出数据间的复杂关联结构,在现代机器学习中发挥着关键作用。图聚类是图数据分析中发现社区和组的一个基本研究问题,旨在将网络划分为多个子结构,从而发现网络的底层结构并揭示其潜在功能。随着复杂网络的快速发展,图聚类过程需要有效地集成多个来源的复杂网络数据,如网络拓扑和节点语义,这对网络分析领域的发展至关重要。节点属性对节点的特性进行描述,为图聚类提供了丰富的有价值的信息,同时还可以补充网络结构,从而更好地挖掘出系统的潜在特征,揭示系统的功能。 由于拓扑信息和节点属性信息的异构型以及网络类型的复杂性,属性图聚类充满挑战。除此之外,现有的大多数属性图聚类算法将结构信息和属性信息线性融合之后采用传统的图聚类算法进行聚类,或分别对结构信息和属性信息进行聚类,在此基础上得到聚类的一致性矩阵。虽然这些方法利用了属性图中的两种信息,但无法充分融合拓扑信息和属性信息,挖掘出他们的关联性信息。针对以上问题,本文提出了两种属性图聚类算法:基于低频图信号处理和知识蒸馏的属性图聚类算法,基于自适应图信号处理的属性图聚类算法。本文的主要贡献和创新点可总结如下: (1)从同质图的视角来看,基于图中相邻节点更有可能属于同一类的假设,本文提出一种图低频信号处理和非负矩阵分解的属性图聚类算法。通过对节点属性矩阵进行图低频信号处理,可以有效对邻域节点信息进行聚合,使得相邻的节点有相似的节点属性,很好地融合了属性图的拓扑信息和属性信息。通过非负矩阵分解的方法可以提取特征并得到初步的聚类结果。之后选取伪标签,使用自监督学习的方法,不仅可以引导属性网络中拓扑信息和属性信息更深层次的特征的提取,还可以更新属性网络聚类结果,提升算法准确率。 (2)从异质图的视角来看,在现实世界中,图中相邻的节点可能来自不同的类别,导致网络具有异质性,本文提出一种自适应图信号处理的属性图聚类算。通过自适应地聚合邻域节点属性的低频部分和高频部分,可以有效解决目前图神经网络聚类算法中遇到的图异质性问题,处理不同类型的属性网络,提升算法的准确率。 本文在多个真实属性网络数据集上对比了多个同类属性图聚类算法,表明了本文提出算法思想的有效性和合理性,本文提出的两种算法不仅为属性图聚类问题提供了新思路,也具有一定的理论和应用意义。

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

摘要： 现实世界中的复杂系统可使用网络科学的方法将其抽象为复杂网络,复杂网络的重要特征之一是社团结构的存在。通过社团检测算法挖掘复杂网络中的社团结构可以深入了解网络结构特性、探索网络上节点间更深层次的联系。目前,复杂网络中的社团检测研究成果已广泛地应用于不同领域的网络中,如社交网络、合作网络、生物网络和交通运输网络等。节点影响力是网络中节点的一个重要特征,对网络中节点影响力的研究,可以促进其他网络科学领域的发展。本文提出了一种节点影响力计算方法,然后基于该方法改进了两种社团检测算法并将其应用于甘肃省媒体融合技术与传播重点实验室的子课题中。主要研究内容如下:(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%,准确率与推荐检测基因的准确率相近。

关键词： 慢性阻塞性肺疾病   复杂网络   社团检测  

摘要： 目的:　　基于网络分析法可以将共病分析转化为复杂网络上的社团检测问题以挖掘各种疾病之间关系的思想，本文提出通过对慢性阻塞性肺疾病患者电子病历数据进行分析，利用复杂网络模型构建不同类型的共病网络，以探究共病所属的不同社团结构，为防治COPD共病提供精准诊疗策略，简化个体化的医疗模式。　　方法:　　研究选取山西医科大学第二医院2011年12月至2022年9月慢性阻塞性肺疾病患者作为研究对象，横断面收集患者EMR信息建立单模共病网络与二分共病网络，使用Louvain算法对不同类型共病网络进行社团检测，分析归纳各网络社团划分结果;对不同性别COPD患者共病情况进行可视化，采用DIRTLPAwb+算法探究不同性别COPD患者的共病模式差异。　　结果:　　1、对所建立的两种共病网络使用Louvain算法进行社团检测后，二分共病网络社团划分模块度为0.232,单模共病网络社团划分模块度为0.206,单模共病网络被划分为3个社团，最大的社团包含20种疾病，最小的社团包含14种疾病，其中呼吸系统疾病被划分到一个社团，心血管疾病被划分到一个社团。根据二分网络社团划分的结果，可以大致分为5种社团:肺部疾病{肺部感染、间质性肺疾病、肺占位性病变、胸膜肥厚、类风湿性关节炎},心脑血管疾病{心律失常、冠状动脉粥样硬化性心脏病、中枢系统疾病、动脉硬化、心肌梗塞、高同型半胱氨酸血症、骨质疏松、腰椎间盘突出、泌尿道感染},代谢类疾病{高血压、糖尿病、脂肪肝、胆囊结石、继发性肥胖、高脂血症、甲状腺疾病、睡眠呼吸暂停低通气综合征、脾大},循环系统疾病{呼吸衰竭、肺源性心脏病、心力衰竭、胸腔积液、电解质紊乱、低蛋白血症、肺动脉高压、贫血、心包积液、肺间质纤维化、肺性脑病、腹水、肾衰竭、高黏滞血症},呼吸系统疾病{慢性阻塞性肺疾病、哮喘、支气管或肺恶性肿瘤、陈旧性肺结核、变应性鼻炎、支气管扩张、肝囊肿、前列腺增生、慢性胃炎、低氧血症、慢性乙型病毒性肝炎};2、在纳入的49种慢性病中有19种单个慢性病的患病率性别效应在统计学上显著，其中男性肺部感染、心律失常、哮喘、胸腔积液、肾囊肿、肝囊肿、动脉硬化、支气管扩张症、肺动脉高压、肺占位性病变、心包积液、低氧血症、肺间质纤维化、肺性脑病、高同型半胱氨酸血症、睡眠呼吸暂停低通气综合征、脾大的患病率均高于女性。共病对中呼吸衰竭&肺源性心脏病患病率最高，为21.51％,呼吸衰竭&肺部感染、高血压&肺部感染、呼吸衰竭&心力衰竭、高血压&心力衰竭、肺部感染&胸腔积液与肺部感染&心力衰竭的不同性别患病率有统计学差异;3、采用DIRTLPAwb+算法对不同性别COPD共病网络社团检测时，男性COPD患者共病网络被划分为7个社团，女性COPD患者共病网络被划分为8个社团，男性COPD共病网络密度与聚集系数分别为0.241和0.702,女性COPD共病网络密度与聚集系数为0.679和0.240,社团划分相似度指标NMI与ARI分别为0.231和0.465。　　结论:　　二分网络结构信息用于共病网络社团检测能更好的挖掘共病群体，在后续的研究中可以使用二分动态网络以探索COPD共病因果关系;不同性别COPD患者在单个慢性病和共病对患病率上都存在差异，男性COPD患者共病种类多于女性COPD患者。男性COPD患者共病网络较女性COPD患者共病网络更聚集和复杂，男性患者的共病模式比女性患者更复杂多样，疾病间联系更为紧密，在慢性阻塞性肺疾病患者中更应多关注男性患者以期减少共病的发生。

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

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