一种基于标签传播的两阶段社区发现算法

针对标签传播社区发现算法在节点更新顺序及标签传播过程中存在较大随机性而导致划分结果稳定性差的问题,提出一种基于标签传播的两阶段社区发现算法(a two-stage community detection algorithm based on label propagation, LPA-TS),通过参与系数确定节点更新顺序,并在标签传播过程中依据节点间相似性更新节点标签,得到初始社区划分.将社区看作节点,社区间连边数作为边权重,得到社区关系网络.按照参与系数由低到高的顺序合并社区关系网络中的节点,得到最终社区划分结果.算法LPA-TS减少了传统LPA方法在节点更新和标签传播过程的随机性;在第2阶段,将不符合弱社区定义的初始社区与连边最多的相邻社区合并,再按照社区参与系数由低到高的顺序合并初始社区提升社区发现质量.通过与一些经典算法在8个真实网络及不同参数下LFR benchmark人工网络数据集上的实验比较表明LPA-TS算法表现了良好的稳定性,在NMI、ARI、模块性等方面表现良好.     

Balanced Multi-Label Propagation for Overlapping Community Detection in Social Networks

In this paper,we propose a balanced multi-label propagation algorithm(BMLPA) for overlapping community detection in social networks.As well as its fast speed,another important advantage of our method is good stability,which other multi-label propagation algorithms,such as COPRA,lack.In BMLPA,we propose a new update strategy,which requires that community identifiers of one vertex should have balanced belonging coefficients.The advantage of this strategy is that it allows vertices to belong to any number of communities without a global limit on the largest number of community memberships,which is needed for COPRA.Also,we propose a fast method to generate "rough cores",which can be used to initialize labels for multi-label propagation algorithms,and are able to improve the quality and stability of results.Experimental results on synthetic and real social networks show that BMLPA is very efficient and effective for uncovering overlapping communities.     

基于网络社区发现的标签传播聚类算法

高维数据的聚类特性通常难以直接观测.将其构建为复杂网络,节点间的拓扑结构可以反映样本之间的关系.对网络中的节点进行社区发现,可实现对数据更直观的聚类.提出一种基于网络社区发现的低随机性标签传播聚类算法.首先,用半径和最近邻方法将数据集构建为稀疏的全连通网络.之后,根据节点相似度进行节点标签预处理,使得相似的节点具有相同的标签.用节点的影响力值改进标签传播过程,降低标签选择的随机性.最后,基于内聚度进行社区的优化合并,提高社区的质量.在真实数据集和人工数据集上的实验结果表明,该算法对各种类型的数据都具有较好的适应性.     

基于模块密度优化的标签传播社区发现算法

基于标签传播的社区发现算法(LPA)以其简单高效得到了广泛的研究,然而当社区结构模糊时,LPA得到的是一个单一的社区,这是无意义的.模块化标签传播算法(LPAm)则倾向于将网络划分为度数相近的社区且存在解极限问题.为此提出基于模块密度的标签传播(LPAd)算法,该算法通过对模块密度优化进行标签标记和传播,以避免过大社区的形成,且生成的社区满足Radicchi等人提出的弱社区定义.多个真实数据集和人工网络数据的实验结果表明,本文算法在不改变算法复杂度的情况下提高了所发现社区的质量,与现有的若干基于标签传播的社区发现算法相比,取得了改进的效果.     

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

标签传播算法是一种被广泛应用的社区发现算法,该算法为网络中的每个节点分配一个初始标签,然后通过传播标签来发现复杂网络中的潜在社区,具有时间复杂度低的特点。当前基于标签传播的重叠社区发现算法存在忽略节点重要性差异、需要人为设置参数等不足。针对该类算法在重叠社区发现方面的缺陷,提出一种基于多标签传播的重叠社区发现优化算法。该算法使用K-核分解方法找出若干个社区核心节点,以这些节点为种子节点,逐层向外传播标签;在进行标签选择的时候以邻居节点标签的种类来决定重叠节点的标签个数。实验表明,该算法明显改善了社区发现的性能,提高了划分结果的稳定性和准确性。     

局部扩展的标签传播蚁群优化重叠社区发现*

社区发现是分析复杂网络重要的方法。为了提升社区发现算法速度和高精度命题,提出一种局部扩展标签传播算法与蚁群优化结合的重叠社区发现框架（ELPA-ACO）。首先利用局部扩展的标签传播社区发现算法快速获得蚁群初始信息素和位置,然后,结合网络中节点的拓扑结构、内部标签属性、历史信息和节点的传播相互影响力等因子改进蚂蚁转移概率,进一步提高划分精度。在未知网络和真实网络验证,ELPA-ACO算法可适应多种网络划分,无论是速度还是精度都有显著提高。     

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

语义社会网络(Semantic social network, SSN)是一种由信息节点及链接关系构成的新型复杂网络, 为此以节点邻接关系为挖掘对象的传统社会网络社区发现算法无法有效处理语义社会网络重叠社区发现问题. 由此提出标签传播的语义重叠社区发现算法, 该算法以标签传播算法(Latent Dirichlet allocation, LDA)模型为语义信息模型, 利用Gibbs取样法建立节点语义信息到语义空间的量化映射; 提出可度量节点间相似性的主成分 (Semantic coherent neighborhood propinquity, SCNP)模型和语义影响力(Semantic impact, SI)模型; 以SCNP作为标签传播的权重, 以SI 作为截断值的参数, 提出一种改进的Semantic-LPA (Semantic label propagation algorithm)算法; 提出可度量语义社区发现结果的语义模块度模型, 并通过实验分析, 验证了算法及语义模块度模型的有效性及可行性.     

基于模块度优化的标签传播社区发现算法

标签传播算法（LPA）是一种快速高效的社区发现算法,算法无需社区数量等先验信息,但存在大量随机性,稳定性较差. 为了提高标签传播算法的稳定性,提出了一种改进的标签传播算法（LPAMP）. 该算法分为两个阶段,第一阶段以模块度贪婪为依据,进行节点粗聚类;第二阶段在粗聚类的基础上,进行节点标签传播. 实验结果表明,所提算法降低了标签传播算法的随机性,增强了稳定性,并且提高了准确率.     

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

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

基于标签传播的社区挖掘算法研究综述

社会网络由于其流行程度已经成为众多学者的研究热点。通过社区挖掘算法可以发现存在于社会网络中的潜在社区,而重叠社区挖掘则可以挖掘出更具有现实意义的社区结构。但是在研究中社会网络所包含的庞大数据量又会为之带来种种不便,因此快速的社区挖掘算法就受到了越来越多的重视。基于标签传播的社区挖掘算法具有近乎线性的时间复杂度。文中将从多方面研究目前基于标签传播的社区挖掘算法的优劣,并且详细分析基于标签传播算法在以后研究中的改进思路。     

基于LeaderRank的重叠社区发现算法

在真实的社交网络结构中常常存在着社区相互重叠的现象,发现社交网络中的重叠社区有利于研究网络特性,反映网络中的真实情况。针对多标签传播重叠社区发现算法COPRA存在的随机性,导致社区发现结果稳定性差等问题,提出一种结合节点重要性的标签传播算法。该算法首先采用LeaderRank计算出网络中各个节点的重要性,选择重要性高的节点进行团扩展作为标签初始阶段的预处理,采用合理的标签更新顺序以防止抵消预处理阶段的工作,后期引入贡献度来弱化标签选择阶段的随机性,在基准网络和真实网络上的实验结果表明本文算法提高了社区发现结果的质量。     

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

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

基于链接密度聚类的重叠社区发现算法

为了能够更加有效地发现社会网络中具有重叠性的社区结构,提出一种基于链接密度聚类的重叠社区发现算法DBLINK.该算法首先以网络中的边集为对象,将其划分为若干个互不相连的链接社区,再将所得到的链接社区转化为最终的节点社区,隶属于不同链接社区边的交点即为网络中的重叠节点.由于DBLINK采用基于密度的算法对边集进行聚类,将不满足一定条件的边孤立出来,使其不隶属于任何链接社区,因此可以避免社区结构过度重叠的现象发生,从而提高了重叠社区发现的质量.实验结果表明,DBLINK不仅具有较好的时间效率,而且在社区发现的质量方面也优于其他几种代表性的重叠社区发现算法.     

基于标签传播的拓扑势社区检测算法

基于拓扑势的社区检测通过节点的链接信息构造拓扑势域,在拓扑势域内进行社区划分.但实际划分过程存在大量孤立性社区.带节点属性信息的社区检测问题作为社区的重要组成,已成为社区检测的主要研究方向.本文提出了一种结合标签传播的拓扑势社区检测算法(TPCDLP).首先,结合标签传播思想将属性信息转换为节点间的链接权值.其次,把链接权值加入到拓扑势中构造拓扑势域.再利用核心节点进行子群社区的划分.最后,利用子群社区间核心节点的距离进行社区划分.在3个含标签属性的数据集上,与6种算法对比,该算法在改进的模块度QoEv、信息熵Entropy、社区重叠度Overlap和综合指标F上表现更优.在3个真实社区上应用了该算法,并与3种算法对比,实验结果显示该算法在标准化互信息指标N MI上表现良好,能够有效应用于实际问题.     

基于核心图的标签传播算法

网络中的社团发现是当前的一个研究热点.在众多社团发现算法中,标签传播算法因简单快速而被广泛应用,但标签传播算法也存在结果稳定性较差的问题.基于此对标签传播算法的初始化过程进行改进,提出了基于核心图的标签传播算法.通过计算图中任意两点的k阶公共邻居,将具有最大相似性的节点及k阶邻居作为初始核心社团,并为其分配初始标签.通过上述过程,提取一些较为紧密的子结构来作为标签传播的初始社团,并给这些结构分配初始社团标签.在真实网络中的实验结果表明,该算法可以大幅提高结果的稳定性.     

基于标签传递的异常检测算法研究

异常检测旨在检测出观测数据中的非正常值,被广泛应用于反信用卡欺诈、网络入侵检测、医疗分析以及气象预报等领域。在异常检测中,正常数据通常具有异常数据所不具备的某种内蕴结构。因此,如何有效地利用正常数据与异常数据在数据结构上的差异性将有助于提高异常检测性能。为此,本文提出了一种新颖的基于标签传递的异常检测算法。该算法通过图模型刻画正常数据所具有的内蕴结构,并通过多重标签传递来构建未标记正例样本与待测试样本的标签置信度的差异。最后,基于正例样本的标签置信度的统计特性分析,实现对测试样本的异常性判决。在人工合成及真实数据集上的实验验证了本文算法的有效性。     

稳定的标签传播社团划分算法研究

快速稳定地发现复杂网络中的社团是近年来社团划分研究的热点。标签传播算法(LPA)具有接近线性的时间复杂度,能快速发现复杂网络中的社团结构,但是该算法在标签传播过程中存在不确定性和随机性,降低了划分结果的准确性和稳定性。为了解决这一问题,设计了一种稳定的标签传播社团划分算法(S-LPA)。该算法利用改进的K-Shell算法来计算节点全局影响力,并结合能反映节点局部影响力的度值以及邻居节点信息,计算节点综合影响力;在标签传播过程中,根据标签影响力更新标签;当网络中所有节点的标签不再变化或者迭代次数达到最大值时,拥有相同标签的节点划分到同一社团中。在真实网络和人工合成网络上的实验结果表明,S-LPA算法不仅具有线性时间复杂度,而且提高了社团划分的质量和稳定性。     

基于网络节点中心性度量的重叠社区发现算法

基于搜索密度峰值的聚类思想,设计了一种网络节点的中心性度量模型,并提出了一种重叠社区发现算法.首先,定义了网络节点的内聚度和分离度,分别用于描述网络社区内部连接稠密和外部连接稀疏的结构特征,在此基础上计算节点的中心性度量表达节点对社区结构的影响力.接着,利用3δ法则选择中心度异常大的节点作为社区中心.以隶属度表达社区间的重叠特性,并给出了非中心节点的隶属度迭代计算方法,将各节点分配到其可能隶属的网络社区,以实现重叠社区划分.最后,利用人工网络和真实网络对提出的重叠社区发现算法进行验证,实验结果表明：该算法在社区发现质量和计算效率方面都优于许多已有重叠社区发现算法.     

基于标签传递的人像分割

人像分割技术在人脸识别、3D人体重建及运动捕捉等实际应用中具有重要的作用,其可靠性直接影响后续处理的效果。本文以标签传递理论的目标分割算法为基础,提出了一种优化的人像分割算法。首先,引入模糊集理论,提高复杂背景图像分割的能力;然后,使用超像素过分割进行预处理,利用过分割结果优化相似度定义提高分割轮廓的平滑性和可靠性。实验结果表明,与原有标签传递算法相比,本文提出的算法可以保持较高的分割轮廓平滑度且具有更高的分割精度。     

基于节点拓扑结构和属性的重叠社区检测算法

近些年来,网络中的重叠社区检测应用越来越广泛,这极大引起了人们的兴趣。通常重叠社区检测只考虑节点的拓扑结构信息,忽略了节点的属性信息,这可能会遗漏数据间的重要结构。本文提出了一种基于节点拓扑结构和属性相似度的局部社区检测算法。首先,计算出节点与社区之间属性相似度。其次,为挖掘内部紧耦合的社区,计算出能够表示耦合性的模块度增量。最后,通过融合多个已检测到局部社区,计算出隶属矩阵从而获取全局重叠社区结构。在三个有真实社区的数据集上的实验结果从内部指标模块度和与真实社区的比较验证了基于节点拓扑结构和属性相似度的重叠社区检测算法比目前基于节点结构的社区检测算法在效率和有效性上有所提升。