复杂网络调研报告 2009112734 郑梅容 2010-04.

Presentation on theme: "复杂网络调研报告 2009112734 郑梅容 2010-04."— Presentation transcript:

1 复杂网络调研报告 郑梅容

2 报告大纲 复杂网络起源 复杂网络基本概念 复杂网络的几种模型及其性质 复杂网络文献读后感

3 复杂网络起源 七桥问题 七桥问题描述的是东普鲁士的一个城镇，城中有一条横贯城区的河流，河中有两个小岛，两岸和两岛之间共架有七座桥，问能否在一次散步中走过所有的七座桥，而且每座桥只经过一次，最后返回原地。

4 20世纪60年代，由两位匈牙利数学家建立了ER随机图理论，被公认为是在数学上开创了复杂网络理论的系统性研究。
20世纪的后40年中，随机图理论一直是研究复杂网络的基本理论。 在ER随机图模型中，任意两个节点之间有一条边相连接的概率都为p，几乎每一个ER随即图都具有某种性质Q，如果当N趋于无穷大时产生具有这种性质Q的ER随机图的概率为1。ER随机图的许多重要的性质都是突然涌现的。也就是说，对于任一给定的概率P，要么几乎每一个图都具有某个性质Q，要么几乎每个图都不具有该性质。 在ER随机图模型中，任意两个节点之间有一条边相连接的概率都为p，几乎每一个ER随即图都具有某种性质Q，如果当N趋于无穷大时产生具有这种性质Q的ER随机图的概率为1。ER随机图的许多重要的性质都是突然涌现的。也就是说，对于任一给定的概率P，要么几乎每一个图都具有某个性质Q，要么几乎每个图都不具有该性质。

5 Milgram的小世界实验 首先， Milgram选定两个目标对象，然后他在遥远的堪萨斯州和内布拉斯加州招募到了一批志愿者。 Milgram要求这些志愿者通过自己所认识的人，用自己认为尽可能少的传递次数，设法把一封信最终转交到一个给定的目标对象手中。尽管并不是每个实验对象都很成功，但是根据最终到达目标者手中的信件统计分析，从一个志愿者到其目标对象的平均距离是6。 Milgram推断：地球上任意两个人之间的平均距离是6。这就是著名的六度分离推断。 Milgram的小世界实验在社会网络分析中具有重要影响。然而在Milgram的实验中，实际上只有少部分的信件最终送到了收信人手中，因此实验的完成率很低，而Milgram总共只送出了300封信。即使这些信全都成功送道了收信人手中，用这么少的数据量来统计人际关系网的性质，其可信度也是非常低的。

6 复杂网络的基本概念 平均路径长度 网络中两个节点i和j之间的距离定义为连接这两个节点的最短路径上的边数。
网络的平均路径长度L定义为任意两个节点之间的距离的平均值，即 其中N为网络节点数。网络的平均路径长度也称为网络的特征路径长度。 研究发现，尽管许多实际的复杂网络的节点数巨大，网络的平均路径长度却小的惊人。具体地说，一个网络称为是具有小世界效应的，如果对于固定的网络节点平均度<k>，平均路径长度L的增加速度至多与网络规模N的对数成正比。

7 整个网络的聚类系数C就是所有节点i的聚类系数 的平均值。
网络的聚类特性，简单的说就是在你的朋友关系网络中，你的两个朋友很可能彼此也是朋友，这种属性称为网络的聚类特性。 假设网络中的一个节点i有 条边将它和其他节点相连，这 个节点就称为节点i的邻居。这 个节点之间实际存在的边数 和总的可能的边数 之比就定义为节点i的聚类系数 。 整个网络的聚类系数C就是所有节点i的聚类系数 的平均值。

8 度和度分布 度是单独节点的属性中简单但是又很重要的概念。网络中所有节点i的度的平均值称为网络的平均度，记为<k>。近几年的研究表明，许多实际网络的度分布明显不同于泊松分布。许多网络的度分布可以用幂律形式来更好地描述。幂律分布也成为无标度分布，具有幂律度分布的网络也称为无标度网络。 在一个度分布为具有适当幂指数（通常为2≤γ≤3）的幂律形式的大规模无标度网络中，绝大部分的节点的度相对很低，但存在少量的度相对很高的节点，而这类网络业称为非均匀网络，那些度相对很高的节点称为网络的“集线器”hub。例如高速公路网就可以近似看作是一个均匀网络，因为不可能有上百条高速公路都经过同一个城市；而航空网则可以看作是一个无标度网络，大部分机场都是小机场，但存在少量连接众多小机场的非常大的机场。

9 复杂网络的几种模型及其性质 WS小世界模型
作为从完全规则网络向完全随机网络的过渡，Watts和Strogtz于1998年引入了一个有趣的小世界网络模型，称为WS小世界模型。其构造算法如下： ① 从规则图开始：考虑一个含有N个点的最近邻耦合网络，它们围成一个环，其中每个节点都与它左右相邻的各K/2节点相连，K是偶数。 ② 随机化重连：以概率P随机地重新连接网络中的每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。

10 WS小世界网络不呈现幂律特性，但是平均路径小，具有高聚类特性。

11 WS小世界网络模型统计性质 聚类系数： 平均路径长度：
迄今为止，人们还没有关于WS小世界模型的平均路径长度L的精确解析表达式，不过利用重正化群方法可以得到如下公式： 其中 为一普适标度函数，满足：

12 BA无标度网络模型 增长：从一个具有 个节点的网络开始，每次引入一个新的节点，并且连到m个已存在的节点上，这里m≤ 。
优先连接：一个新节点与一个已经存在的节点i相连的概率 与节点i的度 、节点j的度 之间满足如下关系： 经过t步后，这种算法产生一个有N=t+ 个节点、mt条边的网络。

13 BA无标度网络模型统计性质 聚类系数： 这表明与ER随机图类似，当网络规模充分大时BA无标度网络部具有明显的聚类特性。 平均路径长度：
L ∝ 这表明该网络业具有小世界特性。

14 复杂网络文献读后感 《复杂网络理论在互联网病毒传播研究中的应用》 《复杂网络的可靠性研究》

15 《复杂网络理论在互联网病毒传播研究中的应用》
这篇文章综述了近几年复杂网络理论在互联网病毒传播研究中的应用。首先介绍了互联网的结构特征,然后从临界值的角度介绍了计算机病毒在不同拓扑结构网络中的传播性质，讨论了相应的免疫机制,并对电子邮件病毒的传播行为进行了系统分析。研究表明,互联网络拓扑结构对计算机病毒的传播行为有着重要的影响，在不同的拓扑结构下，传播行为会呈现不同的特性。复杂网络理论为互联网上计算机病毒传播的研究提供了新的思路和方法。

16 无标度网络很容易受到病毒攻击而导致病毒的流行，因此选择合适的免疫策略显得更加重要。无标度网络有三种免疫策略：①随机免疫，也称均匀免疫，它是完全随机地选取网络中的一部分节点进行免疫，它对度大的节点和度小的节点是平等对待的。无标度网络中随着<>→∞时，免疫临界值趋于1，如果对无标度网络采取随机免疫策略，需要对网络中几乎所有节点都实施免疫才能保证最终消灭病毒传染。②目标免疫，根据无标度网络的不均匀特性，可以进行有选择的目标免疫，即选取少量度最大的节点进行免疫，一旦这些节点被免疫后，就意味着他们所连的边可以从网络中除去，使得病毒传播的可能的连接途径大大减少。③熟人免疫，该策略的基本思想是，从N个节点中随机选出比例为p的节点，再从每一个被选出的节点中随机选择一个邻居节点进行免疫。这种策略只需要知道被随机选择出来的节点以及他们直接相连的邻居节点，从而巧妙地回避了目标免疫中需要知道全局信息的问题。

17 不同的病毒复制和传播策略有可能导致不同的网络拓扑，因此需要有一种不受网络拓扑结构变化影响，并且不需在病毒爆发之前知道传染机制的控制策略。扼流就是这样一种策略，它通过限制给定时间段内一台计算机与其他计算机之间的心连接的数目而限制病毒传播速率。 当计算机病毒产生的网络流量比正常通信流量大得多时，扼流法很适用。扼流法是一种控制策略，它通过限制给定时间段内一台计算机与其他计算机之间的新连接的数目而限制病毒传播速率。它能够在不影响计算机正常工作的情况下大幅度降低病毒传播速率，从而赢得更多的时间来打补丁或用其他的方法对付该病毒。

18 《复杂网络的可靠性研究》 复杂网络可靠性的研究对于理解网络的结构和行为至关重要。真实复杂网络的拓扑特性和可靠性紧密相关，对于不同的网络，其可靠性存在很大差异。已有研究表明不同的网络拓扑有着不同的容错性和抗攻击性。特别是，当遇到节点的随机移除时，无尺度网络要比随机网络健壮的多，而当恶意攻击时，前者比较脆弱。然而由于对复杂网络的拓扑结构知之甚少，甚至有很大偏差，因此对复杂网络的可靠性研究一直是个很棘手的问题。

19 目前复杂网络的可靠性研究大都集中于研究攻击模式对网络拓扑结构的影响以及一些相继故障模型，而度与介数在一定程度上都可以反映出节点重要性，因此基于度与介数的攻击得到了广泛的研究。然而，这些都是基于几何量变化来研究网络在受到攻击后的结构动态行为，一直以来都没有一个确定的宏观的指标来衡量复杂系统可靠性。这也正是这篇文章的研究目标。

20 首先，为了宏观的研究复杂网络拓扑的可靠性，针对复杂网络的特点，这篇引入了可靠性指标一网络连通可靠度来衡量网络的可靠性，为增强网络的安全性提供坚实的理论基础。其次，它给出了可靠性度量网络连通可靠度的相关算法。通过对不同网络模型受到攻击后的可靠性指标变化及分布进行模拟分析，结果发现:1、随着网络规模的增大，可靠度呈线性增长趋势；2、在对网络进行随机攻击时，网络连通可靠度大小排序为：BA>E>R规则、WS，而在恶意攻击时，ER>规则、WS>BA。理论和实践都证明，网络连通可靠度不仅仅刻画了复杂网络的可靠性，而且将复杂网络可靠性用确切的量来表示，这为复杂网络的保护提供了一定的理论基础。另外，在文章的最后，给出了一个衡量网络脆弱性的静态参数韧性度，和研究的网络连通可靠度两个参数互为结合，可以很好的衡量网络的可靠性及脆弱性。

21 复杂网络可靠性研究中有两个最核心的问题，一是如何计算保持连通的概率，即可靠性的计算问题，另一个是可靠性优化问题。网络连通概率的计算是NP难问题，目前只应用于为数不多节点数很少的一些特殊网络，这严重影响了相关成果的应用。弥补这一缺陷的主要途径有二：一是利用近似分析的方法给出系统可靠性的上界与下界；二是利用概率统计技术对系统的可靠性作出估计。

22 复杂网络可靠性研究的目的，是为了保护网络。我认为复杂网络的保护应从以下几个方面来考虑：抵抗恶意攻击的能力，抵抗拥塞的能力及抵抗相继故障的能力。Scale-free网络由于其结构上的特征，使其具有鲁棒性和脆弱性，因而对这种结构进行自然防范的有效措施是有目的的接种疫苗，给网络中的关键结点赋予免疫性。又由于无尺度网络对随机故障的承受能力比较强，而随机网络、小世界网络对恶意攻击的耐受性较好，因此，在建立网络的时候，也可以选择全局无尺度，局部随机(或小世界)网络的拓扑结构。

23 结论 在此我仅报告一点初始的想法，具体的研究正在进行。 诚恳地欢迎各位给与指导！

24 谢谢！