基于节点相似性的社区发现算法研究

论文摘要

现实生活中许多系统可以表示成复杂网络,如社会关系网、蛋白质互作用网、交通运输网等,复杂网络分析在社会学,生物学等领域有着广泛的应用。社区结构是复杂网络的重要特征之一,即一个网络可以分成若干个社区,每个社区内部的节点之间连接相对紧密,各社区间的节点连接相对稀疏。设计有效的社区发现算法可以发现社会网络中的社区结构、生物网络中的蛋白质功能模块等,有助于深入研究各种类型复杂网络的功能模块及其演化特征,对准确地理解并分析复杂系统的拓扑结构及动力学特性具有十分重要的理论意义和应用价值。针对复杂网络中的社区发现问题,本文主要包括以下两方面内容:（1）对网络中节点间的相似性进行合理度量是社区发现的核心问题。针对此,给出了一种基于节点间点不重复路径的节点相似性指标,以此为基础,提出了一种基于节点间路径度量的图聚类算法（a graph clustering algorithm based on local paths between nodes in complex networks,PGC）,包括节点相似性计算、中心节点选择、初始社区划分和社区优化四个主要过程。采用节点间点不重复路径对节点相似性进行度量,消除了由大度节点引起的较多的点重复路径对节点相似性度量的影响,提高了对大度节点邻域中节点的划分能力。通过与一些经典算法在真实网络以及人工网络数据集上的实验比较分析,结果表明算法PGC在NMI、ARI等方面均表现出良好的性能。（2）针对标签传播社区发现算法在节点更新顺序及标签传播过程中存在较大随机性而导致划分结果稳定性差的问题,提出一种基于标签传播的两阶段社区发现算法（a two-stage community detection algorithm based on label propagation,LPA-TS）,在第一阶段,通过节点参与系数确定更新顺序,并在标签传播过程中依据节点之间的相似性更新节点标签,得到初始社区划分。将社区看作节点,社区间连边数作为边权重,得到社区关系网络;在第二阶段,将不符合弱社区定义的初始社区与连边最多的相邻社区合并,再按照社区参与系数由低到高的顺序合并初始社区提升社区发现质量。LPA-TS减少了传统LPA方法在节点更新和标签传播过程的随机性。通过与一些经典算法在8个真实网络及不同参数下LFR benchmark人工网络数据集上的实验比较表明LPA-TS表现了良好的稳定性,在NMI、ARI、模块性等方面表现良好。

论文目录

文章来源

类型: 硕士论文

作者: 车晨浩

导师: 郑文萍

关键词: 复杂网络,社区发现,相似性度量,标签传播

来源: 山西大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,计算机软件及计算机应用

单位: 山西大学

分类号: O157.5;TP301.6

DOI: 10.27284/d.cnki.gsxiu.2019.000095

总页数: 67

文件大小: 15184K

下载量: 139

相关论文文献

• [1].认知无线电中基于可信度的感知节点集选择[J]. 应用科学学报 2009(06)
• [2].认知无线电中一种感知节点集自适应选择算法[J]. 信号处理 2010(06)
• [3].无线传感器网络中一种关键节点集轮换算法[J]. 系统仿真学报 2010(06)
• [4].收缩邻居节点集方法求解有向网络的最大流问题[J]. 模式识别与人工智能 2013(05)
• [5].基于加权K-阶传播数的节点重要性[J]. 物理学报 2019(12)
• [6].PEAK:一种面向弱节点集群的并行可演化管理框架[J]. 计算机工程与科学 2013(11)
• [7].基于节点速度和能量的MPR节点集选择[J]. 传感技术学报 2019(06)
• [8].基于节点影响力的标签传播社区检测算法[J]. 重庆理工大学学报(自然科学) 2018(07)
• [9].基于节点重要性评价的京津冀雾霾污染网络研究[J]. 环境科学学报 2018(06)
• [10].一类新节点集上的Newman有理插值逼近[J]. 安徽理工大学学报(自然科学版) 2015(02)
• [11].基于深度可调节节点的水声网络部署优化算法[J]. 系统工程与电子技术 2019(01)
• [12].动态网络中稳定社区发现[J]. 小型微型计算机系统 2015(09)
• [13].多节点集群P2P系统研究[J]. 计算机科学 2010(02)
• [14].复杂网络基于最小驱动节点的能控性优化（英文）[J]. 系统科学与数学 2019(05)
• [15].基于网络拓扑结构的重要节点发现算法[J]. 运筹与管理 2019(07)
• [16].基于节点属性的重叠社区发现算法改进[J]. 通信技术 2018(01)
• [17].一种融合节点先验信息的图表示学习方法[J]. 软件学报 2018(03)
• [18].复杂网络中Top-k影响力节点的识别算法[J]. 计算机科学与探索 2018(06)
• [19].基于种子节点集的社区层次结构发现算法[J]. 信息工程大学学报 2016(03)
• [20].网络科学中相对重要节点挖掘方法综述[J]. 电子科技大学学报 2019(04)
• [21].引入信任度传递机制的影响力最大化节点挖掘[J]. 西南科技大学学报 2019(03)
• [22].一种复杂网络中节点安全重要性排序的度量方法[J]. 信息安全学报 2019(01)
• [23].异构WSNs中节点稳定匹配的覆盖空洞修复优化算法[J]. 传感技术学报 2019(06)
• [24].无线传感器网中一种支持固定路由结构的协作机制[J]. 通信技术 2008(08)
• [25].软件网络中关键函数节点的识别方法[J]. 燕山大学学报 2018(05)
• [26].基于节点集计算能力差异的Hadoop自适应任务调度算法[J]. 计算机应用 2016(04)
• [27].基于有限节点集的网络毁伤最大化问题研究[J]. 控制与决策 2020(04)
• [28].面向选择推荐节点的P2P网络信任模型[J]. 计算机工程与科学 2018(06)
• [29].采用影响力节点集扩展的局部社团检测[J]. 西安交通大学学报 2016(04)
• [30].PMC模型下网络故障的节点可诊断研究[J]. 计算机应用研究 2019(11)

标签：复杂网络论文;  社区发现论文;  相似性度量论文;  标签传播论文;