复杂网络调研报告

《复杂网络调研报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1复杂网络调研报告2009112734郑梅容2010-042/24报告大纲复杂网络起源复杂网络基本概念复杂网络的几种模型及其性质复杂网络文献读后感3/24复杂网络起源七桥问题七桥问题描述的是东普鲁士的一个城镇，城中有一条横贯城区的河流，河中有两个小岛，两岸和两岛之间共架有七座桥，问能否在一次散步中走过所有的七座桥，而且每座桥只经过一次，最后返回原地。4/24随机图理论20世纪60年代，由两位匈牙利数学家建立了ER随机图理论，被公认为是在数学上开创了复杂网络理论的系统性研究。20世纪的后40年中，随机图理论一直是研究复杂网络的基本理论。在E

2、R随机图模型中，任意两个节点之间有一条边相连接的概率都为p，几乎每一个ER随即图都具有某种性质Q，如果当N趋于无穷大时产生具有这种性质Q的ER随机图的概率为1。ER随机图的许多重要的性质都是突然涌现的。也就是说，对于任一给定的概率P，要么几乎每一个图都具有某个性质Q，要么几乎每个图都不具有该性质。5/24Milgram的小世界实验首先，Milgram选定两个目标对象，然后他在遥远的堪萨斯州和内布拉斯加州招募到了一批志愿者。Milgram要求这些志愿者通过自己所认识的人，用自己认为尽可能少的传递次数，设法把一封信最终转交到一个给定的目标对象

3、手中。尽管并不是每个实验对象都很成功，但是根据最终到达目标者手中的信件统计分析，从一个志愿者到其目标对象的平均距离是6。Milgram推断：地球上任意两个人之间的平均距离是6。这就是著名的六度分离推断。6/24复杂网络的基本概念平均路径长度网络中两个节点i和j之间的距离定义为连接这两个节点的最短路径上的边数。网络的平均路径长度L定义为任意两个节点之间的距离的平均值，即其中N为网络节点数。网络的平均路径长度也称为网络的特征路径长度。7/24聚类系数网络的聚类特性，简单的说就是在你的朋友关系网络中，你的两个朋友很可能彼此也是朋友，这种属性称为

4、网络的聚类特性。假设网络中的一个节点i有条边将它和其他节点相连，这个节点就称为节点i的邻居。这个节点之间实际存在的边数和总的可能的边数之比就定义为节点i的聚类系数。整个网络的聚类系数C就是所有节点i的聚类系数的平均值。8/24度和度分布度是单独节点的属性中简单但是又很重要的概念。网络中所有节点i的度的平均值称为网络的平均度，记为。近几年的研究表明，许多实际网络的度分布明显不同于泊松分布。许多网络的度分布可以用幂律形式来更好地描述。幂律分布也成为无标度分布，具有幂律度分布的网络也称为无标度网络。在一个度分布为具有适当幂指数（通常为2≤

5、γ≤3）的幂律形式的大规模无标度网络中，绝大部分的节点的度相对很低，但存在少量的度相对很高的节点，而这类网络业称为非均匀网络，那些度相对很高的节点称为网络的“集线器”hub。例如高速公路网就可以近似看作是一个均匀网络，因为不可能有上百条高速公路都经过同一个城市；而航空网则可以看作是一个无标度网络，大部分机场都是小机场，但存在少量连接众多小机场的非常大的机场。9/24复杂网络的几种模型及其性质WS小世界模型作为从完全规则网络向完全随机网络的过渡，Watts和Strogtz于1998年引入了一个有趣的小世界网络模型，称为WS小世界模型。其构造

6、算法如下：①从规则图开始：考虑一个含有N个点的最近邻耦合网络，它们围成一个环，其中每个节点都与它左右相邻的各K/2节点相连，K是偶数。②随机化重连：以概率P随机地重新连接网络中的每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。10/24WS小世界网络不呈现幂律特性，但是平均路径小，具有高聚类特性。11/24WS小世界网络模型统计性质聚类系数：平均路径长度：迄今为止，人们还没有关于WS小世界模型的平均路径长度L的精确解析表达式，

7、不过利用重正化群方法可以得到如下公式：其中为一普适标度函数，满足：12/24BA无标度网络模型BA无标度网络模型基于网络的增长和优先连接特性，增长特性是只网络的规模的不断扩大化，优先连接特性是指新的节点更倾向于与那些具有较高连接度的“大”的节点相连接。其构造算法如下：增长：从一个具有个节点的网络开始，每次引入一个新的节点，并且连到m个已存在的节点上，这里m≤。优先连接：一个新节点与一个已经存在的节点i相连的概率与节点i的度、节点j的度之间满足如下关系：经过t步后，这种算法产生一个有N=t+个节点、mt条边的网络。13/24BA无标度网络模

8、型统计性质聚类系数：这表明与ER随机图类似，当网络规模充分大时BA无标度网络部具有明显的聚类特性。平均路径长度：L∝这表明该网络业具有小世界特性。14/24复杂网络文献读后感《复杂网络理论在互