关键词： 复杂网络   社区检测   核心度   重叠社团  

摘要： 针对含有重叠节点的社团提出了新的检测算法—NCD算法。提出了节点核心度的概念,按照节点核心度的计算方法选取簇的初始中心点;提出差异性函数对重叠部分的节点进行识别;在中心点扩展原则的指导下,通过判断网络中节点之间可否构成三角模型对重叠社团进行检测。使用了NMI和模块度作为社团检测的指标,将NCD算法应用在3个真实网络数据集上进行实验,结果表明,NCD算法可以高效地检测到社团中的重叠节点,同时表明了该算法与其他算法对比具有明显的优越性。

关键词： 社团检测   节点内容   先验信息   随机块   非负矩阵分解  

摘要： 在复杂网络分析中,社团检测发挥着越来越重要的作用,而在实际应用中如何提高社团检测的性能仍是一个共同研究目标.由于网络节点中内容信息有助于社团识别,一些方法侧重于将网络拓扑和节点内容相结合,并且获得了不错效果.此外,也有些方法借用节点之间的拓扑相似度,以提升实现社团检测性能.鉴于此,我们提出了一个统一化方法,结合节点内容的半监督社团检测,简称SCDNC.在该方法中,我们不仅将链接增强应用于社团检测,而且实现了拓扑和内容有机融合.首先,我们运用随机模型来描述节点社团隶属度.其次,我们构建出一个刻画节点内容社团隶属度的随机块模型,节点社团隶属度作为节点内容的权重向量,以实现拓扑和内容结合.再次,我们利用网络中节点之间的拓扑相似度构建先验信息,即,使网络中节点与其最相似的邻居节点具有相同的隶属度分布.最后,使用非负矩阵分解的方法学习新模型的统一化参数.在带有真实标签的人工网络和真实网络上,我们对新方法与一些当前流行的社团检测方法进行了性能比较.实验结果显示,通过融合节点内容和先验信息强化的链接,新方法检测社团的性能取得了显著提升.

关键词： 社团检测   边重整化   随机游走   相似性   模块度  

摘要： 现实网络构造过程中,存在连接数据不完整甚至自相矛盾等问题,且现有的社团检测算法易出现丢失部分连接信息等现象,为此,提出一种基于边重整化方法的新社团检测算法。根据“节点间相似性越小则属于同一社团的概率也越小”原理,引入节点间随机游走的稳态概率来衡量节点之间的相似性,不断移除相似性最小的现存连边,并补充相似性最大的丢失连边,以保持网络总连接边数不变。最后通过实例验证了新社团检测算法的有效性。

关键词： 大规模   复杂网络   图重构   社团检测  

摘要： 对大型复杂网络进行高质量的社团检测通常依赖图的拓扑结构来划分节点集,然而现实世界的网络通常带有嘈杂且与集群无关的连接,这些链接可能会导致模型将来自不同集群的节点划分在一起。为此,提出了基于图重构的社团检测算法(graph reconstruction based community detection,GRCD),该方法能够处理大规模复杂网络的社团检测。首先,删除社团之间的相互连接的边来重新构建原始图的社团结构;然后,将网络视为一个社交系统,旨在以更直观的方式揭示社团;提出了一种高效的社团检测策略,即基于话语权的社团组织生成策略;最后,在不同规模数据集上进行实验。实验结果表明,GRCD算法不仅能够处理大规模网络,而且在保持较高稳定性的同时,其社团划分的质量对比现有的几种基准算法都有很强的竞争力。

关键词： 局部社团检测算法   属性网络   进化多目标优化  

摘要： 在过去的二十年中，挖掘网络中的全局社团结构一直是一个热门的研究课题，但这些研究通常要求网络的全局信息是已知的。随着互联网的发展和网络规模的不断增大，许多网络的全局信息可能不可用或获取成本高昂，如万维网和社交网络等。因此,基于网络局部信息的局部社团检测应运而生，其目的是基于网络的局部信息找到包含给定起始节点的社团。近年来，研究人员提出了大量的局部社团检测算法，其中，进化算法具有良好的全局搜索能力以及对目标函数的开放性，因此基于进化算法的局部社团检测方法成为解决局部社团检测问题的重要方法之一。然而，现有的基于进化的局部社团检测算法忽视了网络的重叠结构和属性信息，因此本文提出了基于多目标进化的局部重叠社团检测算法以及基于多目标多任务进化的属性网络局部社团检测算法。　　本文的主要研究工作如下:　　(1)提出了用于局部重叠社团检测的多目标模型和多目标进化算法。为了解决局部重叠社团检测问题，本文首次将局部重叠社团检测问题建模为多目标优化问题，并提出了基于三分表示的局部重叠社团检测多目标进化算法(TDR-MOEA)。该多目标模型由两个目标函数组成，即社团内部连接密度和社团外部连接密度。在TDR-MOEA算法中，提出了三分个体表示方案，以有效地编码和解码给定节点的局部重叠社团结构。基于该表示方案，设计了新颖的初始化策略和进化算子，以提高TDR-MOEA的性能。最后，本文通过在具有不同特征的合成网络和真实网络上的进行实验，验证了所提多目标模型和TDR-MOEA的有效性。实验结果表明，TDR-MOEA算法在检测局部重叠社团方面优于当前的局部重叠社团检测算法，同时也表明多目标进化是处理局部重叠社团检测问题的一个有竞争力的框架。　　(2)提出了基于多目标多任务进化的属性网络局部社团检测算法。属性网络主要包含两个维度的信息，一个是拓扑结构，另一个是节点属性。为了更好地平衡和利用这两个维度的信息，本文提出了一种基于多目标多任务进化的属性网络局部社团检测算法(EMLCD)。在EMLCD算法中，属性网络局部社团检测问题被表述为具有两个任务的多任务优化问题，即拓扑局部社团检测任务(Top-Task)和属性局部社团检测任务(Att-Task)。使用多任务进化方法来检测属性网络局部社团的优势在于，该方法中的知识迁移机制可以用于平衡拓扑和属性信息，并提高检测性能。因此，在EMLCD算法中，提出了高效的知识迁移策略来促进两个任务之间的正向知识迁移。此外，本文提出了模型选择策略，以指导决策者从两个任务得到的解集中选择理想解。实验结果表明，EMLCD可以更好地平衡拓扑和属性信息，从而检测到高质量的局部社团。

关键词： 符号网络   社团检测   凸非负矩阵分解   平衡理论   图神经网络   社交网络   舆情分析   微博  

摘要： 在现实复杂系统中,成员之间不仅存在支持、信任、促进等积极交互,同样存在反对、怀疑、抑制等消极交互,符号网络通过引入节点间正、负连接直观灵活地描述这类信息,由于其包含更加丰富的复杂系统信息,有助于全面深入地挖掘个体之间的联系,符号网络逐渐成为国内外各领域学者研究热点之一。社团结构作为符号网络分析的基础,对揭示复杂系统的组织构成、功能结构和个体行为具有理论意义和实践价值,相关研究成果被广泛应用于推荐系统、公共安全、生物医学、社交网络等诸多领域。尽管近年来符号网络社团检测算法研究频出,取得了一定的进展与成果,但主流算法大多存在数学模型过于复杂、时间复杂度高、难以应用于大规模网络等缺点,而众多较为成熟的传统社团检测算法又由于负属性边的影响无法直接应用于符号网络,准确快速地检测出符号网络中的社团结构仍是具有挑战性的任务。针对上述问题,本文基于凸非负矩阵分解和图卷积神经网络分别提出了两种符号网络社团检测算法,并将算法应用于舆情分析领域。论文主要研究内容如下:(1)从简化数学模型复杂程度的角度出发,本文设计了一个基于归一化拉普拉斯矩阵和凸非负矩阵分解的算法(NLRCovex-NMF)来检测符号网络中的社团结构。该算法将凸非负矩阵分解应用于符号网络,将邻接矩阵分解为社团成员归属矩阵和节点权重矩阵,易于理解和实现,同时该算法引入了归一化拉普拉斯图正则项,减少分解过程中产生的噪声。通过人工网络和真实网络的对比实验验证,该算法在小规模无符号网络和符号网络均具有较为有效的社团划分性能。(2)针对NLRCovex-NMF算法时间复杂度高,难以将其应用于大规模符号网络的问题,本文提出了基于结构平衡理论的图卷积聚类网络(CNSBGCN)。该算法将社会学平衡理论和图卷积神经网络相结合来提取图结构和节点属性的隐藏信息,形成有效的节点嵌入表示。算法设计了基于最大化符号网络模块度的损失函数,通过端到端学习的方式完成社团检测任务。通过在多个不同特征的网络数据集进行对比实验,验证了该算法能够在较大规模符号网络上检测出较为准确的社团结构。(3)将理论成果应用于“风险舆情发现与处置”项目中,结合公开检测的某次新冠疫情舆情事件中新浪微博相关内容数据、转发和评论信息,计算情感得分,分时段构建符号网络,利用本文所提算法挖掘舆情演化过程中核心群体结构变化特征,在验证论文所提算法有效性的同时,为深入开展舆情发现、舆情演变趋势预测、舆情引导目标群体识别等工作提供数据分析辅助支撑。

关键词： 鲁棒社团检测   自步学习   集成聚类   推荐系统   协同过滤  

摘要： 社团检测一直是复杂网络中的重点研究领域。在近年的研究中,人们发现网络中细微的噪声会给社团检测算法带来巨大的负面影响。其主要原因是:它们假设输入的网络是完美干净的。然而,收集的网络数据充满了噪声,并且很难确定噪声的类型。比如,偶然产生的随机噪声和对抗攻击产生的恶意噪声就会使得网络呈现出不一样的数据特征。为克服噪声对社团检测性能的影响,如何设计鲁棒社团检测算法成为研究的热点。现有研究常利用噪声类型先验来增强网络,实现鲁棒社团检测。先验信息是很难获得的,因此这种方式在实际使用时有着诸多的限制。针对这一问题,本文提出了基于自步学习和集成聚类的鲁棒社团检测算法。通过利用基础模型信息替代噪声类型假设,从损失函数和基社团两个不同角度克服了传统社团检测算法面对噪声网络时性能下降和现有鲁棒社团检测算法应用受限的问题。另外,互联网的高速发展使得推荐系统已经成为人们日常生活的一部分。本文深入探究了协同过滤技术进行推荐任务的数据稀疏性和噪声问题,并提出了一种基于鲁棒社团检测的方案,同时将上述鲁棒社团检测方法应用于该场景。本文的工作总结如下: (1)提出了一种基于自步学习的鲁棒社团检测框架,称之为Silencer。Silencer通过将自步学习框架和基于像素损失的社团检测算法进行结合,使得算法在迭代过程中能够自动根据像素级损失定位噪声边,从而降低其对模型的影响以提高模型的鲁棒性。本文成功地将非负矩阵分解算法(Nonnegative Matrix Factorization,NMF)和深度自编码器算法(Deep Autoencoder-like Nonnegative Matrix Factorization for Community Detection,DANMF)嵌入到Silencer框架。相比传统社团检测方法,Silencer能更好地适应包含噪声的真实网络,减少了人工鉴定噪声边所耗费的时间成本。 (2)提出了一种基于集成聚类的鲁棒社团检测算法(Ensemble Clustering Robust Community Detection,EC-RCD)。EC-RCD改进基于模块度的传统社团检测算法和共识网络生成算法,得到了偏离者和平等者两个模块。与其它鲁棒社团检测方法最大的不同在于,此方法增强网络的信息,来自多次运行基础算法得到的结果,而不是一些基于网络特征的先验假设。这两个模块使EC-RCD能够在没有任何先验噪声假设和数据特征假设的情况下实现鲁棒社团检测。 (3)随着数据量的增大,如今靠人力面对数以亿计的商品已经很难完成推荐任务,因此推荐系统已经成为当下最热门的研究话题之一。现有推荐系统中最常用的就是协同过滤技术,但不论是基于相似度函数还是基于传统社团检测,在得到相似用户的过程中都会不可避免的存在稀疏性和噪声问题。因此,本文将EC-RCD与协同过滤技术进行结合,它能既能继承社团检测算法解决稀疏性问题的优势,又能缓解噪声带来的社团检测性能不佳的问题。

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

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

关键词： 社团检测   鲸鱼算法   标签传播算法   多目标优化   共识社团   标签传播  

摘要： 复杂网络中的社团结构对于了解网络结构、发现其变化过程与规律、监控与预测变化趋势有着重要的理论意义。从复杂网络中检测出这些社团结构对于推测用户潜在意向、预测研究方向进展、舆情控制和导向、打击恐怖分子维护国家安全、减少部署成本等有着良好的应用前景。近年来，研究者们已经提出许多社团检测算法用于社团挖掘、社团分析和社团预测等领域，但在先验知识很少或者完全没有先验知识的情况下提高社团检测的准确率，同时降低时间复杂度，特别地，对于基于优化的进化算法框架的算法来说，是否能进一步提高种群收敛的速度，能够跳出局部最优的陷阱，一直是社团检测方法研究的重点。基于此，本文提出了两种社团检测算法，主要的研究工作如下：　　1.提出一种基于鲸鱼算法的多目标静态网络社团检测算法。传统的针对静态网络基于优化算法的社团检测算法往往采用单目标优化，或者在选取最优解时将多目标加权相加，最后转化为单目标的方式进行，但这样的方式要么面对多个约束条件时无能为力，要么没法精确掌握线性组合的参数以获得最优的解。鲸鱼算法是模拟座头鲸群狩猎行为的一种启发式算法，它有着实现原理简单、控制参数少、对于解决某些优化问题具有收敛能力快、全局搜索能力强的特点。原始的鲸鱼算法针对的是连续函数的优化，本文采用了针对社团检测问题改进的离散化鲸鱼算法算子对问题进行多目标优化。通过标签传播算法生成初始种群，并借助鲸鱼算法框架对种群进行多目标优化以得到社团划分。将该算法在人工合成网络和真实世界网络的数据集上进行实验，实验结果表明所提出的算法具有较好的性能。　　2.提出一种基于共识社团鲸鱼算法的多目标动态网络社团检测框架。随着带有时间信息的数据大量涌现，动态网络社团检测逐渐成为研究的重点。动态网络是随着时间变化而变化的，而动态网络的社团检测应能体现出社团结构随着时间的变化，但同时还要使这种变化不是很剧烈，减少结果的漂移。针对该问题，本文引入了种群内共识和种群间共识，缩小检测结果在时间变化时带来的影响。为了进一步减少初始化的开销，使用标签传播算法对网络迭代少数次以保持种群的多样性和正确性，接着使用鲸鱼算法框架对网络进行迭代，寻找最优解。在迭代过程中计算共识社团，在一定条件下将共识社团插入种群中以保持种群中含有上一时刻的知识从而使种群向最优的方向进化。将所提算法与对比算法在人工合成的和真实世界的网络数据集上进行测试，实验结果表明所提方法具有较好的性能，具有比较强的竞争优势。

关键词： 复杂网络   社团检测   重叠社团   马尔可夫链  

摘要： 现实世界中大量的系统都可以被视作复杂网络,社团检测作为复杂网络中的热点问题之一,在过去的几十年里引起了广泛关注并得到了大量研究,在各行各业里得到了广泛应用。虽然许多方法在这个问题上表现良好,但现实世界中的网络种类繁多,如果网络具有一些很复杂的特征,例如非常稀疏、社团结构不明显或社团结构重叠性太强,这些方法就会变得无能为力。 为了解决这些问题,本文研究了一种基于马尔可夫链的社团检测模型(Community Detection Model based on Markov Chain,CDMMC)。具体工作如下: (1)为了解决非重叠社团检测领域普遍存在的社团检测算法应用于稀疏网络以及社团结构不明显的网络上效果不佳的问题,本文将CDMMC应用到了非重叠社团检测领域提出了图重构(Graph Reconstruction Method,GRM)算法。在GRM算法中,通过四种基于马尔可夫链的特征提取方法来提取网络蕴含的结构化特征,从而得到一个概率特征矩阵,通过该矩阵利用GRM算法对新图进行进一步的重构,并用重构后的图代替原来的网络进行社团划分,最终提取这个新的网络的连通分量即可得到社团的划分,实现非重叠社团检测。最后可以利用Leiden算法对GRM算法进行局部优化,使整体社团检测算法的效果更加突出。在240个不同参数的人工网络数据集和6个不同的真实网络数据集上关于图重构(GRM)算法和带有Leiden优化的图重构(GRML)算法与其他8种经典的非重叠社团检测算法的对比实验证明了算法的有效性、准确性和优越性。实验表明,当网络较为稀疏时或社团结构不明显时,本算法与其他8种经典算法相比优势非常明显。 (2)为了解决重叠社团检测领域普遍存在的社团检测算法应用于强重叠网络上效果不佳的问题,将CDMMC应用到了重叠社团检测领域提出了图吸收(Graph Absorbing Method,GAM)算法。GAM算法在得到概率特征矩阵后,首先会初始化一个以节点重要性排序的序列,然后把该序列作为吸收的种子节点利用概率特征来吸收其他节点,直到社团达到指定数量或者无法继续。对于每个没有被吸收的孤立节点,最终算法会将其归入与该节点最匹配的社团中。在人工和真实网络数据集上的实验表明,GAM在重叠社团检测领域优于其他的对比算法,特别是在社团结构重叠性更加强烈的数据集上。