一种基于多标签传播的重叠社区挖掘算法

在众多社区挖掘算法中,标签传播算法因为接近线性时间复杂度被广泛应用,但其也存在大量随机性,稳定性差的问题,采取一种新型的多标签策略解决重叠社区挖掘问题,并根据节点度减少初始标签赋予量的方法提升了算法的稳定性.     

一种稳定的标签传播社区发现算法

网络中的社区发现是当前的一个研究热点。在众多社区发现算法中,标签传播算法因简单快速而被广泛应用。但标签传播算法也存在结果稳定性较差的问题。通过提取非重叠完全子图来避免社区重叠,提取最小极大团来避免巨型社区的出现,基于此,对标签传播算法的初始化过程进行改进,提出了一种稳定的标签传播社区发现算法,即非重叠最小极大团提取算法。在真实网络中的实验结果表明该算法可以大幅提高结果的稳定性。     

融合节点影响力与多标签传播的重叠社区发现算法

重叠社区发现是复杂网络分析研究的重要目标之一。针对传统多标签传播算法存在的社区发现结果具有随机性、不稳定性,以及忽视节点影响力对标签传播的影响等问题,提出一种基于节点影响力与多标签传播的能够生成稳定社区的重叠社区发现算法。算法在节点影响力的计算、排序和核心节点识别基础上,通过邻居节点初始标签的再处理和基于平衡系数的节点标签异步更新策略,实现复杂网络重叠社区的有效识别。在真实数据集和人工数据集上的实验综合表明,算法性能优于各对比算法,适用于大规模复杂网络。     

基于标签传播的重叠社区发现算法

重叠社区发现是复杂网络研究的重要课题.提出一种基于标签传播的重叠社区发现算法.首先利用标签传播算法得到初始无重叠社区划分结果,之后通过设计新的重叠节点识别算法确定重叠节点,最后再根据重叠节点的识别结果对社区进行合并从而得到最终的重叠社区划分结果.该算法克服了已有算法重叠节点占比过大的弊端.为验证算法的有效性,在LFR人工数据集、3个标准公开测试集以及真实的大豆基因共表达网络上进行实验,并与已有算法进行对比.实验结果表明,该算法性能明显优于对比算法,极大地改善了重叠节点比重过大问题.     

基于H指数的改进标签传播算法研究

发现复杂网络中的结构和特征是社区发现的一个重要任务.标签传播算法(LPA)因具有接近线性的时间复杂度,常用于快速处理大规模的社区网络.针对该算法在节点的更新顺序和标签选择策略上存在很大的随机性,严重破坏了算法的稳定性和社区划分结果的准确性.提出了一种基于节点H指数的标签传播算法,即利用节点的综合影响力改进标签传播算法的节点更新顺序和标签选择策略.实验研究表明,改进算法有效地降低了算法的随机性,提高了社区划分的稳定性和准确性.     

基于拓扑势的局部化重叠社区识别

针对传统社区识别算法中需要根据先验知识设定参数、 社区划分结果具有随机性及复杂度过高的问题, 提出一种基于拓扑势的局部化重叠社区识别算法. 该算法通过引入拓扑势计算节点的影响力, 利用节点间的局部相似性度量指标, 采用标签传播策略进行重叠结构的社区识别. 在真实网络及人工合成网络上与多种经典算法进行对比实验验证了算法的高效性.     

基于节点亲密度的标签传播重叠社区发现算法

针对基于标签传播的重叠社区发现算法中出现的随机性和不稳定性问题,提出了一种新的基于节点亲密度的标签传播算法.首先,利用网络的局部信息,以模块度增量为依据,对网络中节点进行粗聚类,实现对节点的初步划分;然后,定义节点亲密度函数进行标签的更新和选择.在人工和真实网络上对算法进行验证.结果表明,该算法能有效地提高大规模重叠社区检测的准确性和稳定性,并且具有近乎线性的时间复杂度.     

基于密度峰值聚类标签传播的社区发现方法

社区发现的目标是发现复杂网络的结构、行为和组织形式。标签传播算法是一种快速有效的社区发现算法,然而在初始的标签传播算法中,节点的结构信息和特征信息没有得到充分利用,且存在标签传播过程不稳定的问题。针对上述问题,文章提出了一种基于改进的密度峰值聚类算法和标签传播算法的有向加权复杂网络社区发现算法(DPC-LPA)。该算法首先根据节点的结构和特征对其进行加权,充分利用了结构信息和特征信息;然后,采用改进的密度峰值聚类算法来寻找网络的社区中心,并据此构建初始社区,提高了社区划分的质量;其次,基于节点相似度和节点权重,合理确定标签传播的更新顺序,并通过衡量节点间标签传播的强度来完成标签传播,解决了标签传播算法不稳定的问题。最后,在CiteSeer、Cora、WebKB和SCHOLAT真实数据集上,将DPC-LPA算法与DCN、WCF-LPA、CLPE算法进行对比实验。实验结果证明了DPC-LPA算法的可行性和有效性：从模块度来看,利用DPC-LPA算法划分的社区具有更加显著的社区结构;从调整兰德系数来看,DPC-LPA算法的社区划分质量更稳定;从运行时间来看,DPC-LPA算法具有较高的效率。     

基于局部邻域连通性的重叠社区发现算法

发现复杂网络中的重叠社区是目前复杂网络分析的重要内容。选择社区代表性强的节点作为种子节点进行扩展是基于种子扩展策略重叠社区发现算法的关键,提出了一种基于度信息和邻域连通性的节点邻域中心性度量指标,并在此基础上提出了一种基于局部邻域连通性的重叠社区发现算法（Local Neighbor-hood Connectivitybased overlapping community detection Algorithm,LNCA）。首先计算每个节点的局部邻域连通熵和邻域中心性cc,选择中心性高的节点作为种子节点;然后采用带重启的随机游走策略扩展种子节点并得到初始社区;最后合并重叠度较大的社区得到最终社区发现结果。在6个带真实社区标签的网络和9个无真实社区标签的网络上,与SLP A、DEMON、CPM、Node_Perception、Ego_Networks、Egonet_Splitter等6个经典重叠社区发现算法进行比较,结果表明,在带标签网络上,LNCA算法在重叠NMI和F1分数上优于多数对比算法,可得到与网络真实社区更匹配的社区结...     

基于联合引力度扩展的加权网络重叠社区划分算法

基于引力度扩展的重叠社区发现算法(GDE),主要用于挖掘无权社交网络的重叠社区结构.真实社区更多是具有加权属性的,本文根据 GDE 算法的种子策略思想,并依据加权网络的特征,以网络节点的度与强度来综合确定重叠社区的中心节点,提出基于联合引力度扩展的加权网络重叠社区划分算法(UGDE).算法的实验检测结果表明：该算法对划分加权网络中的重叠社区具有可行性与有效性.     

面向新浪微博的情感社区检测算法

面向社交网络的情感社区检测,可应用于公共健康、舆情监测等领域.以新浪微博为平台建立一种情感社区检测框架,首先融合微博情感表情特征和情感词典,提出基于朴素贝叶斯算法的半词典半表情(naive Bayes based semi-lexicon and semi-emoji,SL-SE-NB)分类模型以实现对文本的情感极性预测;提出一种基于潜在狄利克雷分配(latent Dirichlet allocation,LDA)话题模型的用户-超话题-关键词(user-topic-keywords,UTK) 模型抽取用户话题;基于标签传播算法(label propagation algorithm,LPA)并加入话题概念,提出基于种子集与最小边介数的标签传播情感社区发现算法(label propagation algorithm based seeds and min-edge betweenness,SMB-LPA).最后通过实验验证了所提出算法的有效性和高效性.     

基于相似性模块度最大约束标记传播的网络社团发现算法

提出一种基于相似性模块度最大约束标记传播的快速网络社团发现算法(MLPA)。该方法采用结构相似度计算, 通过最大约束标记传播模型更新节点标记, 使社团的划分结果更加符合社团内部结构相对紧密、 社团之间结构相对稀疏的特点, 提高社团划分的精确度。结合标记传播5次循环迭代可以完成95%或者更多节点标记过程的实验结果, 判定标记更新过程趋于稳定, 从而在稳定时停止更新, 降低了运行时间。MLPA避免了传统的邻接矩阵计算方法, 适合大规模网络的社团发现。     

非随机的标签传播社区划分算法

针对传统社区传播算法存在局部震荡、划分结果不稳定、划分结果分辨率高等弱点,提出了非随机的标签传播社区划分算法,通过去除传统算法的随机性进而克服其弱点.该算法主要进行了3个方面的改进:按特定顺序更新节点的标签;计算标签数量时,不仅统计邻居节点,而且统计待更新节点本身;通过贡献函数避免多个最大值时的随机选择.实验证明,该算法不仅保证了算法的划分正确性,而且大幅度减少了计算过程中的随机选择动作.     

一种改进的基于相干邻居亲近度的标签传播算法

【目的】提高现有的基于相干邻居亲近度(Coherence neighborhood propinquity)的标签传播算法(Label propagation algorithm,LPA)社区发现的准确性,并减少标签传播过程花费的时间。【方法】在CNP-LPA算法基础上,引入节点间依赖度,提出一种改进的CNP-LPA+算法,在预处理阶段结合相干邻居亲近度与节点间依赖度,将依赖度高的节点并入本区域内的核心节点,并在得到的核心CNP网络基础上传播标签,显著提高了社区发现的质量。选取CNP-LPA算法使用的6组社交网络数据集,采用模块度Q评估LPA、CNP-LPA、CNP-LPA+3种算法的划分结果。【结果】CNP-LPA+算法在所有数据集上均取得了最高的Q值,有效提高了算法的准确性,并减少了标签传播过程花费的时间。【结论】CNP-LPA+算法是有效的。