基于核心节点扩散的有向网络重叠社团发现算法

复杂网络中的社团结构探测是当前复杂网络研究领域的一个热点问题。传统的社团划分算法主要以无向、无权网络作为分析对象,不能够适用于现实世界中各种有向网络、加权网络。在分析和研究各种社团划分算法的基础上,提出一种新的重叠社团发现算法。该算法从网络中的核心节点开始,不断合并适应度最大邻居节点,最终将网络划分为多个重叠的社团。最后,将该算法应用到两个有向网络中,实验表明该算法能够很好地划分出有向网络中的重叠社团。     

基于链路标签传播的重叠社团发现算法

为挖掘复杂网络中的重叠社团结构,在标签传播算法的基础上,从链路的角度出发,提出一种新的标签更新策略。考虑不同邻居对链路标签贡献值的不同特点,使其更新过程更加快速,克服当前基于节点的标签传播算法需要指定节点所属社团个数的缺陷,在无需人工干预的情况下得到稳定的重叠社团结构。将该算法分别应用于人工网络和真实的社会网络中,实验结果表明,该算法能够快速、有效地挖掘稳定的重叠社团结构。     

基于LeaderRank和节点相似性的多标签传播重叠社团挖掘算法

针对基于多标签传播重叠社团挖掘算法COPRA因随机更新策略带来的不稳定性以及需要预先输入参数的局限性等问题,提出一种基于LeaderRank和节点相似性的多标签传播重叠社团挖掘算法.该算法首先利用LeaderRank算法对网络中的节点进行重要性排序从而确定节点的更新顺序,减少标签不必要的更新.在标签传播过程中,根据节点相似性重新设计标签的更新策略,提高算法的稳定性.将算法应用于人工网络和真实网络中进行实验,实验结果表明该算法在挖掘重叠社团上具有较高的准确性和稳定性.     

联合图的全局和局部互信息的重叠社团检测算法

图神经网络在学习节点表示中展现了其突出的能力,然而在社团检测方面,大多数图神经网络模型仍然使用K-means来定位社团中心,为了克服K-means不适用于高维空间下聚类的缺点,提出了联合图的全局和局部互信息的重叠社团检测算法（overlapping community detection algorithm using global and local mutual information of graph,overDGI）,这是一种用于处理重叠社团检测问题的图神经网络。首先,采用最大化图互信息和社团互信息使得隶属于同一社团的节点间的向量表示距离更近、更接近社团中心;然后,设计了一个目标分布来帮助模型更好地解决重叠社团检测任务。综合实验表明,overDGI在重叠社团划分上的表现对比现有的几种基准算法都有很强的竞争力。     

完全子图的邻域重叠社团结构探测

为了能够更准确地对邻域重叠网络进行社团结构探测,对基于完全子图的社团探测算法进行了改进。在合并完全子图团簇时,计算每一对完全子图的重叠节点个数,设置合并完全子图的阈值,如果大于阈值,则合并。当处理不在团簇内的其他节点时,按照比例系数大小为划分规则进行划分。该算法可以应用于空手道俱乐部和科学家合作网当中,其验证算法可以更准确地探测邻域重叠社团结构。     

基于相似性复杂网络社团结构发掘算法的研究

复杂网络的社团结构对于研究现实世界有着重要意义。然而,现在的一些算法存在着划分精度不够,限制条件较多等不足,影响了复杂网络的应用。所以,本文提出了一种基于相似性复杂网络社团有效划分算法。文中,利用相似性,灵活定制阈值,将层次聚类思想应用到网络社团发掘过程中。并且,在不同的层次上设定了相应阈值,保证了精度,实现网络社团的初步划分。为获得更加清晰的结构,提出了重叠节点的相似性指标。结果,本文不仅发现了网络的层次社团结构,还挖掘出重叠节点。最后,实验表明本算法提高了复杂网络社团划分的精度。     

基于三支决策的非重叠社团划分

基于三支决策理论,提出了一种基于三支决策的非重叠社团划分算法（N-TWD）,该方法将初始聚类形成的重叠社团进行二次划分以形成最终的非重叠社团。N-TWD算法首先利用层次聚类形成有重叠的社团结构,将两个存在重叠的社团的左边社团中非重叠部分定义为正域,右边社团中非重叠部分定义为负域,而两个社团的重叠部分定义为边界域。然后,针对边界域中的节点,分别计算边界域中节点与正域和负域的社团归属度B_P、B_N进行二次划分。对于二次划分后仍然留在边界域中的节点将利用投票的方法决定其最终归属,最终获得非重叠的社团结构。本文选取4个经典社交网络数据集和1个真实世界数据集对N-TWD算法进行了验证,相比较其他社团划分算法（GN、NFA、LPA、CACDA）,N-TWD时间复杂度较低,总体获取的社团模块度值更高。     

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

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

基于核心边的局部贪婪扩展与重叠性家庭群体识别

为了支撑电信运营商面向家庭群体的精确营销活动,解决在赋权的超大规模复杂网络中进行重叠性社团发现的难题,提出了基于核心边的局部贪婪扩展（CEBLGE）算法,以核心边作为初始社团种子,基于赋权的适应度函数进行两阶段扩展。算法中防止了畸形扩展,定义了边权相似度、赋权重叠模块性,优化了对过度相似社团的评价和处理方法,从而提升了重叠社团划分的质量。然后基于中国移动的电信大数据,利用逻辑回归算法构建了手机用户间的家庭成员关系模型,基于CEBLGE算法进行了家庭群体识别,并通过测试样本数据和实际营销活动检验了上述模型和算法的有效性。     

优化稳定性的多层次社团快速探测算法

由于现有的社团探测算法大多只能在单一的尺度上划分社团,而且运算速度比较差,因此不利于分析大规模的科技社会网络.本文提出一种新颖的多尺度社团结构快速探测算法.该方法通过优化表示社团结构统计显著性的稳定性指标函数,来寻找多个层次上具有最佳统计意义的社团结构.为了得到具体的社团归属,开发了一种只需利用马尔科夫迭代就能更新归属向量的动力学系统,使得社团归属便能够快速地收敛到最优值,因此具有较低的计算复杂性.它不需要指定具体的社团数量,便能够找到每个节点与具体社团的归属关系,因此能够自然地支持重叠社团的划分.理论分析和实验验证共同表明,该算法可以快速而准确的发现社会网络和生物网络中的各种功能社团.     

基于圈结构的LPANNI优化算法

针对重叠社区发现准确率提升问题,提出了一种基于圈结构的LPANNI优化算法CLPANNI（cycle label propagation algorithm with neighbor node influence）。该算法通过挖掘节点的最小圈信息,依据圈比指标衡量节点的重要性并按升序进行标签更新,增加了标签传播过程的稳定性,按照邻居节点影响力大小加权接收邻居节点传递的标签。与四种基准算法在NMI_LFK、NMI_MGH、MOV指标下进行测试比较,CLPANNI算法在社区发现准确率方面表现较好。实验结果表明,该算法能够有效探测网络重叠社团结构,发现网络的紧密子团,识别的社团分布与真实网络结构更为接近。     

一种重叠可信社团划分算法的设计与实现

本文首先总结了社会网络中可信社团的特征,确定了可信社团的概念,并给出了可信社团的定量化定义。然后借鉴已有的无向网络上的重叠社团划分算法思想,设计并实现了一种有向网络上的重叠社团的划分算法,并在此基础上设计和实现了可信社团的划分算法。最后在典型的含有重叠社团的网络上和真实的可信社会网络上验证了两个算法的有效性。     

复杂网络中的邻域重叠社团结构探测

网络,数学家们称其为图,它为许多复杂系统的结构提供了一个很好的抽象,从社会网络、计算机网络,到生物网络以及物理系统的状态空间。在过去的几十年里出现了许多确定网络系统拓扑结构的改进实验,但对实验产生的数据进行科学的分析,仍然存在本质的挑战。目前的社团检测中主要存在两个问题:一是不知道网络中有几个社团;二是网络中的顶点可能属于不同的社团,也就是社团中存在重叠结构。为了了解各种重叠社团检测算法的思想、实现步骤、优缺点比较、算法应用,文中对邻域重叠社团检测算法进行了深入的分析,以k-means算法分析了经济网络,同时采用Silhouette指标解决了最佳聚类数的问题,并通过仿真实验证明了此算法的可能性。     

利用改进蚁群算法的重叠社团检测分析方法

针对重叠社团检测准确率提升问题,提出了一种基于改进蚁群算法的新型重叠社团检测算法。该算法包含位置初始化、运动和后处理三个阶段,分别通过初始位置识别与标签列表存储、基于节点间相似度的启发式信息重定义、合作保持标签列表等方式,使算法在合成数据集与现实世界数据集中的重叠社团与节点检测方面具有更好的性能。实验结果表明,在合成网络与现实世界网络平台上使用不同检测算法,所提出的方法对重叠社团与重叠节点的检测准确率较传统检测方法来说更高,因而对重叠社区检测问题求解与理解网络功能结构具有重要的参考与借鉴意义。     

基于边图的重叠社团检测研究

社团检测吸引了大量的研究,在真实网络中,社团的层次性和重叠性交织在一起,然而到目前为止大部分工作只研究网络的层次性或重叠性。 2010年Ahn在Nature上发表的文章证明层次性和重叠性是网络相同现象的两个方面,针对社团检测在Ahn的方法的基础上提出了新算法：边图谱分析,将谱分析方法应用到边社团发现上,进行了兼顾层次性和重叠性的社团检测研究,实验中使用两个真实网络来对比边图谱分析算法、Ahn的算法和派系过滤算法,实验结果表明本文提出的边图谱分析算法实现了网络的重叠社团检测并且社团划分结果比较满意。     

复杂网络中基于WCC的并行可扩展社团挖掘算法

WCC(Weighted Community Clustering)通过复杂网络中社团含有的三角数量来评价社团挖掘算法的性能。在原始的WCC算法中,需要在每次迭代中对所有的社团变化计算WCC值,因而计算量非常大。为了减小社团变化带来的WCC计算量,提出一种并行可扩展的社团挖掘算法。对应用WCC进行社团评价的方法进行分析,提出一种包含预处理、初始划分和划分改进三个阶段的并行社团挖掘算法。在划分改进中,由于每次社团变化都需要计算大量的WCC提升,基于社团的统计量提出一种WCC近似计算方法。大量的真实数据集实验表明,提出的社团挖掘算法与相关算法相比较,不仅社团检测的准确性更高,而且具有更好的并行可扩展性。     

基于潜在特征的重叠社团识别算法

针对标签空间的指数增长这一问题,提出了一种基于潜在特征的重叠社团识别算法。首先,提出了一种包含重叠社团的网络产生式模型。根据该产生式模型,通过最大化目标网络的产生概率来推导网络中节点的潜在特征,并给出了优化目标函数。然后,通过将网络诱导为二部图,分析得出了潜在特征个数的下届,并据此对标签空间进行优化。实验表明,提出的重叠社团识别算法与BigClam算法相比较,在保持运行效率和查准率基本不变的前提下,可以明显提高检索结果的召回率。该算法可以有效地应对社团识别中标签空间的指数增长。     

基于节点相似性的加权复杂网络BGLL社团检测方法

针对加权复杂网络中的重叠社团检测问题,提出了一种面向加权网络的基于Jaccard系数的BGLL模块密度优化算法（Modularity Density and Jaccard Based BGLL,DBGLLJ）.利用节点重要度重构网络,根据模块度增益作为阶段函数和模块密度增益作为目标函数进行网络硬划分,并提出了结合改进的Jaccard系数的重叠检测方法.为验证算法,选择了3种算法在LFR网络和真实网络中进行测试,结果表明：在标准LFR网络和真实网络中,DBGLLJ算法检测效果较优,具有较高的重叠模块度以及重叠检测准确性,且运算效率较好.将所提算法应用于现实复杂机电系统因效性网络,重叠检测结果较好,具有较高的参考价值.     

基于引力因子的加权网络重叠社区识别算法

通过挖掘大数据来识别复杂社会网络上的社区,有利于对经济、政治、人口等方面的重要问题进行定量研究,社区的识别算法已经成为当前研究的热点问题。重点研究了重叠社区识别问题,提出了基于引力因子的加权复杂网络的重叠社区识别算法GWCR。该算法首先选取万有引力因子大的节点为中心节点,将节点与中心节点之间的引力因子作为衡量标准,并将节点归入社区引力因子大于某一阈值的社区,最后通过识别重叠节点来识别重叠社区。在3个真实网络数据集上的实验结果表明,与传统的重叠社区识别算法相比,GWCR算法划分的社区的模块度较高。     

基于主题划分和链接划分的社团发现算法

传统的社团发现算法利用链接关系对社团进行划分,不利于发现社团之间的非链接关系,从而影响划分精度。研究分析了节点蕴含的文本信息,挖掘了文本信息蕴含了节点的主题信息,根据这些主题信息判断社团在主题上的关系。研究设计了优化的潜在狄利克雷分配模型对社团进行主题划分,应用优化的模块度社团发现算法对社团进行链接划分,合并成为一个能对社团进行主题划分和链接划分的主题社团发现算法。此外,还针对主题社团设计了一种评估方法,并且使用多个数据集在主题社团发现的各个阶段对算法进行了实验验证。实验结果证明,基于主题检测的社团发现算法能够正确地对社团进行主题划分和链接划分。