复杂网络重要节点排序算法

发布时间：2017-08-07 09:08

  本文关键词：复杂网络重要节点排序算法

  更多相关文章： 复杂网络 重要节点 节点相似度 SRank算法 结构洞 W-Burt算法

【摘要】：随着复杂网络的研究不断深入,越来越多学者关注于研究少量重要节点对整个网络功能所产生巨大作用,而快速有效地挖掘复杂网络中的重要节点成为现今研究的热点。网络规模和结构瞬息万变,快速有效地挖掘网络中的重要节点对各个领域都有重要的现实意义。本文针对复杂网络节点重要度排序的研究工作内容如下:(1)针对现有无权网络和加权网络经典的节点重要度排序方法进行了研究,详细介绍了针对无权网络的排序方法:度中心性、接近中心性、介数中心性、Burt、PageRank以及LeaderRank算法,并比较每种方法的优缺点。详细介绍了加权网络的排序方法:加权度中心性、加权接近中心性、加权PageRank、加权LeaderRank算法,并比较每种方法的优缺点。(2)针对无权网络提出了节点相似度的概念,用于衡量节点间相互影响的程度,结合LeaderRank算法,并充分考虑节点对相互作用存在差异性从而提出了SRank算法。不同于经典的节点重要度排序方法,SRank算法充分考虑了节点局部特征和全局特征,更符合实际网络,其排序结果更为准确,而且SRank算法不仅适用于无向网络,也适用于有向网络。(3)采用SIR传播模型定义得到无权网络节点的传播重要度。通过在五个真实网络的仿真,采用排序结果与节点传播能力的相关性图、相关性指数以及重要节点传播效果图的三种评价方法,从不同角度说明,SRank在不仅在挖掘重要节点表现优异,在整个节点重要度排序中,都优于其他算法,且SRank算法时间复杂度低,适用于大规模网络重要节点挖掘。(4)针对加权网络引入了结构洞的概念,考虑节点的二层邻接拓扑结构定义了节点维持连边关系的花销,提出W-Burt算法。W-Burt算法综合考虑节点的桥接重要度和节点中心性,符合现实网络中,即使度值很小的桥接点对信息在网络中的扩散起到巨大的推动作用,使得排序结果更为准确。(5)采用SI传播模型定义得到加权网络节点的传播重要度。通过在三个真实网络的仿真,采用排序结果与节点传播能力的相关性图、相关性指数以及重要节点传播效果图的三种评价方法,从不同角度说明,W-Burt在整个节点重要度排序中,都优于其他算法,且W-Burt算法时间复杂度较低可用于大规模网络。
【关键词】：复杂网络 重要节点 节点相似度 SRank算法 结构洞 W-Burt算法
【学位授予单位】：南京邮电大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5
【目录】：

• 摘要4-5
• ABSTRACT5-9
• 专用术语注释表9-11
• 第一章 绪论11-16
• 1.1 课题研究背景与意义11-12
• 1.2 国内外研究现状12-14
• 1.3 本文主要内容14-16
• 第二章 复杂网络节点重要度相关理论16-31
• 2.1 图的基本理论16-19
• 2.2 复杂网络的相关概念19-21
• 2.3 几种无权网络重要节点排序算法21-25
• 2.3.1 度中心性21
• 2.3.2 介数中心性21-22
• 2.3.3 接近中心性22
• 2.3.4 Burt算法22-23
• 2.3.5 PageRank算法23-24
• 2.3.6 各算法对比分析24-25
• 2.4 几种加权网络重要节点排序算法25-28
• 2.4.1 含权的度中心性25-26
• 2.4.2 含权的接近中心性26
• 2.4.3 含权的PageRank算法26-27
• 2.4.4 含权的LeaderRank算法27-28
• 2.4.5 各算法对比分析28
• 2.5 评价方法28-30
• 2.5.1 SI模型和SIR模型28-30
• 2.5.2 相关性系数30
• 2.6 本章小结30-31
• 第三章 SRank无权网络重要节点排序算法31-58
• 3.1 LeaderRank算法31-33
• 3.2 节点相似度33-34
• 3.3 SRank算法模型和复杂度分析34-36
• 3.4 算法仿真与分析36-57
• 3.4.1 仿真数据36
• 3.4.2 排序结果与分析36-46
• 3.4.3 传播动力学模型评价算法有效性46-52
• 3.4.4 相关性系数52-53
• 3.4.5 重要节点传播效果53-57
• 3.5 本章小结57-58
• 第四章 基于结构洞的加权网络重要节点排序算法58-73
• 4.1 N-Burt算法介绍58-59
• 4.2 W-Burt算法模型与复杂度分析59-62
• 4.3 算法仿真与分析62-72
• 4.3.1 仿真数据62
• 4.3.2 排序结果与分析62-65
• 4.3.3 传播动力学模型评价算法有效性65-67
• 4.3.4 相关性系数67-68
• 4.3.5 重要节点传播效果68-72
• 4.4 本章小结72-73
• 第五章 总结与展望73-75
• 参考文献75-78
• 附录1 攻读硕士学位期间撰写的论文78-79
• 附录2 攻读硕士学位期间申请的专利79-80
• 致谢80

【相似文献】

中国期刊全文数据库 前5条

1 张凤林,郭波,刘卫华,王正明;有限需求量的网络路径优选研究[J];系统工程;2004年11期

2 任晓龙;吕琳媛;;网络重要节点排序方法综述[J];科学通报;2014年13期

3 戴技才;宗会明;;基于复杂网络聚类的最优选址模型[J];地理科学;2013年02期

4 曾庆立;李丽华;唐圣学;;基于神经网络路径规划的硬件设计[J];吉首大学学报(自然科学版);2007年06期

5 ;[J];;年期

中国重要会议论文全文数据库 前1条

1 王旭坪;李小龙;阮俊虎;;不确定信息下应急模糊网络路径选择研究[A];第五届（2010）中国管理学年会——管理科学与工程分会场论文集[C];2010年

中国重要报纸全文数据库 前10条

1 Jeremy Littlejohn 编译 沈建苗;给过热的“扁平网络”泼泼冷水[N];计算机世界;2012年

2 特约撰稿 张琦;网络升级也适用“交规”[N];中国电脑教育报;2006年

3 ;用永久TAP应对复杂基础设施[N];网络世界;2007年

4 本期专家：刘晓辉 王春海;专家坐堂之网络篇[N];电脑报;2004年

5 钟凯文;虚拟通道能省钱[N];中国计算机报;2001年

6 ;CCE网络问答[N];中国电脑教育报;2005年

7 黄祝淼;移花接木实现会考系统网络交卷[N];中国电脑教育报;2003年

8 本期专家：刘晓辉 王春海;专家坐堂之网络篇[N];电脑报;2003年

9 杨阿昭;性能不稳 谁在作怪[N];中国计算机报;2003年

10 谢永亮;日本“网络防卫队”获正名[N];中国国防报;2014年

中国博士学位论文全文数据库 前1条

1 周曜;移动Ad Hoc网络路径压缩及安全技术研究[D];南京理工大学;2010年

中国硕士学位论文全文数据库 前10条

1 宋翔宇;基于WebRTC的网络加速服务关键技术研究与实现[D];华南理工大学;2015年

2 Mawagali, Palme;复杂网络中的强连接研究[D];哈尔滨工业大学;2016年

3 朱梓嫣;复杂网络重要节点排序算法[D];南京邮电大学;2016年

4 辛强伟;复杂网络上的信息传播[D];西安理工大学;2007年

5 谢小亮;基于信息对话的网络路径算法研究[D];西安科技大学;2013年

6 殷文杰;MANET网络路径稳定性及增强策略的研究[D];复旦大学;2009年

7 刘岳;基于GIS的长沙市大河西先导区绿道网络建设[D];湖南大学;2011年

8 刘彦君;异质网络的目标价值评估与脆弱性分析研究[D];国防科学技术大学;2013年

9 赵晟;城乡信息一体化的网络路径研究[D];广西大学;2013年

10 王战国;基于S-RTT策略的BitTorrent文件共享模型[D];湖南大学;2008年

，

本文编号：633836