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

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

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

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

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

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

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

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

关键词： 复杂网络   聚类同步   牵制控制   社团检测   介数中心性   Ricci曲率   图扩散  

摘要： 在复杂网络研究中,网络的同步性状态和社团检测是两个十分重要的问题。同步性研究关注网络结构和功能之间的关系。社团检测是指将网络中的节点划分为不同的社团,以便更好地理解网络结构和功能。对于现存的网络同步性研究,存在只是在非奇异网络上研究,研究的网络同步状态过于简单等问题。针对于社团检测研究,现存的算法存在依赖于统计学特征、在大型网络上检测效果不佳、算法鲁棒性低等问题。在部分领域中,同步性实际上可以结合社团检测算法进行研究,两者的理论可以有机的结合在一起,但是相关的工作很少。针对以上这些问题,本文主要做了以下工作: 在第三章中,基于自适应牵制控制策略研究了具有多链路和时变延迟的奇异复杂网络的聚类同步问题。针对奇异网络研究了网络的聚类同步问题,奇异网络的动力学方程相比非奇异网络会更为复杂,相关的同步性问题也更难处理,并且奇异网络上的结论可以相应的转化到非奇异网络上,这使得本章的结论更具有价值。在研究中,奇异网络被构建为两层模型,这可以更准确地揭示领导者-跟随者层之间的层级结构。本章运用牵制控制手段达成网络的同步,可以有效的节省控制开销,针对于非线性多链路时变时滞网络的研究则使得本章的研究结果更具有普适性和实际应用价值。 在第四章中,结合复杂网络的同步性研究和社团检测算法,提出了一种基于社团检测和介数中心性的复杂网络牵制控制手段。在控制过程中,首先使用GN算法识别网络中潜在的社团结构,然后从每个社团中挑选介数中心性高的节点作为牵制控制的被控节点,并研究基于介数中心性重整化网络拓扑结构以加快网络系统响应的方法。实验证明从社团中筛选被控节点相比于随机选择可以有效的提高控制响应的速度,基于牵制控制的控制协议可以本质上地减少能量消耗和控制器的开销。而基于介数中心性优化网络的权值连接结构,可以使得网络系统具有更快的响应速度,更快的达成聚类同步。 在第五章中,研究了基于Ricci曲率的社团检测算法。通过计算节点之间的离散Ricci曲率,经Ricci流过程不断迭代收敛识别出网络中的社团结构。在Ricci曲率的基础上,本章还提出通过引入图扩散过程来改变Ricci曲率中节点的度量,可以令算法在大型网络上具有更高的准确率,在网络缺失节点时具有更高的鲁棒性。

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

摘要： 现实世界中大量的系统都可以被视作复杂网络,社团检测作为复杂网络中的热点问题之一,在过去的几十年里引起了广泛关注并得到了大量研究,在各行各业里得到了广泛应用。虽然许多方法在这个问题上表现良好,但现实世界中的网络种类繁多,如果网络具有一些很复杂的特征,例如非常稀疏、社团结构不明显或社团结构重叠性太强,这些方法就会变得无能为力。 为了解决这些问题,本文研究了一种基于马尔可夫链的社团检测模型(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在重叠社团检测领域优于其他的对比算法,特别是在社团结构重叠性更加强烈的数据集上。

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

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

关键词： 舆情分析   意见领袖   社团检测   加权TOPSIS   SIR模型  

摘要： 随着互联网技术和大数据的发展,越来越多的网民习惯从网络上获取自己所关注的信息资源、分享自己的见解或发表自己的意见,而这些活动的重要载体就是各种类型的网络虚拟社区,如微博。在微博环境中,网络舆论的形成在很大程度上受到意见领袖的影响。当网络中的意见领袖针对媒体所发布的信息、以及后续引起的讨论、最终在用户当中形成成熟的舆论时,对媒体解读与反解读显得更为重要。意见领袖所发挥的作用不仅可以吸引人们对话题的关注,推动网络舆论发展,而且其言论往往能得到社区其他用户的追捧与追随,并且大多数时候在他们在虚拟社区中具有较高的威望。 本文结合社团结构检测和意见领袖识别方法,以微博的“知网正在整改”话题的数据为研究对象,开展舆情事件网络中意见领袖分析研究。 第一部分采用基于节点向量的模糊C均值算法完成微博网络数据的聚类。通过模块度确定网络中每个节点的节点向量,即利用低维向量表示的节点,再在低维向量空间中利用模糊C均值对数据点进行聚类,从而得到网络的社团结构划分。将该算法和其他算法进行实验操作后对比分析,验证本文算法在网络数据聚类方面的精确性和稳定性,更好地挖掘社交网络的社团结构。 第二部分,采用多属性融合的加权TOPSIS法识别网络中的意见领袖。针对目前意见领袖识别过程多以用户属性或网络的结构信息作为指标的问题,以微博为研究对象,采用优序图法加权TOPSIS的相关理论建立意见领袖的识别模型。将用户的属性信息和网络的结构信息相结合作为综合评价指标,采用优序图法计算各指标权重,通过TOPSIS排序方法的用户重要程度评分,并对用户评分排序。针对微博的“知网正在整改”话题的数据,使用意见领袖识别方法进行实验分析,并与单测度指标方法进行对比分析,验证多属性决策意见领袖识别方法的有效性。 第三部分,将基于模糊C均值的社团检测算法和多属性融合的加权TOPSIS意见领袖识别算法相结合,构建基于社团结构的意见领袖识别模型:首先对所构建的舆情网络进行社团结构划分,然后通过使用多属性融合的加权TOPSIS意见领袖识别方法对社团内部进行意见领袖的识别。将上述混合模型应用到“知网正在整改”话题微博舆情网络中。并与结构中心性指标以及多属性融合的加权TOPSIS法所识别的意见领袖进行对比分析,通过SIR传染病模型验证混合模型的有效性。 最后,各项实验结果证明了本文所构建的模型对于意见领袖的判别较为合理。通过首先分析所构建的舆情网络的社团结构,再识别其中的意见领袖,在不改变用户影响力排名的情况下,能够准确、高效地识别微博网络中的意见领袖。

关键词： 复杂网络   社团检测   图重构   互信息   神经网络   核心节点  

摘要： 社团检测是一种基于图挖掘的无监督或半监督方法。其主要目的是通过探索图的拓扑结构来发现节点之间的高阶相似度,并将这些相似的节点归为同一个社团。在社团中,成员之间联系紧密,而不同社团成员之间的联系较少。这种方法可以用于电子商务中的用户购物推荐和广告,生物信息学中蛋白质和蛋白质之间的相互作用预测,引文分析中的文献推荐或学者合作等众多应用。为了探索复杂网络下更加有效的社团检测,本研究针对以下问题展开:(1)对大型复杂网络进行高质量的社团检测通常依赖图的拓扑结构来划分节点集,然而现实世界的网络通常带有嘈杂且与集群无关的链接,这些链接可能会导致模型将来自不同集群的节点划分在一起;(2)大多数基于图神经网络的社团检测模型仍然使用K-means来定位社团中心,并未充分利用图神经网络学习节点表示的优势;论文的主要工作包括:第一,图重构下大规模网络的社团检测算法(graph reconstruction based community detection,GRCD)。该方法能够处理大规模复杂网络的社团检测。首先,删除社团之间的相互连接的边来重新构建原始图的社团结构。然后,GRCD将网络视为一个社交系统,旨在以更直观的方式揭示社团;提出了一种高效的社团检测策略:基于话语权的社团组织生成策略。最后,在不同规模数据集上进行实验,实验结果表明,GRCD算法不仅能够处理大规模网络,而且在保持较高稳定性的同时,其社团划分的质量对比现有的几种基准算法都有很强的竞争力。第二,联合图的全局和局部互信息的重叠社团检测(Overlapping Community Detection Algorithm using Global and Local Mutual Information of Graph,over DGI)。这是一种用于处理重叠社团检测问题的图神经网络。首先,采用最大化图互信息使得节点向量表示更能精确表达图结构信息。然后,在利用图结构来定位社团中心的基础上,通过最大化社团互信息使得隶属于同一社团的节点的向量表示与该社团的核心节点的向量表示距离更近。最后,设计了一个目标分布来帮助模型更好的解决重叠社团检测任务。通过综合实验表明,over DGI在重叠社团划分上的表现对比现有的几种基准算法都有很强的竞争力。本文的主要目标是探讨如何利用核心节点来提高社团检测的效果。在GRCD中,通过基于话语权的社区组织策略,重点利用核心节点来提高社团检测的准确性。在over DGI中,通过最大化社团互信息使得隶属于同一社团的节点的向量表示与该社团的核心节点的向量表示距离更近。这两种方法均表现出良好的性能,为网络中的社团结构挖掘提供了新的视角。

关键词： 深度学习   复杂网络   图神经网络   社团检测  

摘要： 近年来,随着信息技术的不断发展与算力的大幅提升,深度学习已经渗透至人们生活的各个方面。深度学习中的图神经网络方法在处理社交网络、交通网络等以图为结构的数据时表现出色,受到了众多学者的关注。由于真实世界的数据普遍存在数据稀疏、标签缺失等问题,且图数据中节点多以重叠的社团结构聚集,本文以图卷积神经网络为主题,分别探讨了如何提高图卷积神经网络的自适应挖掘隐藏特征与拓扑信息能力,以及自适应图卷积神经网络在重叠社团检测方面的应用。本文从解决数据稀疏、挖掘数据潜在特征信息与拓扑关系入手,提出了一种基于自适应特征与拓扑的图卷积神经网络模型AAGCN。该模型通过设置自适应层对数据进行预处理,将挖掘到的隐藏特征和拓扑信息,与原数据的特征信息和拓扑结构进行融合,一并送入到卷积层进行训练,从而提高图卷积神经网络的模型表达能力。通过真实数据集上的节点分类实验,验证了AAGCN模型自适应层的有效性。真实世界的图数据如社交网络、引文网络中往往具有大量的重叠社团结构,挖掘重叠社团可以帮助对图数据更好地进行分析。然而,现有的重叠社团检测方法普遍存在检测效果不佳、无法处理大规模网络等问题。为此,本文提出了一种基于自适应图卷积神经网络的重叠社团检测模型AAOCD。该模型利用AAGCN模型挖掘隐藏节点特征与拓扑信息的能力,生成并优化节点-社团隶属矩阵,从而实现端到端的重叠社团检测。实验表明,AAOCD模型在重叠社团检测方面取得了良好的检测效果。图17幅,表11个,参考文献86篇