大规模无标度网络生成算法研究

发布时间：2021-01-15 11:54

　　无标度网络是指顶点的度服从泊松分布的拓扑图。随着现代信息化的大量普及,大规模数据图越来越多地被应用到社交网络等现实场景,而现实世界的大部分数据图结构均满足大规模无标度网络的特性,因而可以通过对大规模无标度网络图数据的处理来验证图处理算法的性能。然而,现有大规模无标度网络图的构建方法存在效率低,扩展性差等问题。本文旨在研究大规模无标度网络图的高效生成方法,具体内容如下。首先,针对现有方法生成无标度网络所存在的低效性问题,本文提出一种基于BA模型的大规模无标度网络生成算法及相应的网络图数据存储结构RWBT。设计了相应的遍历策略以便提高算法效率,并对节点的删除操作优化处理,通过采用节点序号互换代替删除桶的操作从而降低更新树的频次,解决了在内存中处理大规模数据图时,重复遍历节点导致的低效性的问题。其次,本文提出一种基于RWBT结构扩展的RWKT索引结构,并进一步改善数据图的存储结构以及相应的节点遍历策略,通过对k叉树结构的内部节点进行排序,减少了冗余比较次数,进一步提升了算法的处理效率。最后,通过对本文讨论到的几种算法的不同参数进行设置,通过实验分别从结果质量、运行时间以及原子操作次数等多方面... 

【文章来源】：燕山大学河北省

【文章页数】：59 页

【学位级别】：硕士

【文章目录】：
摘要
abstract
第1章 绪论
    1.1 研究背景
    1.2 研究现状
    1.3 研究内容
    1.4 本文结构
第2章 基础知识概述
    2.1 无标度网络的相关概念
        2.1.1 小世界特性
        2.1.2 无标度特性
    2.2 现有图生成模型
    2.3 创建无标度网络的基本算法
        2.3.1 简单轮盘算法
        2.3.2 随机选择算法
        2.3.3 基于桶结构的轮盘算法
    2.4 本章小结
第3章 基于RWBT的网络生成算法
    3.1 问题分析
    3.2 基本思想
    3.3 基于RWBT结构的算法
        3.3.1 初始化无标度网络
        3.3.2 取样操作
        3.3.3 更新RWBT权值
        3.3.4 插入节点
        3.3.5 删除节点
        3.3.6 RWBT算法
    3.4 对RWBT算法的分析
    3.5 算法优化
    3.6 本章小结
第4章 基于RWKT的网络生成算法
    4.1 问题分析
    4.2 RWKT算法基本思想
    4.3 RWKT算法描述
    4.4 算法分析
    4.5 基于RWMST结构的优化算法
    4.6 本章小结
第5章 实验结果与分析
    5.1 引言
    5.2 实验环境
    5.3 数据集及评价标准
    5.4 性能比较与分析
        5.4.1 新增边数的影响
        5.4.2 初始节点个数的影响
        5.4.3 数据规模的影响
        5.4.4 分支数对算法影响
        5.4.5 内存增长情况比较
    5.5 本章小结
结论
参考文献
攻读硕士学位期间承担的科研任务与主要成果
致谢



本文编号：2978827