一种基于信息扩散的复杂网络重叠社区发现算法

社区结构可以为网络的其他分析挖掘提供中观尺度的分析视角,在大规模复杂网络的各项研究中是一项非常重要而基础的工作。社区的重叠是真实世界网络中常见的一种现象,重叠社区结构可以更准确地描述网络中真实的结构信息,因此,复杂网络重叠社区发现具有更加突出的现实意义。在综合对比分析了当前主要的重叠社区发现算法的基础上,结合信息论的相关知识,给出了一种基于信息论的社区定义,并进一步借鉴信息传播理论,从单个节点对关于某种主题的信息的掌握程度的角度出发提出了一种复杂网络重叠社区结构发现算法。基于实际数据集的相关实验表明,与传统的社区定义和社区发现算法相比,本算法发现的重叠社区从内容角度来看具有更加明确的实际意义,并且具有较低的时间复杂度。     

图神经网络社区发现研究综述

社区结构是复杂网络中普遍存在的拓扑特性之一,发现社区结构是复杂网络分析的基本任务.社区发现旨在将网络划分为多个子结构,对于理解网络、揭示网络的潜在功能有着重要作用.图神经网络是一种处理图结构数据的模型,具有从图中对数据进行特征提取和表示的优势,已经成为人工智能和大数据领域的重要研究方向.网络数据就是典型的图结构数据,使用图神经网络模型解决社区发现问题,是社区发现研究的一个新方向.首先对GNN模型进行深入探讨,分析GNN社区发现过程,并从重叠社区和非重叠社区这两个方面详细讨论现有GNN社区发现取得的进展以及未来可研究的方向.     

结合拓扑势与信任度调整的重叠社区发现算法

现实世界中的复杂系统可建模为复杂网络,探究复杂网络中的社区发现算法对于分析复杂网络的拓扑结构和层次结构具有重要作用。早期研究通常将网络中的节点局限在一个社区中,但随着研究的深入发现社区结构呈现重叠特性。针对现有重叠社区发现算法存在划分社区结构不稳定、忽略节点交互和属性等问题,提出一种基于网络拓扑势与信任度调整的重叠社区发现算法。融合节点的属性和结构特征计算节点的拓扑势,依据节点的拓扑势选取核心节点。从核心节点出发构建初始社区群,计算各个社区间的调整信任度,实现社区的合并与再调整,从而识别重叠社区。在多个人工模拟网络和真实网络数据集上的实验结果表明,与基于贪婪派系扩张、种子扩张等的重叠社区发现算法相比,该算法将扩展模块度最高提升至0.719,能有效识别社区结构及重叠节点,提升重叠社区检测性能。     

基于三角形的重叠社团发现算法

社区结构是复杂网络的重要属性之一, 有效挖掘出复杂网络中隐藏的社区结构具有重要的理论研究意义和广泛的应用前景。真实网络在一定程度上都表现为重叠的社区结构, 针对这一问题, 提出了一种基于三角形的重叠社区发现算法。通过判断两个节点与其共享邻居节点能否构成一个三角形来判断, 若能构成三角形, 则这两个节点属于同一社区。在计算机生成网络与真实网络上进行了实验, 都正确地识别出了社区结构以及重叠节点, 表明了此算法对于发现重叠社区结构的有效性和可行性。     

重叠社区发现算法评价指标综述

重叠社区发现算法对于理解复杂系统、发现复杂网络中隐藏的规律等具有很强的应用价值,而评价指标是算法发现高质量重叠社区的一个关键要素,算法的进步常常依赖于评价指标的进步。现有研究对非重叠社区发现算法的评价指标有较多的总结,而没有对重叠社区发现算法的评价指标进行总结。对重叠社区发现算法的评价指标进行了系统的总结和回顾,将指标分为事先知道社区结构、事先不知道社区结构和其它三大类。事先知道社区结构的评价指标包括基于混淆矩阵、基于ARI、基于NMI三个子类评价指标,事先不知道社区结构的评价指标包括基于模块度、基于密度、基于元数据三个子类评价指标,其它类主要介绍算法可扩展性评价指标。深入理解各种评价指标对于开发和优化重叠社区发现算法、在实际应用中发现高质量社区具有重要价值。     

基于边图的线性流重叠社区发现算法

重叠网络的社区发现是复杂网络研究中的重要问题。为了提高网络中重叠社区发现的时间效率，提出一种基于边图的线性流重叠社区发现算法LBSA。算法首先对于边图网络中的边进行随机的依次处理，完成节点的初步社区划分，再将其中重叠小社区合并到相似度最大的其他大社区中得到最终的社区。通过以上步骤，算法能够以接近线性的时间复杂度得到网络的重叠结构。从最终的实验结果来看，与其他算法相比，该算法能够在更短的时间有质量地发现网络中的重叠社区。     

用于网络重叠社区发现的粗糙谱聚类算法

针对绝大多数社区发现算法都存在着网络节点仅隶属于一个社区的假设,引入谱图理论与粗糙集理论来分析复杂网络社区,提出一种用于网络重叠社区发现的粗糙谱聚类算法RSC,该算法用上下近似来刻画网络节点的社区归属,边界表示社区之间共享的节点,通过优化重叠社区结构模块度来实现重叠社区发现.通过3个不同类型真实网络的仿真实验,结果验证了该方法的可行性与有效性.     

一种基于粗糙集和密度峰值的重叠社区发现方法

随着互联网和社会的发展,各个领域每天都会产生大量相互关联、彼此依赖的数据,这些数据根据不同的主题形成了各种复杂网络。挖掘社区结构是复杂网络领域中的一项重要研究内容,因为其在推荐系统、行为预测和信息传播等方面具有极其重要的意义。社区结构中的重叠社区结构在生活中普遍存在,更具有实际研究意义。为有效发现复杂网络中的重叠社区,文中引入了粗糙集理论对社区进行分析,识别出重叠节点,进而提出了一种基于粗糙集和密度峰值的重叠社区发现方法OCDRD(Overlapping Community Detection Algorithm Based on Rough Sets and Density Peaks)。该方法在传统网络节点局部相似性度量的基础上,结合灰色关联分析方法求出网络节点间的全局相似性,进而将其转化为节点间距离。将密度峰值聚类算法的思想应用于该算法中,以根据网络结构自动选取社区中心节点。依据网络中节点的距离比例关系,定义了社区的上近似、下近似以及边界域。最后,不断调整距离比率阈值并进行划分迭代,在每次迭代中针对社区的边界域进行计算,从而获得最佳重叠社区划分结构。在LFR基准人工网络数据集和真实网络数据集上,基于标准互信息(Normalized Mutual Information,NMI)和具有重叠性模块度EQ这两个评价指标,将OCDRD方法与近几年效果较好的其他社区发现算法进行测试比较。实验结果显示,OCDRD方法在社区划分结构方面整体优于其他社区发现算法,表明了该算法的可行性和有效性。     

具有对偶约束的半监督重叠社区发现方法

在复杂网络重叠社区发现方法的研究中,提高算法准确度的方法之一是利用额外的背景信息（例如来自领域专家的）作为约束的来源来指导社区检测过程。本文研究探索半监督策略的潜力,用以改善在网络中寻找重叠的社区的准确性。在进程的初始化阶段和子社区扩展过程中引入必须链接和不可能链接的约束,提出一种使用有限数量的成对约束、结合贪心策略来寻找重叠社区的方法PC-GCE(Pairwise Constrained Greedy Clique Expansion)。对模拟网络数据与当前无约束的局部扩展重叠社区发现算法（GCE）进行对比实验,结果表明PC-GCE方法在发现重叠社区的性能上优于无约束的算法,并且随着成对约束数量的增加,发现重叠社区的性能越好。     

一种基于局部扩展优化的重叠社区发现算法

挖掘复杂网络的重叠社区结构对研究复杂系统具有重要的理论和实践意义。提出一种基于局部扩展优化的重叠社区识别算法。 首先基于网络节点的聚集系数筛选种子节点,选取不相关的、局部聚集系数大的种子作为初始社区;然后采用贪心策略扩展初始社区,得到局部连接紧密的自然社区;最后检测并合并相似的社区,获得高覆盖率的重叠社区结构。在人工生成网络和真实网络数据集上的实验结果表明,与现有的基于局部扩展的代表性重叠社区发现算法相比,所提算法能在稀疏程度不同的网络上发现更高质量的重叠社区。     

复杂网络中的社团发现算法综述

社团发现方法能够用来挖掘网络中隐藏的聚簇结构信息,对复杂网络结构与功能的分析具有重要意义.近些年来,随着网络数据的爆炸式增长,网络演化的多样性,涌现出了大量能够处理不同场景的社团发现方法和框架.为了深入了解社团发现领域的研究现状和发展趋势,对复杂网络中的社团发现算法进行综述.首先,对这些算法进行了分类;其次,详细介绍了每一类算法,并进行了分析和对比;之后,介绍了一些常用的评价指标,并阐述了社团发现的应用场景;最后,对该领域未来研究方向进行了展望.     

一种基于聚集系数的社区发现算法

社区划分一直是复杂网络研究中的一个热门话题,社区的快速准确划分为研究复杂网络的性质提供了良好的基础。传统的社区发现方法都是在全局复杂网络的基础上进行社区划分,随着网络中节点的增加,网络规模的变大,社区发现变得更为复杂。提出了一种局部社区发现算法,该算法无需知道整个复杂网络的全部信息,只需从一个待求节点出发,考察其与邻接节点的紧密程度,逐步将邻接点添加到社区中,得到该节点所在的社区结构。同时,该算法还可实现全局网络的社区发现。利用该算法分别对Zachary空手道俱乐部网络和海豚社会网络进行社区发现,实验结果表明了该算法的准确性与可行性。     

动态社区发现方法研究综述

随着社交媒体多样性的增加,实时分析社交网络的需求不断增大,动态社区发现的研究受到了广泛的关注。已有的社区发现综述多是侧重静态社区发现,以及相关方法的探讨,无法进行网络演化分析,此外社区的实体数据往往具有交叉更替性和时序性,因此对动态社区发现的研究现状进行分析和综述。首先,基于复杂网络的研究背景,提出了通用的动态社区发现研究框架;接着,形式化表示动态社区发现的相关定义,并从网络层面和节点层面对动态社区演化进行详细分析;然后,根据架构和技术的不同,对动态社区发现方法进行归纳分类,并结合常用数据集和评价指标对经典静态社区发现算法进行定性和定量分析;最后,介绍了社区发现的典型应用场景,探讨了当前动态社区发现研究面临的主要挑战,针对性地提出了相关解决方案,为动态社区发现研究领域勾画出较为清晰和全面的研究方向。     

社区挖掘技术研究

复杂网络分析已成为近年来的一个热点研究领域。如何快速有效地对复杂网络进行社区划分,并在社区划分的基础上找出网络中的重要节点有很强的现实意义。本文分析比较了近年来复杂网络分析中社区结构挖掘算法和社区节点等级排序算法的原理和特征,最后对复杂网络分析的发展进行了总结和展望。     

复杂网络重叠社团检测算法研究综述

社团结构是复杂网络的一项基本特性,对复杂网络中社团结构特别是重叠社团结构的检测,是复杂网络理论研究的一项重要且充满挑战的课题.对当前常用的重叠社团检测算法进行了分析和归纳,阐述每类算法特点,并介绍用于评价算法性能的一些基准图,对复杂网络重叠社团检测领域未来的研究方向提出了一些思考和建议.     

复合加权股票网络的活跃性层次聚类

当前社团分析方法没有充分利用复杂系统的内在特性,难以准确和有效地发现复杂加权网络群体之间的相关性。基于股票网络的活跃性,提出了一种基于活跃性的复合加权股票网络的层次社团划分算法。该算法对股票活跃性进行了定义,提出了一种复合加权模型以有效表示股票网络的活跃性,进而为了实现复合加权网络的社团划分,给出了群体相异度的评判标准。该算法以股票价格波动的相关性为边建立复合加权股票网络,以股票的换手率和成交量为评价标准,选出活跃性高的股票,进而以活跃性股票为中心,基于股票间的相异度权重标价准则,提取多个高活跃的局部结构,可以有效避免层次划分算法由于初始社团结构质量不高,导致社区结构不能沿正确方向继续进行层次发现的问题。最后,基于高活跃的局部结构性,利用全局优化模块度的方法对复合加权网络进行社团划分。将CNM算法（Newman贪婪算法）与BGLL算法运用于构建的网络中,结果表明了算法的优越性。     

基于信息瓶颈的社区发现

该文提出一种映射方法,把单部网络变换成二部图网络.针对得到的二部图网络,在信息论的框架下,提出了一种基于信息瓶颈的社区发现方法.该方法通过寻找网络的最优压缩表示来发现网络的社区结构,最优压缩表示尽可能多地保留原始网络的拓扑特征.在真实数据集和计算机产生的数据集上的实验表明,该方法能够有效地发现网络的社区结构.另外,对于有向网络的社区发现,现有方法忽略有向网络中边的方向而作为无向网络来处理,损失了有向的网络的方向信息,文中提出的社区发现方法能够很好地解决这一问题,并能从有向网络中挖掘出一些现有方法无法发现的知识,这一特点使得该文的方法比现有方法更适用于解决像WWW这样的有向网络.同时,真实世界的许多网络本身就是二部图网络,相对于现有的社区发现方法,文中的方法可以直接应用于这类网络.     

复杂网络社区发现研究进展

近年来,随着现代网络通信和社会媒体等技术的飞速发展,复杂网络成为多学科交叉研究的热点之一,社区发现是复杂网络中的一个重要问题,对其进行研究具有重要的理论意义和应用价值。该问题吸引了多个学科领域的众多学者的关注,并且已有许多社区发现算法被提出。已有的社区发现综述多是侧重某一方向或特定领域展开,基于此,文中在之前工作的基础上,对国内外社区发现工作进行了深入调研,较全面地阐述了复杂网络社区发现的研究现状。首先,针对不同网络结构,给出社区发现的问题定义和主要的评价指标。然后,介绍了不同网络结构中的经典社区发现算法,包括同质网络中的全局社区发现、局部社区发现算法,异质网络中的二分网络、三分网络和多分网络中的社区发现,结合节点内容和连接结构的社区发现算法,以及动态网络中的社区发现和社区演化工作。最后,简要介绍了社区发现的典型应用,包括影响最大化、链路预测和情感分析领域的应用。此外,探讨了当前社区发现研究面临的主要挑战,试图为社区发现研究领域勾画一个较为清晰和全面的轮廓,为初学者提供指引。     

基于联合矩阵分解的动态异质网络社区发现方法

动态网络的社区发现是目前复杂网络分析领域的重要研究内容,然而现有动态网络社区发现方法主要针对同质网络,当网络包含多种异质信息时,现有方法不再适用。针对这个问题,本文提出了一个基于联合矩阵分解的动态异质网络社区发现方法,首先计算动态异质网路中各个快照图的拓扑相似度矩阵和多关系相似度矩阵,其次利用时序联合非负矩阵分解方法,约束各个时刻快照图的社区划分,最后在真实网络数据集上的实验结果表明,该算法可以有效检测出动态异质网络中潜在的社区结构。     

基于标签传递的有向图重叠社团发现算法研究

社团发现作为网络科学中一个重要的基础问题受到了广泛的关注和重视.针对社团结构的研究为我们提供了从中尺度上分析和理解网络的途径,具有重要的理论和实际意义.已有的研究大多关注无向图和非重叠社团的发现.本文基于标签传递和用户排序的思想设计了一个有向图上的重叠社团发现算法,实际数据上的实验表明了算法在发现用户多重社团属性和确定社团规模方面的有效性.