复杂网络和非集中有哪些信誉好的足球投注网站算法.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 在基于