基于势函数的标签传播社区发现算法

针对标签传播算法(LPA)存在大量随机性、算法稳定性差的问题,提出了基于数据场势函数的标签传播算法(LPAP)。该算法计算所有节点的势值,搜索势值极值点。初始化时仅赋予势值极值点以标签,迭代过程中根据邻接节点中相同标签节点势值之和更新标签,所有节点标签不再改变时迭代结束。实验结果表明：该算法得到的社区划分方式平均是LPA的4.0%,是平衡传播算法(BPA)的12.9%;信息变化参数平均是LPA的45.1%,是BPA的73.3%。具有更好的稳定性,适用于大型网络的社区发现。     

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

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

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

标签传播算法存在大量随机性,极大地破坏了算法的稳定性。在深入分析标签传播算法随机性产生原因的基础上,提出基于节点度的标签传播算法。该算法初始化时仅赋予节点度的极值点以标签,并根据邻接节点中具有相同标签的节点度之和进行标签更新。实验表明该算法极大地降低了算法中的随机性,提高了社区划分的稳定性,加快了算法的收敛速度。     

基于节点重要性与相似性的标签传播算法

标签传播算法是一种常用的社区发现方法,具有近似线性的时间复杂度,但该算法存在随机性和不稳定性.为了解决标签传播算法存在的准确性低和稳定性差的问题,本文提出了基于节点重要性与相似性的标签传播算法(Label Propagation Algorithm based on node Importance and Similarity,LPA IS).首先,基于节点重要性提出种子节点集和算法更新序列的获取方法.其次,利用节点重要性与相似性提出了一种计算标签综合影响力的方法,任意节点根据其邻居标签的综合影响力更新自身的标签.在真实网络和人工合成网络上进行实验,结果表明,与其它5种典型标签传播类算法对比,LPA IS算法能够在一定程度上提高算法的准确性和稳定性,并且能够减少算法的迭代次数.     

基于加权聚类集成的标签传播算法

标签传播算法（LPA）是一种高效地处理大规模网络的社区发现算法,由于其近乎线性的时间复杂度而受到广泛关注。然而,该算法每个节点的标签依赖于其邻居节点,其迭代速度和聚类有效性对标签信息的更新顺序非常敏感,影响了社区发现结果的准确性和稳定性。基于该问题,提出了一种基于加权聚类集成的标签传播算法。该算法利用多次标签传播算法的结果作为基聚类集,并用模块度评估每个基聚类的重要性,使其作为节点相似性度量的权值形成加权相似性矩阵,最后通过层次聚类得出最终的社区划分结果。在实验分析中,该算法和其他5个具有代表性的标签传播算法的改进算法在真实数据集上进行了比较,展示了新算法能有效地提高标签传播算法的社区发现精度。     

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

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

基于复杂网络的社区发现算法研究

近年来,高质量社区的挖掘和发现已经成为复杂网络研究的一个热点。目前大多的社区发现算法主要针对无向网络,但现在的很多真实网络通常都是有向加权的。同时,标签传播算法(LPA)是一种接近线性复杂度的社区发现算法,该算法具有简单高效、不需要提供社区规模和社区个数等先验知识的特点,因而得到了广泛关注和应用。针对有向加权网络,提出了一种基于节点重要性和节点相似性的改进标签传播算法(CRJ-LPA)。该算法综合考虑节点的边权、节点的信息传播能力、节点相似度以及节点集聚系数等因素。算法通过加权的ClusterRank获得节点重要性列表用以避免LPA中的随机选择;然后,采用Jaccard系数度量节点的相似度,结合节点重要性列表计算出一个新的度量CRJ(重要度和相似度),提高了算法的稳定性。实验结果表明,该算法有效可行,且具有较好的鲁棒性。     

基于密度峰值的标签传播算法

随着智能技术应用的推广,高质量社区的检测已成为社会网络研究的热点之一。由于具有线性时间复杂度,且无需预定义目标函数和社团数,标签传播算法（LPA）已得到广泛关注。然而,在标签传播过程中,LPA具有不确定性和随机性,进而影响检测社区结果的准确性和稳定性。为此,提出一种基于密度峰值的标签传播社区检测方法（DPC-RWL）。首先,采用密度峰值聚类算法查找出社区的核心节点集合,计算节点与核心节点集之间的权重,选取最大值为该节点赋予权值。最后,使用基于标签传播算法的归属度函数进行传播。真实网络和LFR人工基准网络的对比实验表明,所提算法能准确高效地识别出社区结构。     

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

针对标签传播算法(LPA)结果的不稳定性,提出一种改进的基于标签传播的社区发现算法。该算法引入LeaderRank的概念来量化网络节点的影响力和重要性;然后按照节点重要程度从高到低选择若干核心节点;最后按照顺序分别以每个核心节点为中心向外逐层进行标签更新,直到不再出现标签变化为止,从而解决了原始算法对节点随机排序造成的结果不稳定性。以LFR基准网络和真实网络为实验数据,与几个现有标签传播算法进行比较,社区划分结果的标准化互信息(NMI)和模块度(Modularity)均高于对比算法。理论分析和实验结果表明所提算法不仅有效地增强了社区发现结果的稳定性,同时提高了准确率。     

基于节点影响力的理性节点标签传播算法

社区发现能够揭示真实社会网络的拓扑结构和重要节点.由于具有线性时间复杂度,无需定义目标函数及目标参数,标签传播算法(LPA)作为经典社区发现算法被广泛应用在学术和实践领域.针对LPA算法更新顺序的无序性和标签选择的随机性,提出基于节点影响力的理性节点标签传播算法(RLPBNI).将节点影响力排序作为更新顺序,引入理性节...     

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

针对多标签传播重叠社区发现算法COPRA存在的的随机性强、鲁棒性差等问题,提出一种基于多标签传播思想的重叠社区发现算法。该算法通过LeaderRank算法来量化网络中节点的重要性,再根据量化值大小对节点进行团扩展,得到可重叠的最具重要性的粗糙团,分别对粗糙团和非粗糙团中的节点进行标签初始化,再通过合理的标签迭代顺序和改进的标签删选策略进行标签更新,直到达到标签传播的终止条件结束迭代过程。在人工网络图和真实数据集上进行实验,结果表明所提算法不仅有效地增强了社区发现结果的稳定性,同时提高了准确率。     

基于节点中心性和社区相似性的快速标签传播算法

为了减少标签传播算法（LPA）中不必要的更新、解决算法准确率低且稳定性差的问题,提出了基于节点中心性和社区相似性的快速标签传播算法（FNCS_LPA）。按照节点中心性度量对网络的节点从低到高进行排序后加入节点信息列表,利用节点信息列表来指导更新过程,提高社区发现的稳定性并避免不必要的更新;采取基于社区相似性的更新规则,提高了社区发现的准确率。在真实社会网络和LFR基准网络上进行实验：相比LPA和三种较好的LPA改进算法,FNCS_LPA在执行速度方面提升了几十倍,真实社会网络的模块度也相对较高,在社区结构比较模糊的LFR基准网络上的归一化互信息有明显的优势。实验结果表明FNCS_LPA在提高执行速度的基础上,提高了算法的稳定性和准确率。     

基于标签影响力的半同步社区发现算法

微博网络与社交网络等的交互式社会信息网络规模的快速增长对社区发现提出巨大挑战。标签传播算法(LPA)虽然在时间复杂度上具有很大的优势,但是其内在的多种随机策略使得算法稳定性不高。针对LPA的随机问题,提出了一种基于影响力的半同步标签传播算法(ISLPA),能有效地避免振荡问题,巧妙地实现了相邻节点之间的同步更新,并结合影响力从初始标签、选择邻居节点和更新顺序三方面进行了改进,摒弃了原有的随机策略。真实网络和人工网络的实验结果表明,ISLPA具有较高的稳定性与有效性,与其他LPA相关算法相比存在明显的优势。     

基于节点引力与鱼记忆的社区检测算法

标签传播算法是高效且具代表性的社团检测算法,其中不包含必需调节适应的相关参数,是大型网络社团检测的首选算法。标签传播算法具有较低的时间复杂度,但其随机性较强,且在标签传播过程中存在不确定性因素,影响了社区检测的准确性和稳定性。针对上述问题,提出一种基于节点引力和鱼记忆标签存储策略的社区检测算法CDA-GM。通过融入节点信息熵的k-shell排序策略增强社区检测的准确性,利用节点间的引力更新标签,减小标签传播的随机性。在此基础上,引入鱼记忆节点标签存储策略,避免出现标签震荡,增强标签传播的稳定性。选择人工网络和真实世界网络数据集进行实验,结果表明,该算法能够显著提高社区检测质量,获得准确的社区结构,与COPRA、SLPA、DLPA和COPRAPC算法相比,其标准化互信息值平均提高0.01、0.18、0.12、0.02,社区模块度平均提高0.04、0.02、0.07、0.01。     

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

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

基于节点层级与标签传播增益的重叠社区发现?

多标签传播算法具有接近线性的时间复杂度,但用于重叠社区发现时存在精度低、稳定性差的问题。文中基于重叠节点更可能出现在社区边缘的思想,提出基于节点层级与标签传播增益的重叠社区发现算法。该算法首先利用改进的基于节点中心度与社区分布约束的单标签传播方法发现非重叠社区,并在标签传播过程中利用局部信息同步计算节点中心度。然后根据节点中心度定义节点层级函数,标记节点在所属社区中的层级。最后基于节点间的标签传播增益,利用新的多标签更新规则,获得重叠社区结构。实验表明该算法能有效提高精度和稳定性。     

融合特征向量中心性与标签熵的标签传播算法

重叠社区结构挖掘旨在发现复杂网络中多个独立社区之间的重叠部分，其在社交、交通、舆情乃至反恐等领域具有广泛的应用。然而，目前基于标签传播的重叠社区挖掘算法在社区结构模糊的网络中表现出较强的随机性，导致准确度不高。针对重叠社区模糊边界导致的不确定性和低准确度问题，提出一种融合特征向量中心性与标签熵的标签传播算法ECLE-LPA。ECLE-LPA通过融合节点的K-核迭代因子与特征向量中心性来计算节点影响力并初始化节点标签，在标签传播过程中，通过节点标签熵和节点间亲密度更新节点标签列表及其标签隶属度，从而较好地克服了社区模糊边界的识别问题。实验结果表明：在Les Miserables、Polbooks、Football、Polblogs和Netscience等真实网络中，ECLE-LPA划分结果的EQ值普遍比对比算法提高了1%～3%;在社区结构模糊的人工网络中，ECLE-LPA划分结果的NMI值比其他标签传播算法提高了10%以上。     

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

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

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

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

基于节点聚集系数的分布式标签传播算法

随着互联网的发展和普及,越来越多的用户加入到社交网络,逐渐形成了大规模、多样化的社区。对于新浪微博等社交服务来说,这些社区的发现可以为用户和商家提供有价值的信息。在社区发现算法中,标签传播算法(LPA算法)具有算法思想简单、复杂度低、无需初始化社区数量等优点,但准确率较低,同时在大数据环境下,效率还不够高。将节点聚类系数引入LPA的标签更新过程中,提出一种结合MapReduce分布式计算框架的社区发现算法——DisLPA算法。实验表明,该算法不仅提高了准确率,同时有效改善了计算瓶颈问题。