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

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

利用改进蚁群算法的重叠社团检测分析方法

针对重叠社团检测准确率提升问题,提出了一种基于改进蚁群算法的新型重叠社团检测算法。该算法包含位置初始化、运动和后处理三个阶段,分别通过初始位置识别与标签列表存储、基于节点间相似度的启发式信息重定义、合作保持标签列表等方式,使算法在合成数据集与现实世界数据集中的重叠社团与节点检测方面具有更好的性能。实验结果表明,在合成网络与现实世界网络平台上使用不同检测算法,所提出的方法对重叠社团与重叠节点的检测准确率较传统检测方法来说更高,因而对重叠社区检测问题求解与理解网络功能结构具有重要的参考与借鉴意义。     

基于链路标签传播的重叠社团发现算法

为挖掘复杂网络中的重叠社团结构,在标签传播算法的基础上,从链路的角度出发,提出一种新的标签更新策略。考虑不同邻居对链路标签贡献值的不同特点,使其更新过程更加快速,克服当前基于节点的标签传播算法需要指定节点所属社团个数的缺陷,在无需人工干预的情况下得到稳定的重叠社团结构。将该算法分别应用于人工网络和真实的社会网络中,实验结果表明,该算法能够快速、有效地挖掘稳定的重叠社团结构。     

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

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

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

说话者-侦听器标签传播算法（Speaker-Listener Label Propagation Algorithm,SLPA）以标签传播算法为基础,通过Speaker和Listener互动的动态过程来发现网络中的重叠社团,时间复杂度近似线性,但在标签传播过程中存在随机性,并且在应用到大规模网络时节点标签初始化需耗费大量的资源。针对以上问题,通过改进SLPA设计了一种基于标签传播的重叠社团发现算法（Overlapping Community Division Algorithm Based on Label Propagation,LP-OCD）。该算法在每个节点存储器初始化标签之前,利用K-Shell分解算法对网络进行预处理,去除边缘层节点;在标签更新阶段,通过改进Speaking和Listening策略来降低算法的随机性;后处理阶段边缘层节点的标签由其邻居节点信息决定。实验结果表明,LP-OCD算法不仅具有近似线性的时间复杂度,而且显著提高了所发现重叠社团的质量。     

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

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

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

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

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

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

一种基于局部回路的标签传播改进算法

社区发现是复杂网络分析领域的重要研究内容。针对标签传播算法中标签传播的随机性问题,提出一种基于局部回路的标签传播改进算法,即当节点邻居中标签出现频率存在多个最高时,不是随机选择一个邻居的标签作为该节点的标签,而是选择与该节点构成最短局部回路的邻居标签作为该节点标签,避免了标签在社区之间的任意传播。最后,用真实网络进行测试,结果表明,与传统的标签算法相比,提出的改进算法使社区划分结果得到了提高。     

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

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

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

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

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

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

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

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

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

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

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

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

基于图嵌入和多标签传播的重叠社区检测算法

为进一步优化重叠社区检测算法,提出了一种新的基于度和节点聚类系数的节点重要性定义,按照节点重要性降序更新节点,固定节点更新策略,提高社区检测的稳定性。在此基础上,提出了一种基于图嵌入和多标签传播的重叠社区检测算法（overlapping community detection based on graph embedding and multi-label propagation algorithm,OCD-GEMPA）。该算法结合node2vec模型对节点进行低维向量表示,构建节点之间的权重值矩阵,根据权重值计算标签归属系数,据此选择标签,避免了随机选择问题。在真实数据集和人工合成数据集上对该算法进行实验验证,实验结果表明,与其他重叠社区检测算法相比,OCD-GEMPA在EQ和NMI这两个指标都有明显提升,具有更好的准确性和稳定性。