复杂网络概述

1、复杂网络概述王 驰为什么要研究复杂网络？ 关于复杂性：大量个体（更典型的是具有适应性的主体）所组成的复杂系统，在没有中心控制、非完全信息、仅仅存在局域相互作用的条件下，通过个体之间的非线性相互作用，可以在宏观层次上涌现出一定的结构和功能。为什么要研究复杂网络？ 复杂系统不能够用分析的方法去研究，必须考虑个体之间的关联和作用，复杂网络是构成复杂系统的基本结构，每个复杂系统都可以看作是单元或个体之间的相互作用网络；复杂网络在刻画复杂性方面的重要性是由于结构决定功能的，理解复杂系统的行为应该从理解系统相互作用网络的拓扑结构开始； 网络拓扑结构的信息是构建系统模型、研究系统性质和功能的基础。 为什么要

2、研究复杂网络？ 复杂网络是研究复杂系统的一种角度和方法，它关注系统中个体相互关联的作用的拓扑结构，是理解复杂系统性质和功能的基础。复杂网络研究所关心的问题 如何定量刻画复杂网络？ 网络结构的描述及其性质 网络是如何发展成现在这种结构的？ 网络演化模型 网络特定结构的后果是什么？ 网络结构的鲁棒性 网络上的动力学行为和过程复杂网络的表示方法航空网道路交通网城市公共交通网复杂网络的表示方法WWW电力网因特网复杂网络的表示方法 图提供了一种用抽象的点和线表示各种实际网络的统一方法，因而成为目前研究复杂网络的一种共同的语言。 例子: 国际互联网: 节点路由器 连接光纤 科学引用网: 节点文章 连接文章

3、引用 社会网络: 节点个体人 连接人际关系复杂网络的表示方法 按照图中的边是否有向和是否有权，可以有四种类型的图。加权有向图加权无向图无权无向图无权有向图复杂网络的表示方法 图的计算机表示1,( ,)0,( ,)ijijijv vEav vE邻接矩阵 邻接矩阵描述了节点与节点之间的邻接关系，通常会用一个方阵A来表示，方阵中的元素用aij表示。复杂网络的表示方法 图的计算机表示1,( ,)0,( ,)ijijijv vEav vE一、复杂网络的定义 钱学森给出了复杂网络的一个较严格的定义：具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络称为复杂网络。 一、复杂网络的定义 小世界特

4、性又被称之为是六度空间理论或者是六度分割理论。小世界特性指出：社交网络中的任何一个成员和任何一个陌生人之间所间隔的人不会超过六个。小世界特性：一、复杂网络的定义无标度特性：现实世界的网络大部分都不是随机网络，少数的节点往往拥有大量的连接，而大部分节点却很少，节点的度数分布符合幂率分布，而这就被称为是网络的无标度特性。将度分布符合幂律分布的复杂网络称为无标度网络。一、复杂网络的定义社团结构特性：人以类聚，物以群分。复杂网络中的节点往往也呈现出集群特性。例如，社会网络中总是存在熟人圈或朋友圈，其中每个成员都认识其他成员。集群程度的意义是网络集团化的程度；这是一种网络的内聚倾向。连通集团概念反映的是

5、一个大网络中各集聚的小网络分布和相互联系的状况。例如，它可以反映这个朋友圈与另一个朋友圈的相互关系。二、复杂网络中的基本概念u度度(degree)(degree)：节点节点i i的度的度 k ki i 定义为与该节点连接的其他节点的定义为与该节点连接的其他节点的数目数目, ,对于有向网络分为出度和入度。对于有向网络分为出度和入度。 直观上看，一个节点的度越大就意味着这个节点在直观上看，一个节点的度越大就意味着这个节点在 某种意义上越某种意义上越“重要重要”（“能力大能力大”）。）。 u网络的平均度：网络的平均度：网络中所有节点的度和的平均值网络中所有节点的度和的平均值, ,记作记作 ，并且并且

6、 =2=2M M/ /N N，M M为网络中的边数，为网络中的边数，N N为节点数。为节点数。u度分布函数度分布函数p p( (k k):):随机选定节点的度恰好为随机选定节点的度恰好为k k的概率的概率 二、复杂网络中的基本概念u度分布函数度分布函数p p( (k k):):随机选定节点的度恰好为随机选定节点的度恰好为k k的概率的概率 kkPln)(ln二、复杂网络中的基本概念u节点的聚类系数（簇系数）节点的聚类系数（簇系数）：在简单图中，在简单图中，设与节点设与节点v v相邻的节点有相邻的节点有kiki个，个，则则节点节点v v的聚类系数的聚类系数定义为这定义为这k ki i个个节点之间

7、存在边数节点之间存在边数E Ei i与总的可能边数与总的可能边数k ki i(k(ki i-1)/2-1)/2之比，之比，即：即：C Ci i=2E=2Ei i/ /k ki i(k(ki i-1) -1) ( (包含节点包含节点i i的三角形数目的三角形数目/ /以节以节点点i i为中心的连通三元组的数目为中心的连通三元组的数目) )u 网络的聚类系数网络的聚类系数C：所有节点所有节点i的聚类系数的聚类系数Ci的平均值。的平均值。（0 C 1） C=0网络中所有节点都是孤立点网络中所有节点都是孤立点 C=1网络中任意节点间都有边相连网络中任意节点间都有边相连 网络节点间联系的密切程度网络节点

8、间联系的密切程度, 体现网络的体现网络的凝聚力凝聚力二、复杂网络中的基本概念u节点节点的介数的介数：u 边的介数：边的介数：iljljjljlNiNB,所有i/)(式中，式中，Njl表示节点表示节点vj和和vl之间的最短路径条数，之间的最短路径条数，Njl（i）表）表示节点示节点vj和和vl之间的最短路径经过节点之间的最短路径经过节点vi的条数。的条数。 jimlmlmllmijlmijNeNB,;,所有/式中，式中，Nlm表示节点表示节点vl和和vm之间的最短路径条数，之间的最短路径条数，Nlm（eij）表示节点）表示节点vl和和vm之间的最短路径经过边之间的最短路径经过边eij的条数的条数

9、二、复杂网络中的基本概念 许多大规模的实际网络都具有许多大规模的实际网络都具有明显的明显的聚类效应聚类效应。事实上，在很多类。事实上，在很多类型的网络型的网络(如社会关系网络如社会关系网络)中，你的中，你的朋友同时也是朋友的概率会随着网络朋友同时也是朋友的概率会随着网络规模的增加而趋向于规模的增加而趋向于某个非零常数某个非零常数，即当即当N时，时，C=O(1)。这意味着这。这意味着这些实际的复杂网络并不是完全随机的，些实际的复杂网络并不是完全随机的，而是在某种程度上具有类似于社会关而是在某种程度上具有类似于社会关系网络中系网络中“物以类聚，人以群分物以类聚，人以群分”的的特性。特性。二、复杂网

10、络中的基本概念u 最短路径最短路径（Shortest path）:两个节点之间边数最少两个节点之间边数最少的路径，最短路径的长度称为两点间的的路径，最短路径的长度称为两点间的距离，距离，用用d dij iju 平均路径长度平均路径长度（特征路径长度）（特征路径长度）L L： 所有节点对之间的距离的平均值。所有节点对之间的距离的平均值。 研究发现：尽管许多实际复杂网络的节点数巨大，研究发现：尽管许多实际复杂网络的节点数巨大，网络的平均路径长度却小的惊人。（小世界效应）网络的平均路径长度却小的惊人。（小世界效应）三、复杂网络的结构模型n四种结构模型规则网络规则网络随机网络随机网络小世界网络小世界网

11、络无标度网络无标度网络三、复杂网络的结构模型n规则网络（a）全局耦合网络 （b）最近邻耦合网络 （c）星形耦合网络三、复杂网络的结构模型n规则网络拓扑性质最近邻耦合网络目网路中连通三元组的数）（网络中三角形的数目3ncC)1(4）2（3KKk2k/m2）2/（12/1mncNNLN一般情况下，聚集系数较大，平均最短路径较长。三、复杂网络的结构模型n随机网络（1）初始化：给定N个节点以及连边概率p（2）随机连边： 选择一对没有边相连的不同的节点。 生成一个随机数r 如果rp,那么在这对节点之间添加一条边；否则就不添加边。 重复步骤，直到所有的节点对都被选择过一次。三、复杂网络的结构模型n随机网络

12、拓扑性质度分布：kNkppkNkP1)1(1)(MNMppMNMP2)1(2)(边数分布：聚类系数：C=p=/N-1平均路径长度：ERERDLlnN/ln三、复杂网络的结构模型n小世界网络三、复杂网络的结构模型n小世界网络C(p) : 平均聚集系数平均聚集系数 L(p) : 平均最短路径平均最短路径PageRank算法通过人工进行网页分类并整理出高质量的网站计算用户查询关键词与网页内容的相关程度来返回搜索结果 算法来源PageRank算法谷歌的两位创始人，当时还是美国斯坦福大学研究生的佩奇和布林开始了对网页排序问题的研究，借鉴了学术界评判学术论文重要性的通用方法，那就是看论文的引用次数。由此想

13、到网页的重要性也可以根据这种方法来评价。PageRank算法如果一个网页被很多其他网页链接到的话说明这个网页比较重要，也就是PageRank值会相对较高。如果一个PageRank值很高的网页链接到一个其他的网页，那么被链接到的网页的PageRank值会相应地因此而提高。PageRank算法 算法原理PageRank算法总的来说就是预先给每个网页一个PR值，PR值物理意义上为一个网页被访问概率，所以一般是1/N，其中N为网页总数。另外，所有网页的PR值的总和为1。预先给定PR值后，通过不断迭代，直至达到平稳分布为止。PR(A)=PR(B)/2+PR(C)NskPRaskPRjNjji1)1()1

14、(）（1iPageRank算法 算法证明002/13/12/1103/12/1003/1002/10ajinnAPP1TeeNA1ajinnPlim是否存在？如果极限存在，那么它是否与P0的选取无关？PageRank算法 算法证明nnAPP1状态转移矩阵A需要满足： 1.A为随机矩阵。 2.A是不可约的。 3.A是非周期的。作战体系节点重要性分析机械化战争时代，在通信手段和指挥控制手段受限的情况下，作战体系，形成了一种树状结构。随着指挥信息系统的功能越来越强，作战体系任何两个节点之间均可以根据需要建立联系，逐步形成网络化结构。作战体系节点重要性分析 作战体系结构的网络描述依据复杂网络理论，可以

15、定义作战体系由节点集合 V 和 边 集 合 E 组 成 的 图 G = (V , E) 。其中， V = v1,v2 ,vn，代表组成作战体系的指挥控制节点、预警侦察节点（包括战场态势信息源节点和目标信息源节点）、攻防交战节点等； E =e1,e2 ,em，代表节点之间信息传递关系。 作战体系节点重要性分析 作战体系节点重要性的度量指标u度度指标：指标：描述在静态网络中节点所产生的直接影响力。描述在静态网络中节点所产生的直接影响力。 u介介数指标：数指标：描述网络中最短路径描述网络中最短路径通过某节点通过某节点的的数量数量， 反反映的映的是该节点是该节点在网络中的枢纽性。在网络中的枢纽性。u紧密度指标：紧密度指标：紧密紧密度指标用于刻画网络中的节点通过网络度指标用于刻画网络中的节点通过网络到达网络到达网络中其它节点的难易中其它节点的难易程度。程度。11c)(NjijdiC作战体系节点重要性分析 作战体系受损程度的度量指标u最大连通分支：最大连通分支：最大连通分支的大小指的是相对大小，即最大连通分支的大小指的是相对大小，即最大最大连通分支连通分支的节点数与所有节点数的的节点数