大规模网络上的随机行走过程研究+文献综述(3)
在这种假设下，BA模型的具体构造为：
1.增长：起初建立一个小型网络 （此网络有 个节点， 条边），逐渐将新的节点加入到网络，每一步只加入一个节点。
2.连接：假设原有的网络已经包含 个节点（ ）。在某一次加入过程中，新加入一个节点sn+1时，这个新节点会与原先包含的 个节点形成 个连结。
3.优先连接：连接时优先考虑大度节点。对于某一个原有节点 （ ），把它在原有网络中的度数用 表示，如此，新的节点与 相连的概率Pi为：
（2）
这样，在经过 次之后，新生成的网络中含有 个节点，总共包含 条边。
1.1.3 静态配置模型
静态配置模型是建立在Baralasi和Albert的BA网络模型上的一种网络模型。网络生成方法如下：
（1） 在网络中一共有N个节点，每个节点有一个编号 。
（2） 每个节点对应一个权重 ， 是一个 的可控变量，分别以概率 和 选择点 和点 ，若这两点之间没有边相连，则在两点之间建立一条边。
（3） 重复第（2）步直到整个系统中存在 条边，也就是网络中的节点平均度为 。
按照上述描述的方法所生成的网络其网络中的边的连接是由节点的权重比所决定的，并且在最终的网络中其节点度分布为
因为 是一个 的可控变量，故 的范围为 。
1.2 网络搜索研究综述
随机行走在网络搜索已得到广泛应用。在万文网、点对点网络以及无线通信网络上，常常采用随机行走的搜索策略。用标准随机行走搜索时，查询包从开始节点出发，被随机传递到当前节点的任意一个邻节点，直到发现查询目标为止。根据当前节点储存的邻节点上的文件目录的范围，可以分为：R0随机行走，即标准随机行走，查询包除了当前节点之外，不知道邻节点的信息；R1随机行走，查询包知道一阶邻节点范围内的所有节点的信息；R2随机行走，查询包知道二阶邻节点范围内的所有节点的信息。TMic研究表明R2随机行走的搜索效率最高。有偏随机行走时，查询包不再等概率地选择邻节点，通常根据邻节点的节点度或者权重来计算随机行走的概率，应用较多的是偏向大节点度的有偏随机行走。网络上的搜索还可以采用其它的随机行走方式，如不后退随机行走，不走三角形环路随机行走，不走四边形环路随机行走，点不重复随机行走，边不重复随机行走等等。Yang等研究结果表明，上述几种方法中点不重复随机行走的搜索效率最高。Lv等提出了k-walkers的随机行走搜索方法，其基本思想是开始节点同时发出k个查询包，然后各自独立地进行搜索。仿真结果表明这种搜索方法不但能够有效缩短搜索时间，使得搜索时间减少为标准随机行走的l／k，且大大减少了查询流量或网络负载。例如，对于P2P网络，采用k=32或k=64进行搜索就能够达到泛洪搜索的效果，而查询流量比泛洪搜索要低两个数量级。
1.3 本文研究思路介绍
本文探讨研究了在生成的网络中的随机行走过程。如从一个节点出发到另一个指定节点的首次通过时间和所需步数。改变网络模型、开始节点和目的节点的度数、随机行走的粒子数量，研究以上改变会对首次通过时间和步数有何影响。
研究手段：
（1）分别用小世界网络模型、无尺度网络模型、真实网络数据生成网络并且生成开始节点、目的节点、粒子数等必要的参数。