基于分组的动态加权网络关键节点算法研究

论文摘要

关键节点的测度问题本质上可归结为节点重要性测度及排序问题,该问题的有效解决有助于指导金融、电力、供应链、互联网等多方面的应用开展。而当前的研究大多针对无权、静态社会网络,在动态加权网络中的研究则比较少,显然进一步的研究是很有必要的。考虑到现实中单一因素测度节点重要性的局限性,给出了等效点权概念,一方面,点权作为一个基本的因素,它的确在局部上反映了节点的重要程度,另一方面,点权对其它节点的扩散效应,距离越远,影响越小,考虑到全局网络中节点的点权对中心节点影响,给出了基于等效点权的节点重要性排名方法,从而进一步提高了测度结果的准确性。考虑到现实加权网络的社区结构特性,给出了先分组后计算的思想,经典的社区分组算法能在无权图中有很好的效果,在加权图中却与预期的结果有一些差距,为了解决该问题,给出了基于距离增量矩阵的分组概念模型,考虑到两社区在合并前后路径矩阵的变化情况,给出了评价分组质量的距离增量指标,针对直接计算路径矩阵时间代价大的不足,采用了动态更新的方式来缩短计算时间,从而使该分组测度算法能适用于更大规模的网络。考虑到现实加权网络随时间变化的动态特性,针对其中的路径矩阵给出了动态式更新的方法,针对加入节点、删除节点、边权的变化等情况给出了不同的更新方法,大大缩短了计算开销,同时给出了一种计算节点间最短路径的新方法,使其能更好的满足实际动态网络应用的需求。最后,综合以上三方面,给出了基于距离增量矩阵分组求节点重要性的动态算法（a dynamic algorithm to calculate the importance of nodes based on the distance- increment matrix grouping,IDD）,其主要包括数据分组的初始化、数据加入后的分组选择、距离矩阵的更新和节点重要性计算四方面内容,结合C-DBLP数据并通过实验验证了该算法的可行性和有效性。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 研究背景
• 1.2 国内外概况
• 1.3 主要研究工作
• 2 节点重要性测度方法概述
• 2.1 图的拓扑结构与节点重要性测度
• 2.2 动态网络与复杂网络
• 2.3 已有测度节点重要性方法
• 2.4 本章小结
• 3 分组求节点重要性的动态算法
• 3.1 影响节点重要性的因素
• 3.2 等效点权求节点重要性方法
• 3.3 距离增量矩阵方法
• 3.4 动态路径矩阵方法
• 3.5 IDD 节点重要性排名算法
• 3.6 本章小结
• 4 实验分析
• 4.1 数据的模型化
• 4.2 算法实验
• 4.3 本章小结
• 5 结束语
• 5.1 全文总结
• 5.2 进一步的研究工作
• 致谢
• 参考文献
• 附录 攻读硕士学位期间参加的项目