基于随机游走的Graphlet采样算法优化

摘要

网络的局部结构特征能够用于解决网络研究方面的问题。由三到五个节点组成的基本结构单元，以及它们的出现频率，在生物医学、化学、社交领域中有重要的应用。它们的频率可以用于分子网络建模、蛋白质功能分析、追踪互联网热点以及识别突发事件等方面。这些基本结构单元称为Graphlet，它们出现的频率叫做Graphlet频率分布。由于Graphlet频率分布的计算复杂度高，在分析大规模的网络时，需要通过采样减少输入规模，降低计算量。 现有的采样算法是串行执行的，在生成Graphlet频率分布时，没有利用计算机的并行处理能力。论文通过多个采样过程并行运行、相互协作，实现了并行化；现有的采样算法没有判断采样过程是否收敛，论文设计了通过实时检测采样过程生成的样本序列，判断采样过程是否收敛的收敛判定算法；在采样算法的实现中，设计了更加合适的数据结构和与之匹配的算法，减少了内存占用，提高了运行效率。 通过分析采样序列的统计学特征，证明了新的采样算法能够无偏地得到Graphlet的频率分布；在样本数量增加时，收敛判定方法能够指示样本序列的特征与总体特征越来越接近，证明了收敛判定算法是有效的。测试表明，并行化后的采样算洼缩短了采样时间，当并行度增加一倍时，采样时间最多能减少43%。

目录

第一个书签之前

摘 要

Abstract

1. 绪论

1.1. 研究背景与意义

1.2. 国内外研究现状

1.2.1. Graphlet的由来

1.2.2. Graphlet频率分布

1.2.3. 图的三角形计数

1.2.4. 采样算法

1.2.5. 随机游走的并行化

1.3. 本文研究内容

1.4. 论文结构

2. Graphlet采样算法的分析与改进

2.1. Graphlet数学定义

2.2. 采样算法的比较与选择

2.3. Graphlet随机游走的状态转移矩阵

2.3.1. Graphlet邻居关系的建立

2.3.2. 邻居关系算法的优化

2.3.3. 随机游走的数学约束条件满足性证明

2.4. 随机游走算法的参数调整

2.5. 采样过程的收敛判定

2.6. 采样过程的并行化

2.6.1. 独立的并行随机游走

2.6.2. 非独立的并行随机游走

2.7. Graphlet类别判断

2.8. 本章小结

3. 并行随机游走算法的实现

3.1. 采样算法总体设计

3.2. 数据结构的设计与优化

3.3. Graphlet邻居搜索算法的实现

3.4. 随机游走算法的实现

3.4.1. MH算法的实现

3.4.2. 加权随机游走的实现

3.5. 游走算法并行化的实现

3.6. Graphlet种类判断的实现

3.7. 收敛判定的实现

3.8. 本章小结

4. 测试与结论

4.1. 测试环境

4.2. 样本均匀分布验证

4.3. 收敛判定的有效性验证

4.4. 并行化采样算法的精度

4.4.1. 独立并行采样方案的采样精度

4.4.2. 非独立并行采样方案的采样精度

4.5. 并行化采样算法的时间消耗

4.6. 本章小结

5. 总结与展望

致 谢

参考文献

附录 攻读硕士学位期间参加的主要科研项目