基于图结构特征的Top-k结构洞发现算法及其优化研究

论文摘要

信息网络给生产生活带来了巨大的信息资源,但随着研究和应用的深入,以常规思维方式和分析视角来研究处理这些庞大而又复杂的信息网络,其难度和挑战性不言而喻。结构洞作为反映社会网络节点关键性、研究网络信息传播扩散特性以及社区发现的重要理论。其新颖的研究视角对于社交网络影响力分析、设备网络薄弱节点检测、舆情控制、企业或个人跨界合作优势互补、以及逆向应用的企业竞争力、品牌影响力提升等有着至关重要的作用。本文从图论和网络拓扑结构的研究思想出发,主要基于最短路径增量（SPIG）、连通分量数量（NCC）、节点数方差（VAR）等属性信息对结构洞发现算法进行研究分析,设计并实现了两个针对复杂网络的结构洞发现算法,分别是SNV算法和基于中介中心性优化过滤的算法SNV-BC。首先,对现有基于最短路径增量的结构洞发现算法进行深入研究和分析后,根据其缺陷和不足,增加补充属性并重新定义网络模型,提出新的结构洞发现算法。其次,针对上述算法考虑因素较多,导致时间复杂度较高的问题,结合算法原理和实验数据的综合分析后,提出了新的优化过滤解决办法。最后,利用NDCG评价算法和SIR信息扩散模型等经典的结构洞关键节点评估方法,在不同类型的多个网络数据集中对所提出算法的有效性和效率进行了验证。并利用Gophi、Networkx等可视化技术和工具对实验结果进行可视化发现和分析。通过全面的实验测试,本文所提出的算法SNV-BC在对复杂网络的分析计算中,兼顾效率的同时能够体现出较高的适应性、准确性。同时算法本身在权值、交互度等方面还体现出较高的扩展性。

论文目录

• 摘要
• Abstract
• 第一章 绪论
•   1.1 研究背景和研究意义
•   1.2 国内外研究现状
•     1.2.1 国内外相关文献统计情况
•     1.2.2 结构洞理论的发展
•   1.3 研究的内容及工作创新成果
•     1.3.1 研究内容
•     1.3.2 本文主要工作成果及特色创新
•     1.3.3 论文组织结构
• 第二章 关键技术
•   2.1 NDCG排序评估评价方法
•   2.2 SIR传染病扩散模型
•   2.3 LFR benchmark网络合成模型
•   2.4 数据可视化技术
•   2.5 本章小结
• 第三章 基于图结构特征分析的Top-k结构洞发现算法SNV
•   3.1 理论基础
•     3.1.1 结构洞定义
•     3.1.2 网络模型定义
•     3.1.3 问题描述和属性说明
•   3.2 Top-k结构洞发现算法SNV
•     3.2.1 算法主要思想
•     3.2.2 算法伪代码
•     3.2.3 算法时间复杂度
•     3.2.4 网络数据集简单优化预处理
•   3.3 实验结果及分析
•     3.3.1 实验环境设定及实验数据
•     3.3.2 实验结果分析
•   3.4 本章小结
• 第四章 针对SNV时间复杂度优化的过滤算法SNV-BC
•   4.1 问题提出
•   4.2 理论基础
•   4.3 基于中介中心性的过滤算法SNV-BC
•     4.3.1 算法主要思想
•     4.3.2 算法伪代码
•     4.3.3 算法时间复杂度
•   4.4 实验及结果分析
•     4.4.1 实验环境设定及实验数据
•     4.4.2 实验结果分析
•   4.5 本章小结
• 第五章 总结与展望
•   5.1 后续工作展望
•     5.1.1 算法优化再完善
•     5.1.2 研究方向展望
•   5.2 全文工作总结
• 参考文献
• 攻读硕士学位期间完成的科研成果
• 致谢

文章来源

类型: 硕士论文

作者: 朱江

导师: 孔兵

关键词: 结构洞,信息扩散,最短路径增量,中介中心性

来源: 云南大学

年度: 2019

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

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

单位: 云南大学

分类号: TP301.6;O157.5

总页数: 64

文件大小: 4043K

下载量: 30