基于节点相似度的网络社团检测算法研究

社团结构是众多复杂网络的统计特性之一,挖掘网络中存在的社团结构日益受到人们的普遍关注。网络中的社团结构检测本质上类似于传统机器学习领域的聚类分析,其关键问题在于如何定义网络中节点间的相似度。首先提出了基于节点相似度的节点分裂算法SUN,相比传统的基于边界数(betweenness)的节点分裂算法GN, SGN在速度和精度上都有明显改善;接着,在利用各种节点相似度计算方法得到节点间的相似度之后,采用几种经典的聚类分析算法对网络进行社团划分,在模拟数据和真实数据上的实验表明:基于网络拓扑结构信息的signal和regular方法优于基于网络节点局部信息的Jaccard方法,而且对于复杂网络社团划分问题,如果选择好的网络节点相似度构造方法,已有的基于相似度矩阵的聚类分析算法都能快速有效地对网络社团进行划分。     

基于节点相似度的加权网络社团结构划分算法

针对加权网络的社团结构划分问题,提出了一种基于节点相似度的划分算法.构造一种新型加权网络的节点相似度矩阵,基于该相似度矩阵,随机选取一个节点作为初始社团,搜索与该节点相似度值最大的节点合并成一个新的社团.反复迭代,形成划分.该算法具有较低的计算复杂度.用经典复杂网络的社团划分算例验证了该算法的有效性.     

一种基于聚集系数的局部社团划分算法

社团划分算法是复杂网络研究中的一个热点问题.传统的复杂网络社团划分算法都必须获得全局网络的信息.随着网络规模不断增大,获得全局信息的难度随之增加;而在很多情况下只关心网络中某节点所在的局部社团.为了准确、快速地找到大规模复杂网络中的局部社团,提出了一种基于节点聚集系数性质的局部社团划分算法.该算法根据节点的连接频度,利用节点聚集系数的性质,从网络中某一待求节点开始,通过搜索邻居节点,划分该节点的社团结构.该算法只需要了解与待求节点相关的局部网络信息,在解决局部社团划分问题时其时间复杂度比传统的社团划分算法低.同时,该算法也可以应用于复杂网络全局社团结构的划分.利用该算法分别对Zachary空手道俱乐部网络和由Java开发工具包构成的软件网络图进行社团划分实验,并且分别对实验结果与对象网络的具体特征进行了对比分析.     

基于节点内聚系数的局部社团发现算法

为了能够快速有效地发现复杂网络中的局部社团,提出一种基于节点内聚系数的局部社团发现算法。该算法选取最大度节点作为起始社团,不断搜索其邻居节点,将满足条件的节点不断加入起始社团从而形成新的社团。在不同规模的真实网络数据集和人工合成数据集上进行实验,并与其他三种局部社团发现算法进行社团划分效果的对比。实验结果表明,该算法能够在较短的运行时间内保持较高模块度来识别复杂网络中的局部社团结构,更适合于大规模复杂网络的社团结构挖掘。     

基于节点向量表达的复杂网络社团划分算法

社团结构划分对复杂网络研究在理论和实践上都非常重要.借鉴分布式词向量理论,提出一种基于节点向量表达的复杂网络社团划分方法（CDNEV）.为了构建网络节点的分布式向量,提出启发式随机游走模型.利用节点启发式随机游走得到的节点序列作为上下文,采用SkipGram模型学习节点的分布式向量.选择局部度中心节点作为K-Means算法的聚类中心点,然后用K-Means算法进行聚类,最终得到社团结构.在真实和模拟两种网络上做了丰富的实验,与主流的全局社团划分算法和局部社团划分算法作了比较.在真实网络上CDNEV算法的F1指标比其他算法平均提高19%;在模拟网络上,F1指标则可以提高15%.实验结果表明,相对其他算法,CDNEV算法的精度和效率都较高.     

复杂网络局部社区挖掘的节点接近度算法

为了准确、快速地发现大规模复杂网络中的局部社区,提出了一种基于节点接近度的局部社区发现算法。该算法以最大度节点作为起始节点,利用节点接近度和局部社区Q值不断搜索其邻居节点,将接近度最大的节点加入初始社区形成新的初始社区;同时,该算法也可以应用于复杂网络全局社区结构的划分。对2个典型复杂网络进行了局部社区挖掘分析,实验结果表明,该算法能够有效识别隐藏在实验网络中的局部社区。针对稀疏网络,该算法的时间复杂度为O（nlog（n））,n为网络节点数。     

一种基于节点相似性的局部社团划分算法

提出一种基于节点相似性的社团挖掘算法,算法首先根据节点的相似度值找出最相似邻居节点,合并节点形成若干个社团,然后优化模块度函数进行社团的合并,当模块度值最大时算法终止。最后,通过Zachary网络和Dolphin网络进行实验仿真,验证了算法的可行性和精准性。     

一种基于相对关系亲密度的局部社团发现算法

在复杂网络研究中,社会网络中的社团发现,对商业营销、疾病传播控制等具有实际意义.目前许多研究针对于全局网络进行社团挖掘.挖掘算法因其较高的复杂度往往不适用于动态、大型网络.针对某个点或者某个区域的局部社团挖掘成为了近期的研究热点.为此提出了一种新的相对关系亲密度的计算方法,并与已有算法思想结合,形成了一种新的局部社团发现算法,提高了算法性能.基于已知社会网络、随机测试网络的实验证明了算法的有效性.     

一种基于节点相异度的社团层次划分算法

当前层次划分社团算法难以选取合适的初始节点,导致社团结构划分结果较差。为此,提出一种基于节点相异度的层次社团划分算法。给出度和接近度的评估标准,根据评估标准筛选网络的初始核心节点。为克服相异性指数在度量社团内节点相似度时的不足,引入节点的相异度评价准则,计算初始核心节点间的相似度,得到具有较高相似度的初始节点集。采用全局优化模块度的策略,从而实现对复杂网络的社团划分。应用于标准数据集的实验结果表明,与GN算法、FN算法相比,该算法划分效果更好,时间复杂度更低。     

基于局部信息检测的多粒度社团挖掘方法

从复杂性和动态性特征出发,给出了复杂网络局部模块度的定义,并提出了基于局部信息检测的社团发现算法,认为局部模块度值最大的节点集合就是最理想的社团结构.在此基础上提出了多粒度社团挖掘方法,为多视图观察复杂网络结构特征提供了新的研究思路.最后的实验分析表明了方法的有效性和可行性.     

Local community detection algorithm based on local modularity density

Compared to global community detection, local community detection aims to find communities that contain a given node. Therefore, it can be regarded as a specific and personalized community detection task. Local community detection algorithms based on modularity are widely studied and applied because of their concise strategies and prominent effects. However, they also face challenges, such as sensitivity to seed node selection and unstable communities. In this paper, a local community detection algorithm based on local modularity density is proposed. The algorithm divides the formation process of local communities into a core area detection stage and a local community extension stage according to community tightness based on the Jaccard coefficient. In the core area detection stage, the modularity density is used to ensure the quality of the communities. In the local community extension stage, the influence of nodes and the similarity between the nodes and the local community are utilized to determine boundary nodes to reduce the sensitivity to seed node selection. Experimental results on real and artificial networks demonstrated that the proposed algorithm can detect local communities with high accuracy and stability.

     

基于中心点的指纹细节结构匹配算法

指纹细节匹配算法是自动指纹识别系统(AFIS)中一项关键的任务,目前存在大量的研 究和算法.依据算法是否依赖中心点,指纹细节点匹配算法可以分为两类:基于中心点的匹配算 法和非中心点匹配算法.大多数非中心点匹配算法都非常耗时,因此不适合在线应用.而基于中 心点方法的效率相对较高,但是这类算法极度依赖于中心点的定位精度.在本文中,提出了一种 全新的基于中心点的指纹细节结构匹配算法,该算法综合了基于中心点匹配算法和非中心点匹 配算法的优点,同时又避免了二者的缺点.首先利用中心点检测算法获得中心点的位置,然后在 中心区域定义了一些局部的结构,同时利用这些局部结构寻找指纹细节的对应点,并通过对应点 和中心点的相对关系来确认这些对应细节点.其次利用这些细节对应点匹配全局的细节信息,最 后,利用匹配细节的全局距离和距离方差来判决最终匹配结果.实验结果表明,算法的匹配效果 非常好,同时匹配效率较高,非常适合在线指纹识别系统的应用.     

基于自适应Memetic算法的多目标复杂网络社区检测

针对提高复杂网络社区检测准确度问题, 提出了一种自适应Memetic算法的多目标社区检测算法。在全局搜索中利用Logistic函数来设置与全局优化相应的交叉概率和变异概率,并将多目标优化问题转化成同时最小优化Kernel K-Means和Ratio Cut这两个目标函数;在局部搜索中利用权重将两个目标函数合并成一个局部优化目标,并采用爬山搜索来寻找个体最优。在虚拟和真实网络实验平台下,与五个基于遗传算法的方法以及Fast Modularity算法相比,结果表明算法能有效提高社区检测准确度,具有更好的寻优效果。     

局部扩展的遗传优化重叠社区发现方法

重叠社区结构是复杂网络的一种重要的特征,提出了一种局部扩展的遗传优化重叠社区发现（LEGAOCD）。借鉴局部扩展的重叠社区发现方法的思想,将少数的核心节点构成模体;同时,利用了三角形模体来判断社区的稳定性度量问题,从而量化社区结构稳定性;然后通过改进的遗传优化算法策略分配它们应归属的社区;最后通过两个评价目标函数得到高质量的重叠社区结构。该算法在数据集上与经典的CPM算法、COPRA算法作比较,实验结果表明,LEGAOCD算法在检测重叠社区结构和重叠节点方面具有较优的性能。     

一种改进的鲸鱼优化算法

针对鲸鱼优化算法（whale optimization algorithm ,WOA）容易陷入局部最优和收敛精度低的问题进行了研究,提出一种改进的鲸鱼优化算法（IWOA）。该算法通过准反向学习方法来初始化种群,提高种群的多样性;然后将线性收敛因子修改为非线性收敛因子,有利于平衡全局搜索和局部开发能力;另外,通过增加自适应权重改进鲸鱼优化算法的局部搜索能力,提高收敛精度;最后,通过随机差分变异策略及时调整鲸鱼优化算法,避免陷入局部最优。实验选取九个基准函数,所有算法均迭代30次,结果表明：改进的鲸鱼优化与原鲸鱼优化算法以及五种改进的鲸鱼优化算法相比,其均值和标准差均优于其他算法,收敛曲线也优于其他大多数算法。说明改进的鲸鱼优化算法收敛精度和算法稳定性最佳,收敛速度较其他大多数改进的鲸鱼优化算法明显加快。     

基于DE 和SA 的Memetic 高维全局优化算法

针对高维复杂多模态优化问题,传统的进化算法存在收敛速度慢,求解精度低等缺点,提出一种面向高维优化问题的Memetic全局优化算法。算法通过全局搜索和局部搜索结合的混合搜索策略,采用多模式并行差分进化算法进行全局搜索,基于高斯分布估计的模拟退火算法进行局部搜索。改进后的Memetic算法不仅继承了差分进化算法能发现全局最优解的优点,而且能大幅度提高搜索效率。最后,通过对4个高维多峰值Benchmark函数进行仿真实验,实验结果表明本文算法有效提高了算法的收敛速度和求解精度。     

基于节点相似性度量的社团结构划分方法

针对复杂网络结构划分过程复杂、准确性差的问题,定义了节点全局和局部相似性衡量指标,并构建节点的相似性矩阵,提出一种基于节点相似性度量的社团结构划分算法.其基本思路是将节点(或社团)按相似性合并条件划分到同一个社团中,如果合并后的节点(或社团)仍然满足相似性合并条件,则继续合并,直到所有节点都得到准确的社团划分.实验结果表明,所提算法能成功正确地划分出真实网络中的社团结构, 性能比标签传播算法(LPA)、GN(Girvan-Newman)、CNM(Clauset-Newman-Moore)等算法优秀,能有效提高结果的准确性和鲁棒性.     

改进的基于局部模块度的社团划分算法

针对大多复杂网络社团划分算法不能快速发现最优节点加入社团的问题,提出一种利用节点亲密度的局部社团划分算法。引入节点亲密度的概念量化社团与邻居节点的关系,按照节点亲密度由大到小选择节点加入社团,最后以局部模块度为指标终止局部社团扩展。在真实网络和人工仿真网络进行实验,并与基于信息压缩的随机游走算法等4种典型社团划分算法相比较,所提算法划分结果的综合评价指标(F1score)和标准化互信息(NMI)均好于比较算法。实验研究表明,所提算法具有较好的时间效率和准确度,适用于大规模网络社团划分。     

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

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

带固定半径近邻搜索3-opt的离散烟花算法求解旅行商问题

传统烟花算法求解大规模离散问题存在收敛速度慢、求解精度不高等问题.针对旅行商问题的特点,提出一种带固定半径近邻搜索3-opt的离散烟花算法.该算法基于基本烟花算法进行离散化改进,采用整数编码的路径表示方法来表示旅行商问题的解,对爆炸算子、高斯变异算子进行离散化操作策略设计.为了使算法具有较好的局部搜索能力,提出固定半径近邻搜索3-opt策略来提高算法精度和收敛速度,同时采用不检测标志策略提高算法效率.实验结果表明:该算法能有效地求解旅行商问题,其离散烟花算子在全局收敛能力、收敛精度、求解时间和稳定性等方面均优于传统烟花算子;基准测试算例的最优解平均误差率仅为0.002％,优于对比算法.