大规模网络中抽样策略与应用研究

摘要

在复杂网络科学领域，人们通过对复杂网络的静态性质和动态特征的研究，提出了很多刻画复杂网络的指标和分析计算方法。然而，随着网络规模的不断增长，这其中有很多算法由于时空复杂度过高而不再适用于大规模网络上的计算。解决这个问题的方法之一便是利用网络抽样，在抽样数据集上以较低的资源消耗获得近似解。然而，现有的抽样算法大部分是基于单阶段抽样框架，往往难以精确刻画具有多重分布特性的复杂网络样本，无法满足具体领域研究的需要。本文在国内外相关研究基础上，针对大规模网络中的最短路径计算和大规模社交网络中的二元关系预测提出了网络抽样策略并设计了相应的快速算法。
　　最短路径是很多网络分析算法的基础，然而经典算法由于复杂度过高，往往无法处理大规模的网络。我们在大规模网络的最短路径计算中引入了中心点抽样，提出了有效计算最短路径的近似算法。本算法利用复杂网络中普遍存在的等级结构，抽取网络中的若干中心节点并与周围的邻居节点进行凝聚形成超级节点，构成新的上层网络，并在上层网络上重复中心节点与邻居节点的凝聚过程，直到最上层网络中的节点个数低于某一阈值时结束。最后利用Dijkstra算法精确地计算最上层网络中节点间的最短路径，并根据凝聚得到的等级网络结构来估计原始网络中节点之间的最短距离。实验结果表明我们的算法在精度和效率上都明显优于当前现有的算法。
　　在大规模社交网络中，用户之间的二元关系对社交网络分析有着很高价值。然而，随着网络规模的不断增加，用户之间的关系越来越复杂，也越来越隐蔽，如何高效准确地推断用户之间的二元关系逐渐成为现在的研究热点。在本文中，我们基于社会心理学理论提出了一种适合于大规模网络二元关系预测的算法。我们设计了分段训练框架将训练集分为两个子集，并在每个子集上分别训练SVM分类器。为了应对大规模训练数据带来的算法效率下降问题，我们引入了有效的抽样策略，利用不到原网络1％的数据样本，构建了具有高预测准确率的模型。我们与现有的算法以及它们的集成算法（AdaBoost）进行了比较，在公共标准数据集上的实验结果表明，我们的算法在大规模社交网络上的预测准确率更高。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪 论

1.1 研究背景

1.2 研究现状

1.3 研究内容

1.4 论文的结构安排

第二章 复杂网络与抽样基础

2.1 复杂网络研究内容

2.2 复杂网络的形式化表示

2.3 复杂网络基本拓扑性质

2.4 复杂网络上的关系与链路预测

2.5复杂网络抽样基础

2.6 本章小结

第三章 基于抽样的最短路径算法

3.1 中心节点抽样策略

3.2 基于节点抽样构建等级网络

3.3 基于节点抽样的最短路径计算

3.4 实验结果与分析

3.5 本章小结

第四章 基于抽样的二元关系预测算法

4.1 特征提取

4.2 两阶段抽样策略

4.3 基于抽样数据集的分段训练框架

4.4 实验结果与分析

4.5 本章小结

第五章 全文总结与展望

5.1 全文总结

5.2 展望

致谢

参考文献

攻读硕士学位期间取得的成果