一种基于局部随机游走的标签传播算法

摘要：

社区结构是复杂网络的重要特征之一,识别网络中不同功能的社区对理解复杂网络特性具有重要作用.基于标签传播的社区发现算法通常以节点的直接邻居作为邻域更新标签,可能无法准确发现社区结构或导致得到的社区划分结果不稳定.针对此问题,提出了一种基于局部随机游走的标签传播算法(Local Random Walk Based Label Propagation Algorithm,LRW-LPA),利用节点的k步邻域内局部重要性指标选择重要性最低的节点作为起始节点,进行带重启的局部随机游走以确定起始节点的局部邻域;选择此局部邻域范围内出现次数最多且影响值最大的标签来更新起始节点标签.LRW-LPA采用带重启的局部随机游走过程能更准确地确定节点的合适邻域范围,提高了算法的稳定性.与LPA,BGLL,Infomap,Leiden,Walktrap等经典社区发现算法在12个真实网络和12个人工构造网络上的比较实验表明,LRW-LPA算法在标准互信息(NMI)、调整兰德系数(ARI)和模块度(Q)等方面表现良好.

关键词：复杂网络、聚类、社区发现、标签传播、局部随机游走

所属期刊栏目：49

分类号：TP391(计算技术、计算机技术)

资助基金：国家自然科学基金;国家自然科学基金;国家自然科学基金;国家自然科学基金;山西省工程项目

在线出版日期：2022-10-20（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：103-110