论文部分内容阅读
如今，我们对现实网络的研究日益广泛，如蛋白质相互作用网，社会联系网，英特网等。很多情况下我们只对这些网络中的部分内容有所了解和利用。即使我们可以得到完整的网络信息，只对整体网络中的一部分进行研究也更为“经济”。为了得到完整网络的子网，我们以随机节点抽样和随机连边抽样等方法对整体网络进行抽样。当随机节点和随机连边抽样存在一定的偏差时，寻找一种更为准确的抽样策略就成为了重要的研究课题。许多情况下，探索网络的过程类似于随机游走的过程，因此，研究、刻画不同的随机游走抽样策略对网络抽样效果的影响就十分重要。 本文中，我们在已有的无限制的随机游走（URW）的基础上发展出选择种子节点的随机游走（CSNRW），及不返回上一步的随机游走（NRRW），并探讨了这三种类型的随机游走在加权的美国航空网，ER，BA和WS网络中的抽样情况。通过模拟研究了它们的抽样效率、度分布、抽样子网的平均度和平均聚类系数随抽样步数的改变，得到了一系列的相关结果：三类抽样策略在具有相同尺度和平均节点度的网络上具有不同的抽样效率和阈值；这些网络的子网度分布都只是略微的偏向更大的节点度；通过对和变化曲线的观察，发现子网的和可以在有限的抽样步数内回到原值，并且容易在加权网中被高估。我们的工作也揭示了，若一个节点具有大的节点度，则与它相邻的节点间更易具有较少的连接。