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

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

基于三级邻居影响力分析的重叠社区发现算法

针对目前重叠社区发现算法时间复杂度较高、社区发现稳定性较差的问题,基于标签传播和COPRA方法,提出一种基于三级邻居节点影响力分析的重叠社区发现算法OCDITN。使用三级邻居节点影响力度量方法TIM(three-level influence measurement)计算节点间的影响力,根据节点影响力确定选择更新节点的顺序;在节点标签更新策略中,根据计算节点与其邻居之间的相似度确定邻居节点标签的更新顺序,计算各节点标签隶属度,发现重叠社区。实验分别基于人工模拟网络数据集和真实世界网络数据集进行测试,与SLPA、LPANNI、COPRA算法相比,该算法在EQ和Qvo两个评价标准上性能分别提升7%和12%,社区划分结果更稳定,社区划分质量更高。     

基于社区划分的影响力最大化算法

影响力最大化问题是社会网络中的重要研究方向,其主要目的是获取社会网络中最有影响力的用户使通过这些用户获得影响传播范围的最大化。随着大数据时代的来临,传统的贪心算法因为复杂度高而不能有效解决大规模社会网络下影响力最大化的时间问题。提出一种基于社区划分的影响力最大化算法,利用影响概率将大规模社会网络分成较小的社区模块,并考虑社区边界节点之间的联系,从而最大程度缩小因社区划分造成的社区间的孤立。为进一步提高算法效率,在每个社区中以影响路径作为影响评估单元,同时对每个社区并行处理以便更高效地获取有影响力的节点。通过仿真实验验证了算法的可行性和高效性,其可以较好地适应大规模社会网络环境。     

基于社区结构的影响力最大化算法

现有的社会网络影响力算法及模型的较高的时间复杂度已不适用于网络规模不断壮大的社会网络服务。针对上述问题,提出了一种基于网络社区结构的影响力最大化算法。首先评估各个社区中节点的影响力,挖掘其核心节点成员;继而在核心节点集和连接社区间的弱纽带节点中选取若干具有影响潜力的初始节点集,使其以最小的代价让信息在网络中得到最广泛的传播。实验结果表明:该算法不仅大大降低了时间复杂度,还获得了接近贪心算法的影响范围,影响覆盖率达到了90%以上。     

社交网络关键黑客节点识别方法北大核心CSCD

计算机网络安全形势严峻,对实施网络攻击的黑客以及黑客所在组织的研究越来越重要。社交网络有不受时间空间限制的特点,因此成为黑客交流的主要平台,也是网络安全研究人员获取信息的重要渠道。为了对社交网络中的黑客进行分析,文章提出一种基于社区发现的社交网络关键黑客节点识别方法。首先,文章通过图卷积网络以无监督方式实现网络的社区划分;然后,利用用户之间的交互行为和主题相似度,通过改进的Page Rank算法实现社区内黑客节点的影响力度量;最后,通过独立级联模型评估关键黑客节点对网络传播效率的作用。在Twitter数据集上的实验表明,该方法能有效识别社交网络中的关键黑客用户。     

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

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

融合标签预处理与节点影响力的重叠社区发现算法

针对节点初始标签散乱及标签传播随机性大的问题，提出一种融合标签预处理与节点影响力的重叠社区发现算法。首先，计算节点影响力，逐步选择影响力值最大的节点作为中心节点；然后，用中心节点的标签对同质的邻居节点进行标签预处理，减少了初始标签数量，降低了后续标签传播的随机性，并初步识别出了重叠节点；其次，通过标签隶属系数识别重叠节点，用节点影响力值选择非重叠节点标签，提高了算法的稳定性和准确性；最后，以最大化自适应函数增量为目标，对内聚度弱的社区进行合并，提高了社区质量。仿真实验结果表明：对于六个真实网络，所提算法在50%的数据集上具有最大的扩展模块度值；而在不同混合度、节点重叠度和节点最大归属社区数的人工基准网络上，该算法在标准化互信息（NMI）指标上都具有最好的性能。综上所述，该算法对各类网络都具有较好的适应性，且具有接近线性的时间复杂度。     

融合标签预处理与节点影响力的重叠社区发现算法

针对节点初始标签散乱及标签传播随机性大的问题,提出一种融合标签预处理与节点影响力的重叠社区发现算法。首先,计算节点影响力,逐步选择影响力值最大的节点作为中心节点;然后,用中心节点的标签对同质的邻居节点进行标签预处理,减少了初始标签数量,降低了后续标签传播的随机性,并初步识别出了重叠节点;其次,通过标签隶属系数识别重叠节点,用节点影响力值选择非重叠节点标签,提高了算法的稳定性和准确性;最后,以最大化自适应函数增量为目标,对内聚度弱的社区进行合并,提高了社区质量。仿真实验结果表明：对于六个真实网络,所提算法在50%的数据集上具有最大的扩展模块度值;而在不同混合度、节点重叠度和节点最大归属社区数的人工基准网络上,该算法在标准化互信息（NMI）指标上都具有最好的性能。综上所述,该算法对各类网络都具有较好的适应性,且具有接近线性的时间复杂度。     

面向大规模学术社交网络的社区发现模型

针对基于标签传播的复杂网络重叠社区发现算法中预先输入参数在真实网络中的局限性以及标签冗余等问题,提出一种基于标签传播的面向大规模学术社交网络的社区发现模型。该模型通过寻找网络中互不相交的最大极大团(UMC)并对每个UMC中的节点赋予唯一标签来减少冗余标签,提高社区发现的效率以及稳定性。标签更新时以UMC作为核心单位采用亲密度的方式由中心向四周更新UMC邻接节点的标签及权重,以权重最大值的方式更新网络中非UMC邻接节点的权重。后期处理阶段采用自适应阈值方式去除节点标签中的噪声,有效克服了预先输入重叠社区个数在真实网络中的局限性。通过在学术社交网络平台——学者网数据集上的实验表明,该模型能够将具有一定共性的节点划分到同一个社区中,并为学术社交网络平台进一步的好友推荐、论文分享等精确的个性化服务提供了支持。     

基于标签传播的社区发现算法研究与应用

在大规模数据量分析研究中,复杂网络的社区发现已成为国内外众多学者的研究热点.深入研究社区发现算法有助于揭示网络不同层次结构及功能,挖掘出具有现实意义的社区结构.本文综述了较为经典的社区发现算法以及有关于社区质量评价的方法,阐述了基于标签传播的社区发现算法优劣性以及国内外研究人员的思路与改进.     

基于阈值的社交网络影响力最大化算法

对于社交网络影响力最大化问题,Kemple和Kleinberg提出了有较好影响范围的贪心算法,但是KK算法的复杂度非常高,并不实用.利用线性阈值模型提出了一种基于节点激活阈值的启发式算法.它综合考虑了节点之间的影响力和节点的激活阈值,根据每个节点在激活过程中动态变化的阈值来计算PIN值,启发过程中,每一次都选取PIN最大的节点作为种子节点进行激活,贪心阶段中再贪心地挑选那些具有最大影响范围增量的节点作为种子节点.通过实验表明,即使在完全不采用贪心阶段,该算法的激活范围与KK算法都非常接近,而算法的复杂度则相对非常小.实验还表明该算法相对于HPG算法在相同启发因子c的情况下具有更大的激活范围.     

基于多标签传播的社交网络用户影响力评估

为了识别出社交网络中的关键人物,需要对用户影响力进行评估。由于影响力是借助信息在网络中的扩散而逐步形成的,因此需首先对影响力传播过程进行建模;然后以该模型为基础,用标签表示影响力的所有者,以隶属度表示用户被影响的程度,利用多标签传播来模拟影响力传播的过程,实现了一种新的用户影响力评估算法MLPIA(Multi-label Propagation User Influence Asessment Algorithm);最后,在真实数据集上测验排名靠前的用户的影响力覆盖范围和紧密中心性,结果证明了该算法的合理性和有效性。     

基于相似度的微博社交网络的社区发现方法

作为一种新兴的社交媒体,微博由于其信息的简短性、实时性和公开性,在短短4年内已积累数以亿计的用户并且数量还在迅速增长,由此带来的社会影响日益广泛.对微博用户关系网络进行社区发现具有重要的理论和实际意义.根据微博网络的有向性及建立关注关系的随意性等特点,提出一种基于共同关注和共同粉丝的微博用户相似度,定义此相似度的模块化函数,依据贪心算法思想设计出基于此模块化函数最大化的社区发现方法,并在此基础上将该方法推广到具有标签信息的微博网络中.应用该方法处理了3个真实的微博用户关系网络数据,结果表明该方法可以有效地发掘微博用户关系网络中的社区结构.     

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

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

基于社交网络弱连接属性的影响力最大化算法

首先研究了目前影响力最大化问题的解决方案,并总结了这些解决方案的优缺点.对社交网络中弱连接的研究之后发现,弱连接可以有效地打通社交网络中不同社团之间的信息壁垒,使得信息在不同社区间流通.利用弱连接的这一作用,同时基于贪心思想,提出BWTG（base-on weak tie greedy)算法来解决影响力最大化问题,并根据解空间的不同,把BWTG算法分为BCWTG（base-on complete weak tie greedy)和BNCWTG（base-on not complete weak tie greedy)两种算法.影响力最大化问题的传统评价指标有两种：时间复杂度和最终激活节点数,但考虑到实际情况,定义了ANNI（actived nodes/node influence)这一新的评价指标,用于衡量回报与付出之比.为了验证BCWTG和BNCWTG算法的性能,在不同类型、不同规模的真实数据集中对算法进行实验验证,在时间复杂度、最终激活节点数和ANNI这3个方面与经典的Greedy算法进行对比,实验结果表明,BCWTG算法和BNCWTG算法在运算时间和ANNI方面有所提高,最终激活节点数方面却弱于Greedy算法,但当满足一定条件时,BCWTG和BNCWTG算法在最终激活节点数方面也能接近Greedy算法.     

基于成对约束的多标签传播重叠社区发现方法

针对多标签传播重叠社区发现算法(COPRA)存在的社区划分结果准确性低和鲁棒性差的问题,提出一种基于成对约束的多标签传播重叠社区发现方法 (PCMLPA)。以主动查找、扩展的方式引入成对约束指导社区发现,提高社区划分结果的准确性。在标签传播的过程中,根据节点影响力大小确定节点更新顺序,根据节点的相似性度量确定邻居节点的遍历顺序,解决COPRA鲁棒性差的问题。与其它基准算法的对比实验结果表明,PCMLPA方法鲁棒性强且社区划分结果具有更高的准确性。     

复杂网络社区发现中标签传播算法的研究与应用

社区结构是复杂网络的一种重要特性,决定了所在网络具备的功能,从复杂网络中发现存在的社区结构,组织形成更大网络社网已成为当前研究热点。为更加准确地发现社区结构,在众多社区发现算法中,标签传播算法以简单高效和易实现的优点得到广泛应用。笔者研究了复杂网络社区发现中标签传播算法的应用。     

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

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

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

针对COPRA算法因在标签更新过程采用随机策略而导致的重叠社区划分结果不稳定问题,本文对COPRA算法进行了改进,提出了一种简单的重叠社区发现算法.该算法仍采用同步的方式传播标签,但只在以边缘节点为中心的桥梁节点群内进行标签传播,以此提升发现重叠社区的速度.该算法还引入了节点连接社区强度,利用其降低标签更新过程中的随机...