基于节点多关系的社团挖掘算法及其应用

为度量多关系节点相似性、挖掘具有多关系节点的社团结构,提出基于节点多关系的社团挖掘算法LSL-GN。首先基于节点相似性和节点可达性刻画具有多关系的节点相似性度量指标LHN-ISL;然后利用该指标重构目标网络的低密度模型,并结合GN(Girvan-Newman)算法完成社团划分。将LSL-GN算法与多个经典社团挖掘算法在模块度（Q）、标准化互信息（NMI）和调整兰德指数（ARI）上进行对比,结果显示LSL-GN算法在3个指标上均优于经典算法,说明它的社团划分质量相对较好。将LSL-GN应用于“用户-应用”的移动漫游网络模型中,划分出了以携程旅行、高德地图、滴滴出行等为基础应用的社团结构,而这些社团划分结果可为设计个性化套餐业务提供策略参考信息。     

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

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

基于社团强度系数的社团结构发现算法

社团结构是复杂网络普遍存在的拓扑特性之一.为了将复杂网络中的社团结构有效地划分出来,在对强社团定义的基础上,引入社团强度系数的概念,提出了一种基于社团强度系数的社团结构发现算法.该算法具有较低的时间复杂度,通过不断寻找网络最大度数的节点及其邻居节点,计算其社团强度系数来衡量社团如何划分.主要针对Zachary网络和Dolphin网络等进行了仿真实验,结果表明该算法具有较高的社团划分准确度、较好的敏感性和良好的可扩展性,充分验证了其可行性和有效性.     

基于相似性复杂网络社团结构发掘算法的研究

复杂网络的社团结构对于研究现实世界有着重要意义。然而,现在的一些算法存在着划分精度不够,限制条件较多等不足,影响了复杂网络的应用。所以,本文提出了一种基于相似性复杂网络社团有效划分算法。文中,利用相似性,灵活定制阈值,将层次聚类思想应用到网络社团发掘过程中。并且,在不同的层次上设定了相应阈值,保证了精度,实现网络社团的初步划分。为获得更加清晰的结构,提出了重叠节点的相似性指标。结果,本文不仅发现了网络的层次社团结构,还挖掘出重叠节点。最后,实验表明本算法提高了复杂网络社团划分的精度。     

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

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

基于核心节点扩散的有向网络重叠社团发现算法

复杂网络中的社团结构探测是当前复杂网络研究领域的一个热点问题。传统的社团划分算法主要以无向、无权网络作为分析对象,不能够适用于现实世界中各种有向网络、加权网络。在分析和研究各种社团划分算法的基础上,提出一种新的重叠社团发现算法。该算法从网络中的核心节点开始,不断合并适应度最大邻居节点,最终将网络划分为多个重叠的社团。最后,将该算法应用到两个有向网络中,实验表明该算法能够很好地划分出有向网络中的重叠社团。     

基于节点依赖度和相似社团融合的社团结构发现算法

社团结构作为复杂网络的拓扑特性之一具有重要的理论和实践意义。提出一种基于节点依赖度和相似社团融合的社团结构发现算法,首先根据依赖度和相似度的定义将整个网络划分成若干个平均集聚系数较大的局部网络,构成网络的基础骨架社团;然后根据连接度的定义不断将社团边缘的节点和小社团吸收到相应的骨架网络中去,直到所有节点都得到准确的社团划分。算法在Zachary空手道俱乐部网络和海豚社会网络中进行了社团划分实验,并与GN算法和Newman快速算法进行了比较,结果表明该算法可以有效地划分社团边缘的模糊节点,社团划分结果具有较高的准确度。     

基于节点关联度的标签传递社团发现算法

现有快速社团发现算法存在划分质量不高和标签传递划分结果不稳定问题。针对这些问题,提出一种基于节点关联度的标签传递社团发现算法(ELPA)。以邻居节点间的关联度为约束更新网络节点的标签,实现对社团初始划分;以模块度增量最大化对社团进行合并,使得每次合并后的社团模块度最大。为验证ELPA的有效性,基于计算机生成网络和真实网络环境与经典算法FN、LPA进行对比实验。结果表明,ELPA算法不仅弥补了LPA算法结果不稳定的缺陷,而且提高了社团划分精度和有效性。     

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

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

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

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

基于共邻节点相似度的社区划分算法

复杂网络中的社区结构能帮助人们认识网络的基本结构及其功能。针对目前多数社区划分算法准确率低、复杂度高的问题，提出了一种基于共邻节点相似度的社区划分算法。首先，为了计算节点间相似度值，提出了相似度模型，该模型通过将被测节点对的邻居节点引入一并计算，提高了相似度度量的准确性；然后，计算节点局部影响力值，能客观地表现出节点在所处网络中的重要性；其次，结合节点相似度值和节点局部影响力值对节点进行层次聚类，完成网络社区结构的初步划分；最后，通过聚合初步划分的子社区，获得复杂网络的最优模块度值。仿真结果表明，在网络的社区特征模糊时，与新的基于局部相似度的社区发现算法（CDALS）相比，所提算法的准确率提高了14%，证明了所提提法更能够准确、有效地划分复杂网络的社区结构。     

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

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

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

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

基于节点相似性和网络嵌入的复杂网络社区发现算法

社区发现算法对分析复杂网络的拓扑和层次结构、预测复杂网络的演化趋势等具有十分重要的意义.传统的社区发现算法划分精度不高,忽略了网络嵌入的重要性.针对这样的问题,提出了基于节点相似性和网络嵌入Node2Vec方法的无参数社区发现算法.首先,使用网络嵌入Node2Vec方法将网络节点映射成欧氏空间中低维向量表示的数据点,计...     

基于结构相似度仿射传播的社团检测算法

复杂网络中普遍存在着一定的社团结构,社团检测具有重要的理论意义和实际价值。为了提高复杂网络中社团检测的性能,提出了一种基于结构相似度仿射传播的社团检测算法。首先,选取结构相似度作为节点之间的相似性度量,并采用了一种优化的方法来计算复杂网络的相似度矩阵;其次,将计算得到的相似度矩阵作为输入,采用快速仿射传播(FAP)算法进行聚类;最后,得到最终的社团结构。实验结果表明,所提算法在LFR(Lancichinetti-Fortunato-Radicchi)模拟网络上的社团检测平均标准化互信息(NMI)值为65.1%,要高于标签传播算法(LPA)的45.3%以及CNM(Clauset-Newman-Moore)算法的49.8%;在真实网络上的社团检测平均模块度值为53.1%,要高于LPA算法的39.9%以及CNM算法的47.8%,具有更好的社团检测能力,能够发现更高质量的社团结构。     

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

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

一种基于模糊相似关系的局部社区发现方法

近几年,在线社交媒体发展飞速,出现了大规模社会网络.传统的基于网络全局结构的社区发现方法难以有效地处理这些大网络.局部社区发现作为一种无需知道网络的全局结构、仅通过分析给定节点的周围节点之间的关系即可找出给定节点所在社区的方法,在社会网络大数据分析中具有重要的应用意义.针对真实世界网络结构中个体间的相似关系是模糊的或不确定性的,提出了一种基于模糊相似关系的局部社区发现方法.首先,采用模糊关系来描述两个节点之间的相似关系,以节点对的相似度作为该模糊关系的隶属函数;然后证明了该关系是一种模糊相似关系,将局部社区定义为给定节点关于模糊相似关系的等价类,进而采用最大连通子图算法求得给定节点所在的社区.分别在仿真网络和真实网络上进行了实验,实验结果表明,该算法能够有效地揭示出给定节点所在的局部社区,相比其他算法,具有更高的F-score.     

基于特征向量局部相似性的社区检测算法

社区的发现和分析是复杂网络结构和功能研究中的一个热点。目前广泛应用的社区划分算法存在时间复杂度过高、社区核心数量无法准确量化、划分精度不高等问题。文中提出了一种基于特征向量局部相似性的社区检测算法ELSC。该算法首先计算网络中每个节点的特征向量中心性,在此基础上提出了特征向量局部相似性(ELS)和特征向量吸引性(EA)指标。ELS指标表示节点之间的相似性,用来形成初始社区,在同一个社区内部节点之间的相似性较高,在不同社区节点之间的相似性较低;EA指标同时考虑了局部相似性和特征向量中心性的占比,表示节点之间的吸引性,用来优化初始社区,并在此基础上完成网络的社区划分。该算法由最值确定节点,避免了节点数量阈值不确定的问题。在7个真实网络上将所提算法与6种知名算法的模块度和标准化互信息两个指标进行综合比较,结果表明,该算法具有良好的准确性,并且具有较低的时间复杂度。     

基于多层节点相似度的社区发现方法

社区发现是复杂网络研究中的一项重要研究内容,基于节点相似度的凝聚方法是一种典型的社区发现方法。针对现有节点相似度计算方法中存在的不足,提出一种基于多层节点的节点相似度计算方法,该方法既可以有效地计算节点之间的相似度,又可以解决节点相似度相同时的节点合并选择问题。进一步基于这种改进的节点相似度计算方法和团体之间的连接紧密度度量准则构建社区发现模型,并在真实世界的网络上进行社区发现实验。与GN算法、Fast Newman算法和改进的标签传播算法的实验结果相比,该模型可以更加准确地找到各个社区的成员。     

基于随机游走的改进标签传播算法

社区发现是挖掘社交网络隐藏信息的一个有用的工具，而标签传播算法（LPA）是社区发现算法中的一种常见算法，不需要任何的先验知识，且运行速度快。针对标签传播算法有很强的随机性而导致的社区发现算法结果不稳定的问题，提出了一种基于随机游走的改进标签传播算法（LPARW）。首先，根据在网络上进行随机游走确定了节点重要性的排序，从而得到节点的更新顺序；然后，遍历节点的更新序列，对每个节点将其与排序在其之前的节点进行相似性计算，若该节点与排序在其之前的节点是邻居节点且它们之间的相似性大于阈值，则将排序在其之前的节点选为种子节点；最后，将种子节点的标签传播给其余的节点，得到社区的最终划分结果。将所提算法与一些经典的标签传播算法在4个有标签的网络和5个无标签的真实网络上进行比较分析，实验结果表明所提算法在标准互信息（NMI）、调整兰德系数（ARI）和模块度等经典的评价指标上的性能均优于其余对比算法，可见该算法具有很好的社区划分效果。