复杂网络及其matlab模拟

毕毕 业业 论论 文文 题 目 复杂网络及其复杂网络及其 matlab 模拟模拟 学 院 物理与电子工程学院物理与电子工程学院 专 业 物理学物理学 毕业年限 2015 学生姓名 学 号 指导教师 0 复杂网络及其复杂网络及其 matlabmatlab 模拟模拟 班级班级 物理学 2 班 姓名姓名 指导教师指导教师 摘摘 要要 近年来 关于复杂网络的研究正方兴未艾 1998 年 Watts 和 Strogatz 在 Nature 杂志上发表文章 引入了小世界 Small 一 World 网络模型 本文对复杂网络的特性还有无标度与小世界网络进行简单介绍 详细介绍各个 模型的生成与算法 并用 matlab 软件进行了模拟 关键词关键词 复杂网络 无标度 小世界 模拟 Abstract In recent years the research on complex networks of academia is be just unfolding in particular the two pioneering work set off an upsurge in the study of complex networks In 1998 Watts and Strogatz published an article In this paper the properties of complex networks are scale free and small world networks are briefly introduced Generation and algorithm details of each model and use MATLAB software to simulate Key word Complex network Scale free Small World Simulation 引言引言 在人类生存的整个空间甚至宇宙中都存在着大量复杂系统 这些系统可以 通过形形色色的网络加以描述 一个典型的网络是由许多节点与连接两个节点 之间的一些边组成的 其中节点用来代表真实系统中不同的个体 而边则用来 表示个体间的关系 往往是两个节点之间具有某种特定的关系则连一条边 反 之则不连边 有边相连的两个节点在网络中被看作是相邻的 例如 神经系统 可以看作大量神经细胞通过神经纤维相互连接形成的网络 1 计算机网络可以 看作是自主工作的计算机通过通信介质如光缆 双绞线 同轴电缆等相互连接 形成的网络 2 类似的还有电力网络 1 社会关系网络 1 4 交通网络等等 数 学家和物理学家在研究网络的时候 往往只关心节点之间有没有边相连 至于 节点到底在什么位置 边是长还是短 是弯曲还是平直 有没有相交等等都是 1 他们不在意的 在这里 我们把网络不依赖于节点的具体位置和边的具体形态 就能表现出来的性质叫做网络的拓扑性质 相应的结构叫做网络的拓扑结构 那么 什么样的拓扑结构比较适合用来描述真实的系统呢 本文首先介绍了复杂网络的研究进展及其统计特征 然后对小世界网络和无 标度网络模型及各模型的 matlab 模拟作了详细介绍 1 1 复杂网络的发展及统计特征复杂网络的发展及统计特征 1 11 1 复杂网络的发展复杂网络的发展 由于现实世界网络的规模大 节点间相互作用复杂 其拓扑结构基本上未 知或未曾探索 两百多年来 人们对描述真实系统拓扑结构的研究经历了三个 阶段 在最初的一百多年里 科学家们认为真实系统要素之间的关系可以用一 些规则的结构表示 例如大数学家欧拉的哥尼斯堡七桥问题 8 哥尼斯堡是当 时东普鲁士的首都 今俄罗斯加里宁格勒市 普莱格尔河横贯其中 这条河上 建有七座桥 将河中间的两个岛和河岸联结起来 有人在闲暇散步时提出 能不能每座桥都只走一遍 最后又回到原来的位置 大数学家欧拉用一种独特 的方法给出了解答 他把两座小岛和河的两岸分别看作四个点 分别用 A B C 和 D 表示 而把七座桥看作这四个点之间的连线 分别用 a b c d e f 和 g 表示 如图 1 于是这个问题就简化成 能不能用一 笔就把这个图形画出来 经过进一步的分析 欧拉得出结论 不可能每座桥都 走一遍 最后回到原来的位置 并且给出了所有能够一笔画出来的图形所应具 有的条件 图 1 欧拉哥尼斯堡七桥问题 英国数学家哈密顿于 1859 年以游戏的形式提出 把一个正十二面体的二十 个节点看成二十个城市 要求找出一条经过每个城市恰好一次而回到出发点的 路线 这条路线就称 哈密顿圈 9 2 1852 年 毕业于伦敦大学的格思里来到一家科研单位做地图着色工作时 发现了一个有趣的现象 每幅地图都可以用四种颜色着色 使得有共同边界的 国家着上不同的颜色 9 1959 年 两个匈牙利著名的数学家 Erd s 和 R nyi 建立了著名的随机图理 论 用相对简单的随机图来描述网络 简称 ER 随机图理论 5 ER 随机图理论 对图论理论研究的影响长达近 40 年 以至于在随后的近半个世纪 随机图一直 是科学家研究真实网络最有力的武器 直到最近几年 科学家们发现大量的真实网络既不是规则网络 也不是随 机网络 而是具有与前两者皆不同的统计特性的网络 其中最有影响的是美国 的 Watts 和 Strogatz 于 1998 年发表了题为 小世界 网络的群体动力行为 的论文 1 推广了 六度分离 的科学假设 8 提出了小世界网络模型 六 度分离 最早来自于 20 世纪 60 年代美国哈佛大学心理学家 Milgram 对社会调 查的推断 是指在大多数人中 任意两个素不相识的人通过朋友的朋友 平均 最多通过 6 个人就能够彼此认识 随后 Barabasi 等人于 1999 年发表了题为 随机网络中标度的涌现 的论文 6 提出了一个无标度网络模型 指出在复 杂网络中节点的度分布具有幂指数函数的规 节点的度是指与该节点连接的边 数 而度分布是指网络中所有节点的度的分布情况 其度分布可以用幂律形 式进行描述 近 10 年来 复杂网络的研究正渗透到众多不同的学科 推进复 杂性科学的交叉研究 深入探索和科学理解复杂网络的定性特征与定量规律 使它获得广泛的应用 对全球科学和社会的发展具有十分重大的长远意义 1 21 2 复杂网络的统计特征 复杂网络的统计特征 平均路径长度 网络中两个节点 i 到 j 之间的距离定义为连接这两个节点 的最短路径上的边数 网络中任意两个节点之间的距离的最大值称为网络的直 径 记为 D 即 D max d 网络的平均路径长度 L 定义为任意两节点之间距 ij 离的平均值 即 ji ij d 1 2 1 1 NN L 1 其中 N 为网络的总节点数 网络的平均路径长度也称为网络的特征路径长度 3 集聚系数 集聚系数又称作簇系数 它衡量的是网络的集团化程度 是网 络的另一个重要参数 簇系数的概念有其深刻的社会根源 对社会网络而言 集团化形态是其一个重要特征 集团表示网络中的朋友圈或熟人圈 集团中的 成员往往相互熟悉 为衡量这种群集现象 科学家们提出了簇系数的概念 节 点 i 的簇系数描述的是网络中与该节点直接相连的节点之间的连接关系 即 i C 与该节点直接相邻的节点间实际存在的边数目占最大可能存在的边数的比例 的表达式为 i C 1kk e2 iiii C 2 式中表示节点 i 的度 表示节点 i 的邻接点之间实际存在的边数 网络的 i k i e 簇系数为所有节点簇系数的算术平均值 即 C N C N C 1 i i 1 3 其中为网络的阶 不尽尽是社会网络 在其它类型的网络中 也普遍存在集 N 聚现象 计算下面简单网络的直径 平均距离和各节点的集聚系数 图 2 网络统计特征计算示意图 解 首先计算出所有节点对的距离 d12 1 d13 1 d14 2 d15 1 d16 2 d23 1 d24 1 d25 2 d26 2 d34 2 d35 2 d36 1 d45 3 d46 1 d56 3 由此可得直径和平均 4 距离和集聚系数分别为 直径 平均距离3dddmax 5645ij j1i1 D 67 1 56 252 166 2 1 j ij dL 集聚系数 6 1 6 c 1i i N C 度分布 度分布是网络的一个重要统计特征 这里的度 Degree 也称为 连通度 Connectivity 节点的度指的是与该节点连接的边数 对网络中所有 节点的度求平均 可得到网络的平均度 k 度分布则表示节点度的概率分布 函数 它指的是节点有条边连接的概率 P kk 2 2 小世界网络模型及其模拟 小世界网络模型及其模拟 1929 年 匈牙利作家 F Karinthy 最早提出了 小世界现象 的论断 他认为 在地球上的任何两个人都可以平均通过一条由六位联系人组成的链条 而联系起来 而后 在 1967 年 美国哈佛大学社会心理学教授 Milgram 通过 设计一个连锁信件实验 提出了著名的 六度分离 假说 即 小世界现象 1 这体现了一个似乎很普遍的规律 在如今的信息化时代 人们之间的关系 已经完全社会化 任何两位素不相识的人都可能通过 六度空间 产生必然联 系或关联 这一现象表明 在看似庞大的网络中各要素之间的间隔实际上是非 常 近 的 大家在世界上通过一步一步的社会相识寻找到目标的这个短链子 理论普遍存在于各种社会 经济网络中 科学家们把这种现象称为小世界效应 1 Small world effect 为了用网络图来解释 六度分离 的小世界效应 Watts 和 Strogatz 在对规则网络和随机网络理论研究的基础上 于 1998 年提出了著名的 WS 小世界网络 1 WS 模型提出后 很多学者在此基础作了近 一步改进 其中应用最多的是 Newman 和 Watts 提出的所谓 NW 小世界模型 事 实上 当 p 很小 N 很大的时候 这两个模型理论分析的结果是相同的 现在我 们统称它们为小世界模型 前面我们已经简单的介绍了一下小世界网络的 WS 和 NW 模型 下面将着 重介绍小世界网络的 ws 模型的特点 2 12 1 WSWS 模型构造算法模型构造算法 5 1998 年 Watts 和 Strogatz 提出了小世界网络这一概念 并建立了 WS 模 型 1 实证结果表明 大多数的真实网络都具有小世界特性 较小的最短路径 和聚类特性 较大的聚类系数 传统的规则最近邻耦合网络具有高聚类的特 性 但并不具有小世界特性 而 ER 随机网络具有小世界特性但却没有高聚类特 性 因此这两种传统的网络模型都不能很好的来表示实际的真实网络 Watts 和 Strogatz 建立的 WS 小世界网络模型就介于这两种网络之间 同时具有小世界 特性和聚类特性 可以很好的来表示真实网络 1 WS 网络模型同时具有平均路径长度短集群系数高的特点 但是 它的度分 布仍是一个轻尾的 Poisson 分布 而且 WS 网络中不存在具有大量连接边的中 枢点 因此 它仍然是一个平衡网络 近年来 研究人员对小世界网络得结构 性质和动力学行为进行了深入的探索 取得了丰富成果 研究表明小世界网络 能够增强信号的传播速度 提高计 提高计算能力和网络同步能力 8 特别地 传染性疾病在小世界网络中传播要比在规则网络中容易得多 WS 模型的生成算法为 给定一个具有 N 个结点的环形网络规则 每一个 结点对称地与它最近的 m m N 个邻点相连 而后对每个结点的每一条顺时针 边以概率 P 重连 对每个结点重复上述过程 得到的网络称为小世界网络 10 2 22 2 小世界网络模型设计及实现 小世界网络模型设计及实现 1 从规则图开始 考虑一个含有 N 个点的最近邻耦合网络 它们围成一个 环 其中每个节点都与它左右相邻的各 K 2 节点相连 K 是偶数 2 随机化重连 以概率 p 随机地重新连接网络中的每个边 即将边的一个 端点保持不变 而另一个端点取为网络中随机选择的一个节点 其中规定 任 意两个不同的节点之间至多只能有一条边 并且每一个节点都不能有边与自身 相连 在上述模型中 p 0 对应于完全规则网络 p 1 则对应于完全随机网络 通过调节 p 的值就可以控制从完全规则网络到完全随机网络的过渡 网络图像 如下 6 图 3 不同概率下网络示意图 网络图中各节点度的概率分布如下 图 4 不同概率下各节点度的概率分布图 上面 P 0 2 时网络图显示 大部分连边保持不变 出现了少量捷径 正是 由于这少量捷径造成了网络的小世界效应 3 3 无标度网络模型及其模拟无标度网络模型及其模拟 1999 年 Alber 和 Barabds 发现 WWW 网页的度分布不是通常认为的 Poisson 分布 而是重尾特征的幂律分布 而且 WWW 基本上是由少数具有大 量超链接的网页串连起来的 绝大部分网页的链接很少 他们把网络的这个特 性称为无标度性 3 Scale free nature SF 研究人员对大量的实际网络进行了实 证分析 发现许多网络的度分布都是幂律的 要描述这些网络的结构和演化过 程 随机图模型和小世界网络模型显然无能为力 1999 年 Barabdsi 和 Albert 考察了实际网络的生成机制 发现增长和择优连 接是实际网络演化过程的两个基本要素 他们创造性地构建了能够产生无标度 特性的第一个网络模型 BA 模型 6 BA 模型的生成算法如下 7 1 增长 网络开始于少数几个结点 个 每个相等时问间隔增加一个新 0 m 点 新点与 m 个不同的已经存在于网络中的旧点相连产生 m 条新边 0 m 2 择优连接 假设新点与旧点 i 相连的概率 p 取决于结点 i 的度数 即 i k i j i i k k kp 4 经过 t 步时间步后 BA 模型演化成一个具有 N t 个结点 mt 条边的网络 0 m BA 网络主要具有以下特性 具有幂律度分布 是一个无标度网络 具有 小世界特征 幂律度分布的重尾特征导致无标度网络中有少数具有大量连接边 的中枢点 择优连接必然产生 富者愈富 现象 BA 网络同时具有鲁棒性和 脆弱性 面对结点的随机失效 网络具有鲁棒性 但面对蓄意攻击时 由于中 枢点的存在 网络变得十分脆弱 很容易陷于瘫痪 9 3 1 3 1 无标度网络模型构造算法无标度网络模型构造算法 按照 BA 模型的定义 针对 Matlab 语言的特点 以初始节点等于 3 为例 设计如下算法 11 第 1 生成 3 个结点的初始完全网络 设置网络规模为 N 并用 0 m 0 m Matlab 特有的稀疏矩阵处理函数 第 2 每隔一个固定时段加入一个新的结点 按照概率 p 与原有网络结 i k 点产生 m 条无重复连边 重复上述过程 N 次 0 m 第 3 存储 N 100 个结点的网络邻接矩阵 下面分别就 N 10 N 60 N 100 做图 8 图 5 无标度网络生成的演化图 上面三幅图对应的网络图中各节点度的概率分布如下 图 6 节点数不同时各节点度的概率分布图 上面组图显示 大部分结点的连边较少 少数结点具有大量的连边 这些 具有大量连边的结点构成了网络的中枢点 当结点个数无限增加时 网络结点 的度分布为幂律分布 可以用幂律形式 P k k 即 P k ak 网络即为 无标度网络 转换为对数函数 lnP k lna lnk 令 lnP 为 y k 为 x 则 y lna x 当 2 a 1 时函数图如下 图 7 各节点度的概率分布双对数曲线 许多实际大规模无标度网络 其幂指数通常为 2 3 绝大多数节点的 度相对很低 也存在少量度值相对很高的节点 把这类网络称为无标度网络 9 4 4 结结语语 现实世界中许许多多的复杂网络都是具有小世界或无尺度特征的复杂网络 从生物体中的大脑结构到各种新陈代谢网络 从 Internet 到 WWW 从大型电力网 络到全球交通网络 从科研合作网络到各种政治 经济 社会关系网络等等 数 不胜数 因此 对小世界网络和无标度网络及其模型进行更深入的研究是非常 必要的 参考文献参考文献 1 Watts D J and Strogatz S H Collective dynamics of small world networks Nature 393 440 442 1998 2 Faloutsos M Faloutsos P Faloutsos C On power law relationships of the internet topology C ACM SIGCOMM Computer Communication Review ACM 1999 29 4 251 262 3 Albert R Barabasi A L Statistic