搜索服从幂律分布的网络 论文阅读

一、定义

1、幂律分布网络定义：
大部分通信网络和社会网络都具有幂律分布的特点，也即度数高的节点的数量少，度数低节点的数量多。

2、数学推导：

1. 对于指数为τ、最小度数为k = 1、在$m=k_{max}$处有突变截止点的幂律分布图，其生成函数为:

2. 节点总数为N的网络图中，所需搜索步骤数s约为$l{n}^2(N)$

3、搜索中的已知信息：
1.节点可以随机地将消息传递给它的一个邻居，也可以避免将消息传递给已经看到该消息的节点。
4. 节点可能只知道自己的属性（也即自己有几个邻居），也可能知道邻居的属性（比如该邻居有几个邻居），故可以选择将消息传递给邻居最多的邻居。
3.搜索过程中，每一步选择一个度比当前节点高的节点。

二、实验结果与贡献：

1、实验结果：
1.对实际的Gnutella网络的大约700个节点进行爬行，模拟搜索算法。假设每个文件只存储在一个节点上，那么在8个步骤或更少的时间内就可以找到50%的文件。此外，如果多个节点都存储了正在查找的文件，则搜索将更快。
2.大型社交网络指数基本都在(τ = 2.1 - 2.3)范围内，而对于非社交信息传递的网络，τ约为4，在不知道目标位置的情况下很难传递消息。
3.幂律分布网络与泊松分布网络的对比：
·在搜索某一点时，若幂律分布网络图中50%的部分节点已被访问过，则之后重复访问这些节点的时间约占80%，而随机分布的泊松图重复访问的时间为50%，也即：该搜索算法优先访问已经访问过的高度数节点，而非未访问过的低度数节点。
·在这种情况下，开始的节点只有一个连接边，但是两步之后，就能通过边到达一个度很高的节点。从此，就可以继续连接到度数很高的节点。该策略允许在最少的步骤数中扫描最大数量的节点。相比之下，即使这两个图有相当数量的节点和边泊松分布网络图的最大度节点为11，只有在第81步时才达到。
·下图显示了在10000个结点的图中，由随机策略和本文提出的策略访问到的随着步数增长访问到的结点总数。大约50%的节点在前10步内就能被扫描到；但是，有少量节点需要的查找步骤等于节点总数，甚至比节点总数还要多。

2、本文贡献：
在本文中，我们提出了一些消息传递算法，可以有效地用于在大型幂律网络(如Gnutella)中进行搜索。具体而言，本文优先利用度数高的节点进行局部搜索，与第5篇文献一样，算法使用结点本地信息，如邻居的身份和连通性，以及邻居的邻居，但不使用目标的全局位置，其搜索代价与图的规模呈次线性关系，并有助于减少网络搜索流量。