复杂网络及非集中搜索算法.doc

复杂网络和非集中搜索算法
一、 介绍
二、 小世界现象
小世界是指任何两个节点间通过较少的步实现连接。
三、 小世界网络基本模型
定理3.1：对于常数k≥3，如果随机地选择节点度为k的节点，那么每对节点间的路径长度为O(log n)的概率极高。
路径长度是n的对数，或多对数，即由log n 的多项式函数限制，将是这类讨论的重要标准，称之为非正式的小世界特征；当一个图中的所有（或大多数）节点对间的路径长度为n的对数多项式，则称之为小世界网络，因为这时的路径长度小于节点数指数级。
Watts和Strogatz认为定理3.1给出的图缺少某些关键的东西。按定理3.1所给的随机图，局部稀疏，一个节点的邻居是邻居的概率非常低。这与真实的网络相差很远，在现实网络中，许多节点的邻居通过边相互连接（例如，在社会网络中，我们的很多朋友相互认识）。毫无疑问，这是使许多人惊讶的小世界现象：任何节点从局部的观点看，社会网络有很高的聚类特性，而不是许多节点有非常短的路基的三分支结构。
因此，Watts和Strogatz假设小世界网络如下：结构化的大直径网络加上少量的随机连接。作为社会网络模型，网络的结构化意味着典型的社会连接，即生活或工作在周围的人们相互连接；附加的随机连接则是偶然的长程连接，这种长程连接使得网络产生较短的路径。研究表明，即使是较少的随机连接也能有效地产生短路径，因此有如下结论。
定理3.2 考虑到图G是通过在一个n节点的圆周上随机加边形成的，那么，每对节点通过短路径长度O(log n)连接的概率非常大。
这种模型非常接近Watts-Strogatz模型，他们的模型也考虑在圆周上加上随机连接。本文采用基于网格的模型，它们本质上相似。采用两维的n×n的网格图，对于每个节点v，另外随机加上到其他节点w的边。对于Watts-Strogatz结构，可以认为这种模型象社会网络，其底下有物理空间——人们都知道他们的地理上的邻居，同时有长距离的朋友。它也接近长程渗透模型，尽管本文考虑的问题有很大的不同。对于现在讨论的问题，尽管模型的本质特点是结构模型和随机连接的重叠，值得注意的是，按此得出的结果有很大的变化。实际上，下面的很大部分集中一般结构上的搜索问题。
四、小世界网络中的非集中搜索算法
通过Milgram 实验，可以得出惊人的算法：社会网络中不仅存在着最短路径，人们可以通过他们的熟人知识，构成到达目标的路径。这是该实验给其参与者设计任务的必然结果；如果一个人想获得从源节点到目的节点的最短路径，他必须从源节点开始把信传送给其所有的朋友，其朋友又把信传送给他的所有朋友，如此反复进行下去。这样信息会尽可能快地传送给目的节点，然而，很明显，这不是可行的选择。结果，Milgram被迫采用一种更有趣的实验来构成路径：在网络中使用隧道，每一步信只传递给一个人。这样一来，尽管最短路径存在，信也可能不能传送到目的节点。
小世界现象的算法方面就引起了最基本的问题——为什么社会网络构造结构使得非集中路由算法如此有效？显然网络包含某种坡度，它能帮助参与者传递信息到目的节点，这就是我们试图建立模型；我们的目标是试图发现非集中路由算法能否适用与简单的随机图模型，如果可以，试图从模型抽取某种定性的属性来区分不同网络，在这些网络中路由算法能成功。显然，这些问题远远超出Milgram实验，甚至社会网络；只有有限的路由信息通常发生在通信网络、万维网、神经网络、以及其他网络。因此，弄清有效的非集中路由算法的基础结构式涉及多领域的问题。
开始，我们必须弄清非集中算法的含义。在前文基于网格的模型中，算法试图将信息从源节点s沿着边传送到目的节点t，在传送过程中的每一步，当前信息持有者v知道隐含的网格结构，目标节点在网格中的位置，以及它自己的长程连接。其关键是他并不知道其它节点的长程连接。通过这些信息，v必须选择其网络邻居w传送信息，然后再w传送信息。我们将按照传递时间来评价非集中算法——在随机产生长程连接、随机选择源节点和目的节点的情况下，从源节点到目的节点所需的步数。我们的目标是发现算法使其传送时间为 n的对数。
有趣的是在Watts和Strogatz提出他们的模型时并没有算法方面的考虑，很显然，该模型对研究简单系统中的非集中路由算法非常有效。实际上，为了能以一种非琐碎的方法提出问题，网络看想象为部分知道算法和部分不知道——这在Milgram实验以及其他实验中很明显，个体节点不仅使用它们的局部连接，还有网络隐含的某些全局参考框架。而且，有意思的是，网络中了解的部分可能不包含从源节点到目的节点的短路径，但整个网络中肯定存在一条短路径。Watts和Strogatz模型用最小化的方法合并了这些特点，因此允许我们考虑如何利用他们所知道的节点网络结构来构建最短路径。
尽管如此，第一个结论是负面的。
定理4.1 在基于网格的模型中任何非集中算法的传送时间是。
这表明：存在着简单的模型，通过模型实现非集中算法发现路径的长度和传递时间间的指数分离。可是，显然这不是故事的结束，Watts-Strogatz模型中的随机连接没有规则，无法支持Milgram 实验中的非集中路由算法。这样引起新的问题：如何在该模型上进行简单的扩展使得非集中路由成为可能。
为了扩展模型，引进一个新的参数，通过它来控制长程连接与网络的地理位置间的相关程度。首先，定义两节点的网格距离为网格上最短路径上的边数，扩展模型的思想是长程连接趋向于连接较小网格距离的节点，其偏差由参数决定。特别地，对指数为的基于网格的模型定义如下：n×n的网格图，加上额外的长程连接，长程连接的概率为，为0，对应W-S模型，太大，无长程连接。
通过参数的设置，可以有一个统一模型来研究。当很小时，长程连接太随机了，不能有效地用于非集中算法，相反，长程连接太不随机了，不能提供足够的长程连接以产生小世界网络。是否存在着最优的点使得长程连接足够适合非集中路由算法？实际上是存在的。存在着唯一的值使得机遇网格模型的传输时间是网络规模的对数。
定理4.2：（a），网格的非集中传输时间为；
(b) ，网格的非集中传输时间为；
（c），网格的非集中传输时间为
非集中算法取得(b)的限制非常简单：每个节点只是传输信息给一个邻居——无论是长城连接还是短程连接，其到目的节点的网格距离尽可能小。（换句话说，如果能够使得信息在网格上离目标节点更近，就通过长程连接传送信息；否则就采用局部连接向目标方向传送。）对算法的分析如下：对于一个常数，在每一步至少存在概率，到目标节点的网格距离减少一半。值得注意：上述结论可以适用于任何常数维的网格网络；类似的三分法产生，当为网格维数时，能够取得网格规模的对数级传送时间。
更一般地，定理4.2（b）关键属性指数为2的含义如下：长程连接的产生并不是在整个网络中，而是一律按距离标度产生：v的长程连接对应着其离v的网格距离在到之间的概率与在1到log n之间的所有j的概率大约相同。
根据这种属性，无论节点现在离目的节点多远，可以看出存在着将到目的节点的网格距离分为两半的可能。直觉地，这种属性在Milgram实验中也有自然的含义；为服从其它的网格简单化模型，大体上说，当人们在任何不同的距离级别上有大致相同的熟人密度，非集中路由算法可以很好地使用。最后，这种标度距离大约一致是开始我们提到的目标的定性性质的一类。这种目标我们在下面两节中分析，也可以在其它模型和真实网络数据中发现。
5.其它模型中的非集中搜索算法
层次模型：先前提到的模型的一种变体是假设网络分为等级而不是网格——换句话，节点处于一个n叉树的叶节点，两个节点间的距离是基于它们最低级公共祖先的高度。
这种模型有多种设置。首先，按照Milgram实验，参与者决定如何将信传送给取决于两种因素之一：地理位置和职业。如果说两维网格本质上是从地理位置中的抽象，那么，层次模型可以说是按照人们职业分类来定义的。另一个关于层次范畴自然是Web网页间的关系：例如，关于。。。
一个自然假设是：在底层层次结构中分离的节点的链路密度低，这构成了有幂指数β的层次模型的基础。下面给出有n个叶节点的完全b叉树（高度h为logbn）。对于两个叶节点v和w，其树距离h(v,w)为树中最低公共祖先的高度。现在定义叶节点V的随即图G:对于V中的每个节点v,有一个值k,从节点v有k条边，其第i条边的终点为w的概率为（k为模型的出度）。
因此，β非常类似网格中的参数α。β=0，得到完全随机连接，当β较大时，连接更多选择邻居节点。现在非集中搜索算法给出源节点s和目的节点t在层次结构中的位置，必须形成一条从s到t得路径，并且只知道访问节点的出边。注意：在定义这种模型中的非集中搜索算法的性能指标时，遇到了基于网格模型中不会遇到的问题：图G可能不包含从s到t的路径。因此，如果随机地生成n节点网络，s和n 随机选择，非集中搜索算法的传输时间为f(n)，算法产生长度为O(f(n))的路径的概率至少为，这里是一个当n增加时趋近于0的函数。
我们现在有定理4.2类似的结论，假设当网络有对数出度，存在唯一的β值，可以取得对数级传输时间。这个结果的取得发生在β=1时，节点v 连接树距离为h的节点的概率对所有的h取值相同。与基于网格的模型类似，它满足使用贪婪算法以尽可能减少到达目的节点的树距离。
定理5.1 (a) 在指数β=1和出度k=c log2 n，对于足够大的常数c，存在着非集中算法，其搜索步数为网络规模的对数级。
（b）对于β≠1和每个对数函数k(n)，不存在传输时间为网络规模的对数级的非集中算法。
Watts, Dodds, Newman各自独立提出一种模型，，其中，每个节点存在于几个不同的层次结构，反映：在小世界实验中，参与者同时考虑几种不同的标准接近目标。确切地，其模型构造随即图G如下：首先以不同的q构成不同的完全b叉树，在每个树中，独立地选择随机的一对一叶节点映射。然后在每个树中应用上述层次模型。其结果是G中的每个节点通过参与者在每个树中独立地获得边。（每个层次结构和上述层次模型有少许不同；特别地，它们在每个层次结构中映射多叫相同的叶，每条边的产生通过随机地选择尾节点，而头节点按照层次结构生成。其结果是所有节点不会有相同的出度。）
精确地给出这种模型中的非集中算法的特点是一个开放问题，但是Watts等通过模拟取得了有趣的结论。他们研究最自然的搜索算法，这种算法中，信息的持有者传送信息给在任何层次结构中离目的节点最近的节点。他们检验了（β，q）如何使得搜索算法有效，发现搜索区域集中在β≥1但接近1，q为较小的常数。（设置q为2或3，β取较宽的范围可以获得有效的搜索算法）。结果显示，定性地，有效的搜索方法可以通过下述方法得到：几种不同的接近节点的测试方法，随机构成边时邻居节点较小的偏差。
基于集合系统的模型
人们可以想象其它方法构建通用的网络模型，例如，将节点同时放在层次结构和网格，因此，自然考虑到通用的结构，其中一系列关于搜索的限制同时出现。这种方法是基于建立在底层集合系统的随机图，按照直觉在一个社会网络中的人们之间有连接，因为他们是相同的小组的成员。换句话说，两个人之间可能有链路是因为他们生活在相同的小镇、有相同的职业、有相同的宗教信仰、或者喜欢同一小说家的作品。
具体地，假设有一个节点集V，它的子集为，这些子集我们称之为组。很难说任意集合系统的好处，但是我们设计网络结构至少网格中的节点和子域的集合，还可能是任意的有根的子树的集合。因此，我们考虑到集合系统满足这两类集合都有的简单属性。特别地，对于常数和，我们给出下列三种属性：
（1） 全集V是所有的组之一；
（2） 如果组Si的组大小g≥2，且包含节点v，那么存在组且包含v，它是严格小于Si，但组大小最小为；
（3） 如果的组最大为g，并且都包含级公共节点v，那么它们的集合最大为kg。
最有趣的是属性3，它可以看做一种限制的增长要求；可以证明它包含网格中的节点集合层次系统中的含根的子树。
给定若干组，可以按如下构建随机图。对于节点v和w，定义g(v,w)为包含它们的最小组的大小，同时也作为v和w之间的距离。对于固定的指数和出度值k，构造每个节点v有k个出度，选择w为从v的第i条边的终点的概率正比于。称之为指数为，出度为k的基于组的模型。在这样的随机图中的非集中搜索算法给定了整个集合系统的情况和目标节点的标识。但是，当信息到达某节点时只知道该节点的出度。如是有下列理论。
定理5.2 （a）给定任意的满足属性（i）、（ii）、（iii）的任意集合系统，在基于组的模型中=1（存在着一个足够大的常数c），存在着非集中搜索算法，其传输时间为网络规模的对数；
（b）给定任意的满足属性（i）、（ii）、（iii）的任意集合系统，,对数时间k(n),不存在传输时间为网络规模对数的非集中搜索算法。
换句话说，当节点间的链路的概率与包含该两节点的最小组的大小成反比时可能存在非集中算法。作为一个例子，如果组是两维网格上的球，包含距离为ρ的两节点的最小组的大小正比于ρ2，并且按照定理5.2（a）节点连接的概率正比于ρ-2，这样产生类似定理4.2（b）的结论——网格中连接与网络规模的平方成反比。
简单的例子显示：对于这种模型在γ>1时，无法直接构想出一般的否定结果[38]。对于更高的层次，基于组的模型很清楚不仅仅是得出目前这些结果的唯一方法；下一节将讨论最近的其他方法，而且，其它通用模型的设计是将来研究的方向。
6.设计原则和网络数据
除了作为图中搜索算法的基本问题的构想，到目前为止讨论的模型作为设计原则已经用到文件共享系统，而且它们能够获得社会网络的大规模结构。
P2P系统和聚焦web的传播：关于复杂网络的最近的研究主题是试图找到一种方法快速设计新型的网络系统的简单统计模型，以便观察P2P文件共享的协议设计中的这些现象。设计这种协议成为计算机系统领域一个活跃的研究主题，这主要得益于1999年Napster和音频共享文件的出现，使得P2P应用的兴趣的爆发。这种应用的目的是允许大量用户共享保存在他们个人计算机上的内容，并且其最初构想是系统支持的应用是基于一种简单的集中的索引，以映射所有的用户文件。根据这种索引，这种方法可以通过特定的内容的查询来发现包含特定文件的计算机的路径。这类系统中的音频共享应用涉及到显著的法律困难，但是，如果不考虑经济和版权问题，很清楚这类系统允许大量用户通过通信共享很大范围的潜在的较少争议的内容，如果他们能够构建一种健壮的、有效的方法。这模拟了研究界的很多研究，这些研究集中在非集中的方法来实现文件共享，而不仅仅依赖单一的集中索引。
在这些问题的非集中方法中，其核心挑战是：每个用户在他的个人计算机上有确定的文件，但没有地方包含一个全局的文件表；如果某人试图查找某一特定的信息，我们如何能有效地决定哪个用户有此信息的附件呢？没有一个集中的索引，这个问题非常类似Milgram实验：用户向他的邻居发出查询，其邻居又向邻居发出查询，如此一至进行下去。这是小世界模型的特点：关于这个问题的很多方法试图设计网络，在此网络上协议实现有效的非集中搜索算法。关于这些问题可参考文献[44,32,67,45,46].
关于Web传播的设计出现了大量的相关问题。然而，标准的Web搜索引擎首先编辑大量的Web主页索引，然后通过这些索引来实现查询，查询者试图通过超链接实现特定主题的网页的定位，而不编辑索引。下面的问题是设计非集中的搜索算法，其面对的web问题如下：没有全局的网络信息何时搜索相关的网页，什么是最有效的决定链接的规则？受这些问题的启发。Menczer使用通过开放路径提供的标题的层次组织，研究前节描述的层次模型获得大规模Web数据的链接模式。
社会网络数据：前面的两个应用——P2P系统和Web传播，涉及到计算机和信息网络的结构，尽管在它们的构造中存在着明显的社会力量。最近的研究表明如前所述的模型实际上适用于社会网络数据。换句话说，这些小世界模型清楚说明网络必须构建成支持有效的搜索，但是并不知道自然形成的网络是否按这种方法组成。最近的两个关于这些特点的研究致力于存在于在线环境的社会网络——如先前应用所述，可以看出社会网络和技术网络交织在一起，但是在这样条件下强调的是社会组成，而在线方面主要提供一个适当的方法对大型网络的细粒度的分析。
关于这个特点的研究之一，Adamic和Adar考虑到一个研究实验室组织的E-mail网络：收集一定时间的数据，定义任何两人间只要有信息交换就存在着一条边。他们将网络覆盖在代表组织结构的集合系统上，集合包含着代表实验室层次结构的子组。在其它研究发现中，两节点间有链接的概率正比于，这和定理5.2（a）的值相对照。因此，跨越大组间的数据交互比最优非集中搜索更频繁。当然，E-mail网络并不是明显设计支持非集中搜索，尽管可以思索是否存在某种隐含的因素使网络构建成便于搜索的结构；无论如何，有趣的是链路涉及到组的集合与先前理论预测的结构类似。
一个关于有效搜索的相关结构被 Liben-Nowell等大量研究[43]。他们考虑生活杂志，一个有 几百万参与者的高度活跃的在线团体，其中的成员相互联系，人员每天在线更新，张贴信息以便讨论。生活杂志特别用于研究链接的地理分区，因为系统中成员提供他们同朋友间的明确链接，大型的子集提供美国的一个家乡团体。其结果是，人们有机会调查：在非常大的人群中，社会网络的连接密度如何随着距离的增加衰减。
为了将这些数据和较早的模型联系，一个必须克服的技术挑战是：美国的人口密度特别不均匀，这使得很难解释基于一个节点非均匀分布的网格模型的预测。在前述结构分组的方法是处理非均匀的一种方法；Liben-Nowell等提出一种不同的归纳——基于等级的朋友关系，他们这一假设更适合这里的地理数据。在这基于等级的朋友模型中，有n个人的集合分布在二维网格上，每个节点可能有一个任意数的人。类似第4节中的基于网格的模型，每个人v在其任意四个邻居网格节点选择本地连接，另外按下述方法选择一个长程连接：首先，v将其它人们按他们同v建的距离分为等级，假设rank(w)表示w在v的等级队列中的位置，称之为：w在v的等级为r。v选择w作为它的长程连接的概率正比于1/rank(w)。
注意这种模型推广了第4节中的基于网格的模型，基于网格模型中的逆平方分布相当于基于等级朋友关系中的每个网格节点居住一个人。可是，基于等级的朋友结构非常好地定义了任何人口密度，而且，Liben-Nowell等证明：这支持有效的非集中搜索算法。他们分析非集中的贪婪算法总是将信息尽可能地传送给离目的节点更近的节点，并且定义传输时间为到达目的节点的步数。
定理6.1 对于网格上的任意人口密度，在基于等级的朋友关系模型中非集中贪婪算法的传输时间为O(log3 n).
在生活杂志数据中，L-N等证实朋友关系（v,w）是：w是v的r级朋友。他们发现这非常类似与r成反比，与基于等级的朋友模型类似。
这一发现值得注意，因为：首先，像Adamic和Adar考虑的电子邮件网络，没有理由相信：存在大规模明显动态的社会网络更接近简单模型预测的分布。其次，尽管生活杂志是一个在线系统，无论远近人们之间没有连接的限制，因此地理位置有很重要的作用，其结果是，人们可能推测很难发现地理路径如此接近这些数据，更一般地，这一节和前面的结果，都是基于高度程序化模型，尽管它们给出关于搜索理论最优的特殊预测，这些预测证实了真实的社会网络数据令人吃惊，并且它给人提示可能存在着这里没有发现的更深的现象。
7关于小世界网络和非集中搜索算法的进一步结果
大规模的渗透：这里考虑的基于网格的模型非常接近关于长程渗透问题。关于长程渗透的基本版本，可以设想一个无限的d维网格Zd，对于每对节点(v,w),存在一条无向边的概率是，这里，是v和w之间的网格距离，。注意；这与第4节描述的基于网格的模型有些不同：地理是无限的，边是无向的，节点的度不一定相同，网格的最近邻居间不一定存在着边。除此之外，这些问题的一个不同是研究问题的本质，在长程渗透问题的开始研究中，关注的是无限连接组成部分是否存在着一个参数范围。
受到小世界网络研究的启发，长程渗透研究开始研究直径问题。Benjamini和Berger在一维图上研究了这个问题，对模型进行修改使得图是有限的，且相邻节点间存在着边。紧随其后的是Coppersmith和Biskup等，他们获得了更严格的限制，同时考虑了较高维的网格。作为这工作的一个结果，我们知道，在关键值α=d和α=2d时，她的直径发生本质的改变。特别地，当α<d,直径为常数，当α=d，D=k log n/log log n，当d<α<2d，直径是n的多对数表达式，当α>2d,直径是n 的一个多项式。猜想α=2d，直径是n的多项式的概率极高。同样不知道在α>2d时直径是否与n成正比？这一结论在一维图中证明了，猜想可能在高维图中存在。
在α=d和α=2d时发生相变是由Kempe等在不同设置时观察到的，是对Demers等关于流言传播算法的猜想的分解。在这个模型中，节点位于有限维网格上，在每一时间步，节点v选择一个其他节点并且传输它当时给w知道的任何信息，节点w被选作信息接收者的概率正比于。信息来源于一个节点并传播给其它节点，以流行病传播模式在网络中传播。从源节点到目的节点的传播时间是多少呢？[34]的主要结果是：α≤d，时间是n的多对数式；d<α<2d时，时间是ρ(v,w)的对数多项式；当d>2d时，时间是ρ(v,w)的多项式。同样，这里α=2d同样不好理解，这非常有趣，因为相变值在在分布式计算系统中的流行病传播算法的应用非常重要。
有附加信息的非集中搜索算法：一些论文研究了再给少量的附加信息时的非集中搜索算法[28,42,47,48,66]。然而，第4节中的非集中算法改变了算法访问每个节点的单位成本，在随后的模型中有下列区别：一个节点可能咨询其邻居节点，并根据这些信息选择节点传输信息。在限制了算法传输步数，只有信息传输操作被考虑，而非咨询时间。
特别地，Lebhar和Schabanel考虑一种算法，拥有信息的节点在较少步数内咨询最多O(log n)个节点的集合，然后在该集合内沿着一个到w的路径传输信息，该节点离目标的网格距离最近。总的来说，该过程要咨询的节点数是O(log2 n)，并且到达目的节点的实际路径只有O(log n(log log n)2)步。
Manku等在d维网格上的长程逾渗模型上的简单算法（α=d）。注意这里的节点有无限制的度——正比于Log n，而不是像网格模型中固定不变。Manku等分析了一种邻居的邻居搜索算法，该算法中信息的持有者v查询它的所有邻居以了解所有邻居的集合S，然后然后在集合S中采用两步传输信息给离目的节点最近的节点。他们证明这种算法有极高的概率生成路径，沿着该路径到达目的节点最多要O(log n/log log n)步，这与Coppersmith等的结论一致[20]。他们还证明在基本的贪婪算法中，信息传输给离目的节点最近的邻居，其传输到目的节点期望的步数为log n。因此，一步提前咨询使得传输时间得以改善；并且一步提前生成路径长度与直径匹配，额外的提前开销不能提供任何改进。
因此，Manku等的结果提供了长程逾渗模型(α=d)中的提前开销对有效的非集中搜索算法的作用的严格描述；在网格模型中类似的提前开销的功能的准确描述是非常有趣的开放问题。
建立在任意底层图上的小世界网络：第5节的结果描述了基于底层结构的可搜索网络的不同模型（除了d维网格外）。在最近的几篇论文中，几种作为小世界网络的框架结构被提出[27,31,53,59]。
原则上，可以考虑在任何底层图G上加长程边；Fraigniaud[27]问是否可以通过这种方法将任何G转换成贪婪算法可以实现有效搜索的网络。特别地，假设选择图G的每个节点一个长程连接分布，通过这样给G的每个节点一条长程边以生成一个随即图Gˊ。然后考虑采用原始的贪婪算法来传送信息到目的节点t:当前的信息持有者传输信息给在G中到目的节点最近的邻居。是否对于任何图G 存在着一种长程连接分布，使得贪婪算法的传输时间是n的对数多项式？
这一问题一般是不确定的；注意解决该问题的挑战是源于这样一个事实:分布给每个节点的单一选择必须是任何可能的目的节点，即使图Gˊ有结构最好的最短路径，搜索算法是限制在原始图G上进行的。Fraigniaud通过下列限制给出肯定的回答:限制图的树的宽带，并假设图中没有大于固定长度的环[27]；他同时讨论了图底层的某些方面具备社会网络中可观察到属性一致。Duchon等给出肯定的回答，假设图满足某一确定的限制增长率[24]。
Slivkins[59]考虑不同的设置，节点被嵌入底层的度量空间。如果度量空间是双倍的，任何圆可以被半径为其一半的固定数的圆覆盖，那么存在模型，其中每个节点生成一个对数多项式个长程连接，并且非集中算法能够取得对数多项式的传输时间。
最后，其它关于搜索算法的研究设置不同的度。可以从社会结构中的导航得到启示，类似如小世界实验，考虑到事实：通过熟人可以认识大量的人。类似地，在P2P网络中，确定的节点有大量的邻居，这有助于信息的查询。Adamic等通过研究随机图给出这些考虑的协议，在随机图中高度的节点相对多些，非集中算法只能使用邻居节点的度信息，而不能使用图的其它信息。通过模拟，发现度信息对于确定的模型可以提供搜索性能的改进。
Simsek和Jensen考虑模型为嵌入空间和节点度的变化。特别地，他们研究了第4节网格模型的变体，节点有较宽范围的度变化，非集中算法使用邻居的位置和度信息。通过模拟，发现使用这些因素比使用单个因素对非集中搜索算法更有效。发现最优的合并位置和度信息方法，理解最优策略可搜索的网络范围，是将来研究的方向。
8 结论
我们从事复杂网络研究的特殊分支，关系最短路径和发现最短路径的非集中算法的能力。正如开始说，这系列想法是这领域研究的特点：从社会网络实验提取基本原则和不明显的网络特点；通过一系列随机图模型及其分析试图获得简化和规格化的形式；伴随模型属性，大量大规模网络数据的测量，到达令人吃惊的程度；连接范围的结果、算法中的问题、图论和离散的概率。
为了给出相关问题将来的研究方向，给出一些不确定的问题、小世界网络问题和非集中搜索算法。其中有些问题在这里讨论过。另一些没有讨论。这些问题可能有不同的形式，它们相互关联。
1. 节点度的变化：非集中搜索算法涉及到的模型包含两个方面的因素：节点度的变化和隐含的度量空间。Simsek和Jensen的研究给出非集中搜索算法有效的限制。例如，考虑d维网格模型的指数为α，假设每个节点的长程连接数独立于给定的概率分布。更准确地说，选择K个长程连接的概率为。
通过参数的改变，可以获得一系列网格模型，研究非集中搜索算法与长程连接和邻居节点度相关。可以研究传输时间与参数间的关系。
2． α = 2d：在网格模型和长程逾渗模型中，不知道α = 2d时图的直径。
3. 对数长度的路径：是否存在d维网格模型上的非集中算法当α = d，路径长度为O(log n),而访问节点数为对数多项式。
4． 任意图的小世界网络：是否可以通过增加适当的长程连接将任意图转换成可有效搜索的小世界网络。
5． 基于组模型的扩展：定理5.2基于组的模型包含一个肯定的结果——是网格和层次结构的归纳，但是当长程连接太长时包含一个否定结果。可是，它美誉完全归纳网格和层次结构的结果，因为当系统满足定理的条件1、2、3时当γ> 1也存在有效的非集中搜索算法。发现这三个属性变化时是否可以用一种自然的方法归纳网格和层次结构，γ=1时有效的非集中算法是否存在。
6． 多层次结构：在多层次结构模型[63]中获得非集中搜索算法的限制条件是一个开放的问题。对该模型进行小的修改，可以形成基于组的模型，完全可能解决这一问题。
7． 可搜索网络的进化：现有的模型支持有效的非集中搜索算法都是静态的，没有考虑其网络的进化。哪些网络的增长和缩小可能使得网络更便于有效的搜索？网络进化模型i在[19,56]涉及到，他们采用反馈机制实现节点的非集中搜索算法，并且可能部分重连网络。获得这些模型及其变体是一个开放的问题。一些P2P文件共享系统包含类似的反馈机制，取得了较好的性能[18],小世界网络的进化参考[67]。
游戏理论可能提供另一个关于研究小世界网络的技术。[5,33,65]
8. 有一定诱因的非集中搜索算法：游戏理论不仅提供网络增长的灵感，同时对网络操作的灵感。在P2P系统和在线社团中一个任务是如何诱导系统成员相互影响使得他们发出询问和信息。对于非集中搜索算法，假设有某种功能将信息从源节点传送到目的节点，中间节点按照一定的策略工作，要求补偿路径上的参与者。当这种行为应用到模型上时非集中路径上的信息如何改变。
在[40]中，设置下层网络为通过分支处理来构建的随机树。
9． 重建：这里所有的网络都是被认为建立在下层的参考架构上——网格结构、集合系统，并且大多数分析是假设在某一模型上。一般地，给出网络，发现其隐含的结构，在此基础上重建网络模型。
10． 比较网络数据集：前述模型给出一般视图，通过视图分析网络数据。人们自然可以使用这种方法比较相关网络数据。例如，假设通信在k个不同的组织，决定每个组织中的指数以确定节点间的连接概率。不同的指数将建立不同的结构。这些指数不同是否影响组织中的其他行为和性能。
更一般地，大规模社会、技术和信息网络是复杂的对象，而通过简单模型通过的建立原则对我们理解很关键。这里的观点给出原则之一，表明网络与它们固有的空间和组织结构相联系。