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

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

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

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

基于圈结构的LPANNI优化算法

针对重叠社区发现准确率提升问题,提出了一种基于圈结构的LPANNI优化算法CLPANNI（cycle label propagation algorithm with neighbor node influence）。该算法通过挖掘节点的最小圈信息,依据圈比指标衡量节点的重要性并按升序进行标签更新,增加了标签传播过程的稳定性,按照邻居节点影响力大小加权接收邻居节点传递的标签。与四种基准算法在NMI_LFK、NMI_MGH、MOV指标下进行测试比较,CLPANNI算法在社区发现准确率方面表现较好。实验结果表明,该算法能够有效探测网络重叠社团结构,发现网络的紧密子团,识别的社团分布与真实网络结构更为接近。     

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

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

融合LeaderRank和标签传播的社区发现算法

由于社会网络的日益复杂,具有线性时间复杂度的标签传播算法越来越被广泛的运用,然而在标签传播过程中存在随机性,致使社区划分不稳定.因此,对节点标签初始化、节点更新顺序和节点标签传播选择过程这三个方面改进,提出一种稳定性较高的标签传播算法.该方法引入LeaderRank算法计算节点影响力,在此基础上选取关键节点并为这些关键节点赋予标签,节点更新顺序依据于节点影响力由高到低更新,在标签传播过程中考虑节点之间的传播能力.采用真实网络数据进行实验,和传统算法相比,论文算法在相关质量指标上均有优势.     

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

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

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

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

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

说话者-侦听器标签传播算法（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算法不仅具有近似线性的时间复杂度,而且显著提高了所发现重叠社团的质量。     

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

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

基于标签传播能力的改进LPA算法

随着网络规模的不断增大,在时间复杂度上具有明显优势的标签传播算法受到广泛关注,但是其内在机制存在不确定性和随机性,导致社团发现结果不够准确和稳定。为此,提出一种新的改进标签传播算法。在K-shell分解算法的基础上,构造节点重要性计算方法,利用节点重要性分析标签传播算法中的标签传播能力,通过节点重要性排序和标签传播能力制定新的标签更新策略,得出最终的社团划分结果。在人工网络和真实网络上的实验结果表明,该算法有较高的准确性和稳定性。     

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

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

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

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

基于时间加权的重叠社区检测算法研究

随着网络结构的不断扩大和日益复杂, 重叠社区发现技术对挖掘复杂网络深层潜在结构具有重要意义. 本文提出一种基于时间加权的重叠社区检测算法. 该方法考虑了用户兴趣的时间因素, 构建带有时间加权链接的用户-用户图. 接着, 基于网络节点的影响力计算用户全局相似度, 在此基础上通过计算节点的中心度作为度量节点对社区结构影响力的重要性指标, 从而提出一种社区中心点的选取方法. 最后, 通过效用函数的迭代计算实现重叠社区检测. 利用人工网络和真实网络对提出的算法进行验证, 实验结果表明: 相对于传统的社区发现方法, 该算法在社区发现质量和计算效率方面都优于许多已有重叠社区发现算法.     

基于多标签传播机制的蛋白质相互作用网络功能模块检测*

鉴于多标签传播算法在发现社会网络的社区结构研究上具有快速、高效的求解能力,提出融合多源蛋白质生物学知识的基于多标签传播机制的蛋白质相互作用(PPI)网络功能模块检测算法.首先,结合PPI网络功能信息和结构信息初始化节点的标签.然后,利用基因表达数据描述蛋白质间的共表达性,依据共表达性构建标签集合,从中选择标签以实现标签在节点间真实可靠的传播.最后,将具有相同标识符的节点划分到同一功能模块中,获得最终结果.实验表明文中算法不仅具有良好的时间性能,而且在检测精度上也具有一定的竞争性.     

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

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

一种新的基于标签传播的复杂网络重叠社区识别算法

针对现有基于标签传播的复杂网络重叠社区识别方法所存在的社区识别精度不稳定,以及随机性较强等缺陷,提出一种新的基于标签传播的复杂网络重叠社区识别算法NOCDLP(a novel algorithm for overlapping community detection based on label propagation).该算法首先搜索网络中若干以度较高节点为中心的完全子图,并以这些完全子图为起点进行标签传播;其次通过分析节点与社区连接强度以及社区接纳某节点后的社区内部连接紧密度情况给出节点归属社区强度函数,以此作为标签传播的依据提高社区的识别精度;再次,在标签传播过程中,NOCDLP算法设置标签传播控制标记,以避免标签传播算法随机性较强的缺陷;最后,在已形成的社区中通过整理重叠节点获得更准确的重叠社区结构.算法在人工网络与真实网络中完成测试,同时与多个经典算法进行对比分析,实验结果验证了NOCDLP算法是有效的、可行的.     

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

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