复杂网络介绍.pptVIP

复杂网络 不同领域的真实网络 社会网：演员合作网，友谊网，姻亲关系网，科研合作网，Email网 生物网：食物链网，神经网，新陈代谢网，蛋白质网，基因网络 信息网络：WWW，专利使用，论文引用，计算机共享 技术网络：电力网，Internet，电话线路网 交通运输网：航线网，铁路网，公路网，自然河流网 社会网络 人物关系网 生物网 食物链网 神经网络 信息网络 WWW网 技术网络 电话网 交通运输网 公路网 航空网 河流网 复杂网络 复杂网络（Complex Network ）： 钱学森给出了复杂网络的一个较严格的定义：具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络称为复杂网络 复杂网络简而言之即呈现高度复杂性的网络。 1）结构复杂，表现在节点数目巨大，网络结构呈现多种不同特征。 2）网络进化：表现在节点或连接的产生与消失。例如world-widenetwork，网页或链接随时可能出现或断开，导致网络结构不断发生变化。 3）连接多样性：节点之间的连接权重存在诧异，且有可能存在方向性。 4）动力学复杂性：节点集可能属于非线性动力学系统，例如节点状态随时间发生复杂变化。 5）节点多样性：复杂网络中的节点可以代表任何事物，例如，人际关系构成的复杂网络节点代表单独个体，万维网组成的复杂网络节点可以表示不 同网页。 6）多重复杂性融合：即以上多重复杂性相互影响，导致更为难以预料的结果。例如，设计一个电力供应网络需要考虑此网络的进化过程，其进化过程决定网络的拓扑结构。当两个节点之间频繁进行能量传输时，他们之间的连接权重会随之增加，通过不断的学习与记忆逐步改善网络性能 复杂网络简而言之即呈现高度复杂性的网络。 4）动力学复杂性：节点集可能属于非线性动力学系 统，例如节点状态随时间发生复杂变化。 5）节点多样性：复杂网络中的节点可以代表任何事物，例如，人际关系构成的复杂网络节点代表单独个体，万维网组成的复杂网络节点可以表示不 同网页。 6）多重复杂性融合：即以上多重复杂性相互影响，导致更为难以预料的结果。例如，设计一个电力供应网络需要考虑此网络的进化过程，其进化过程决定网络的拓扑结构。当两个节点之间频繁进行能量传输时，他们之间的连接权重会随之增加，通过不断的学习与记忆逐步改善网络性能 小世界网络 在数学、物理学和社会学中，小世界网络是一种数学之图的类型，在这种图中大部份的结点不与彼此邻接，但大部份结点可以从任一其他点经少数几步就可到达。若将一个小世界网络中的点代表一个人，而连结线代表人与人认识，则这小世界网络可以反映陌生人由彼此共同认的人而连结的小世界现象。 许多经验中的图可以由小世界网络来作为模型。社会网络、互联网和基因网络都呈现小世界网络的特征。 Small-World Networks 1998年瓦兹（Duncan Watts）和史楚盖兹（Steven Strogatz）把某一种小世界网络归类为随机图的一个模式。他们注意到图可以按两个独立的结构特性而分类，就是群聚系数（clustering coefficient）和结点间距平均值，后者又称为最短路径长度平均值。纯粹的随机图会展现很小的最短路径长度平均值，但同时也会有着很小的群聚系数。可是瓦兹和史楚盖兹算出事实上真实世界的网络虽然有很小的最短路径长度平均值，但却也有着比随机网络高出相当多的群聚系数。于是瓦兹和史楚盖兹提出了一种新的图模式，一般就称作瓦兹－－史楚盖兹模式，就是有 （一）很小的最短路径长度平均值 （二）很大的群聚系数的小世界网络 D. J. Watts S. H. Strogatz 现实世界的网络大部分都不是随机网络，少数的节点往往拥有大量的连接，而大部分节点却很少，一般而言他们符合zipf（其普夫）定律，(也就是80/20马太定律)。人们给具有这种性质的网络起了一个特别的名字——无标度网络。这里的无标度是指网络缺乏一个特征度值（或平均度值），即节点度值的波动范围相当大。 无标度网络（Scale - free network） 无标度网络（Scale - free network） 按生长方式定义：如果网络的每个节点的连接数与此节点产生新连接的概率成增函数关系，这个网络就叫无尺度网络。 按分布定义：如果网络中有一定数量的连接的节点数与此连接数量成减函数，这个网络就叫无尺度网络。 Milgram小世界实验 Question：随机抽取两个美国人，这两个人要经过几个人建立关系？ S. Milgram, The small world problem, Psychology Today, May 1967, 6