学位论文 > 优秀研究生学位论文题录展示

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

作　者: 钟开
导　师: 李玉华
学　校: 华中科技大学
专　业: 计算机应用技术
关键词: 关键节点动态加权网络等效点权分组距离增量矩阵
分类号: TP393.09
类　型: 硕士论文
年　份: 2011年
下　载: 58次
引　用: 0次
阅　读: 论文下载

内容摘要

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

全文目录

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

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

内容摘要

全文目录

相似论文