小世界网络简介与matlab建模.doc

小世界网络简介及 MATLAB 建模1.简介小 世 界 网 络 存 在 于 数 学 、 物 理 学 和 社 会 学 中 ， 是 一 种 数 学 图 的 模 型 在 这 种 图 中 大部 份 的 结 点 不 与 彼 此 邻 接 ， 但 大 部 份 结 点 可 以 通 过 任 一 其 它 节 点 经 少 数 几 步 就 可 以 产 生联 系 若 将 一 个 小 世 界 网 络 中 的 点 代 表 一 个 人 ， 而 联 机 代 表 人 与 人 之 间 是 相 互 认 识 的 ，则 这 小 世 界 网 络 可 以 反 映 陌 生 人 通 过 彼 此 共 同 认 识 的 人 而 起 来 产 生 联 系 关 系 的 小 世 界 现象 在 日 常 生 活 中 ， 有 时 你 会 发 现 ， 某 些 你 觉 得 与 你 隔 得 很 “遥 远 ”的 人 ， 其 实 与 你“很 近 ” 小 世 界 网 络 就 是 对 这 种 现 象 的 数 学 描 述 用 数 学 中 图 论 的 语 言 来 说 ， 小 世界 网 络 就 是 一 个 由 大 量 顶 点 构 成 的 图 ， 其 中 任 意 两 点 之 间 的 平 均 路 径 长 度 比 顶 点 数 量 小得 多 。

除 了 社 会 人 际 网 络 以 外 ， 小 世 界 网 络 的 例 子 在 生 物 学 、 物 理 学 、 计 算 机 科 学等 领 域 也 有 出 现 许 多 经 验 中 的 图 可 以 用 小 世 界 网 络 来 作 为 模 型 因 特 网 、 公 路 交通 网 、 神 经 网 络 都 呈 现 小 世 界 网 络 的 特 征 小 世 界 网 络 最 早 是 由 邓 肯 ·瓦 茨 （ Duncan Watts） 和 斯 蒂 文 ·斯 特 罗 加 茨 （ Steven Strogatz） 在 1998 年 引 进 的 ， 将 高 聚 合 系 数 和 低 平 均 路 径 长 度 作 为 特 征 ， 提 出 了 一 种新 的 网 络 模 型 ， 一 般 就 称 作 瓦 茨 -斯 特 罗 加 茨 模 型 （ WS 模 型 ） ， 这 也 是 最 典 型 的 小 世界 网 络 的 模 型 由 于 WS 小 世 界 模 型 构 造 算 法 中 的 随 机 化 过 程 有 可 能 破 坏 网 络 的 连 通 性 ， 纽 曼(Newman)和 瓦 茨 (Watts)提 出 了 NW 小 世 界 网 络 模 型 ， 该 模 型 是 通 过 用 “随 机 化 加 边 ”模 式 来 取 代 WS 小 世 界 网 络 模 型 构 造 中 的 “随 机 化 重 连 ”。

在 考 虑 网 络 特 征 的 时 候 ， 使 用 两 个 特 征 来 衡 量 网 络 ： 特 征 路 径 长 度 和 聚 合 系 数 特 征 路 径 长 度 （ characteristic path length） ： 在 网 络 中 ， 任 选 两 个 节 点 ， 连 同 这 两个 节 点 的 最 少 边 数 ， 定 义 为 这 两 个 节 点 的 路 径 长 度 ， 网 络 中 所 有 节 点 对 的 路 径 长 度 的 平均 值 ， 定 义 为 网 络 的 特 征 路 径 长 度 这 是 网 络 的 全 局 特 征 聚 合 系 数 (clustering coefficient)： 假 设 某 个 节 点 有 k 个 边 ， 则 这 k 条 边 连 接 的 节点 之 间 最 多 可 能 存 在 的 边 的 个 数 为 k(k-1)/2， 用 实 际 存 在 的 边 数 除 以 最 多 可 能 存 在 的边 数 得 到 的 分 数 值 ， 定 义 为 这 个 节 点 的 聚 合 系 数 所 有 节 点 的 聚 合 系 数 的 均 值 定 义 为 网络 的 聚 合 系 数 。

聚 合 系 数 是 网 络 的 局 部 特 征 ， 反 映 了 相 邻 两 个 人 之 间 朋 友 圈 子 的 重 合 度 ，即 该 节 点 的 朋 友 之 间 也 是 朋 友 的 程 度 我 们 可 以 发 现 规 则 网 络 具 有 很 高 的 聚 合 系 数 ， 大 世 界 （ large world， 意 思 是 特 征路 径 长 度 很 大 ） ， 其 特 征 路 径 长 度 随 着 n(网 络 中 节 点 的 数 量 )线 性 增 长 ， 而 随 机 网 络 聚合 系 数 很 小 ， 小 世 界 （ small world， 意 思 是 特 征 路 径 长 度 小 ） ， 其 特 征 路 径 长 度 随 着log(n)增 长 中 说 明 ， 在 从 规 则 网 络 向 随 机 网 络 转 换 的 过 程 中 ， 实 际 上 特 征 路 径 长 度 和 聚合 系 数 都 会 下 降 ， 到 变 成 随 机 网 络 的 时 候 ， 减 少 到 最 少 但 这 并 不 是 说 大 的 聚 合 系 数 一定 伴 随 着 大 的 路 径 长 度 ， 而 小 的 路 径 长 度 伴 随 着 小 的 聚 合 系 数 ， 小 世 界 网 络 就 具 有 大 的聚 合 系 数 ， 而 特 征 路 径 长 度 很 小 。

试 验 表 明 ， 少 量 的 short cut 的 建 立 能 够 迅 速 减 少 特征 路 径 长 度 ， 而 聚 合 系 数 变 化 却 不 大 ， 因 为 某 一 个 short cut 的 建 立 ， 不 仅 影 响 到 所 连接 的 节 点 的 特 征 路 径 长 度 ， 而 且 影 响 到 他 们 邻 居 的 路 径 长 度 ， 而 对 整 个 网 络 的 聚 合 系 数影 响 不 大 这 样 ， 少 量 的 short cut 的 建 立 就 能 使 整 个 网 络 不 知 不 觉 地 变 成 小 世 界 网 络 实 际 的 社 会 、 生 态 、 等 网 络 都 是 小 世 界 网 络 ， 在 这 样 的 系 统 里 ， 信 息 传 递 速 度 快 ，并 且 少 量 改 变 几 个 连 接 ， 就 可 以 剧 烈 地 改 变 网 络 的 性 能 ， 如 对 已 存 在 的 网 络 进 行 调 整 ，如 蜂 窝 电 话 网 ， 改 动 很 少 几 条 线 路 ， 就 可 以 显 著 提 高 性 能 2.小 世 界 网 络 构 成 原 则WS 小 世 界 网 络 的 构 成 原 则 为 ： 从 一 个 环 状 的 规 则 网 络 开 始 ， 网 络 含 有 N 个 结 点 ，每 个 结 点 向 与 它 最 近 邻 的 K 个 结 点 连 出 K 条 边 ， 并 满 足 N>>K>>In(N)>>1。

随 后 进行 随 机 化 重 连 ， 以 概 率 p 随 机 地 重 新 连 接 网 络 中 的 每 个 边 ， 即 将 边 的 一 个 端 点 保 持 不变 ， 而 另 一 个 端 点 取 为 网 络 中 随 机 选 择 的 一 个 节 点 其 中 规 定 ， 任 意 两 个 不 同 的 节 点 之间 至 多 只 能 有 一 条 边 ， 并 且 每 一 个 节 点 都 不 能 有 边 与 自 身 相 连 这 样 就 会 产 生pNK/2 条 长 程 的 边 把 一 个 结 点 和 远 处 的 结 点 联 系 起 来 改 变 p 值 可 以 实 现 从 规 则 网 络(p=0)向 随 机 网 络 (p=1)转 变 NW 小 世 界 网 络 的 构 成 原 则 为 ： 从 一 个 环 状 的 规 则 网 络 开 始 ， 网 络 含 有 N 个 结点 ， 每 个 结 点 向 与 它 最 近 邻 的 K 个 结 点 连 出 K 条 边 ， 并 满 足 N>>K>>In(N)>>1 随后 进 行 随 机 化 加 边 ， 以 概 率 p 在 随 机 选 取 的 一 对 节 点 之 间 加 上 一 条 边 。

其 中 ， 任 意 两个 不 同 的 节 点 之 间 至 多 只 能 有 一 条 边 ， 并 且 每 一 个 节 点 都 不 能 有 边 与 自 身 相 连 改 变 p值 可 以 实 现 从 最 近 邻 耦 合 网 络 (p=0)向 全 局 耦 合 网 络 (p=1)转 变 在 p 足 够 小 和 N 足 够大 时 ， NW 小 世 界 模 型 本 质 上 等 同 于 WS 小 世 界 模 型 3.MATLAB 建 模建 立 一 个 初 始 节 点 数 为 20 的 NW 网 络 MATLAB 程 序 如 下 ：function matrix = SW()%By 201121250314ticN=20;m=4;% 初始化网络数据p=0.1;% 以概率p=0.1在随机选取的一对结点之间加上一条边matrix=sparse([],[],[],20,20,0);% 创建一个20*20的全0稀疏矩阵%建立初始的环状的规则网络%结点网络有N个节点%每个结点向与它最近邻的m个结点连出边%求出邻接矩阵for i=m+1:N-mfor j=i-m:i+mmatrix(i,j)=1;endendfor i=1:mfor j=1:i+mmatrix(i,j)=1;endendfor i=N-m+1:Nfor j=i-m:Nmatrix(i,j)=1;endendfor i=1:mfor j=N-m+i:Nmatrix(i,j)=1;matrix(j,i)=1;endend%逆时针的边重连,从节点到N-m-1for i=1:N-m-1for j=i+1:i+mr=rand(1);% 随机选取一个数if r<=punconect=find(matrix(i,:)==0);% 取出邻接矩阵中的非0元素位置M=length(unconect);% 求出非 0元素个数r1=ceil(M*rand(1));% 正向取整matrix(i,unconect(r1))=1;matrix(unconect(r1),i)=1;% 连接这一对点%matrix(i,j)=0; matrix(j,i)=0;% 加上这个是SW小世界网络endendend%逆时针的边重新连接,从节点N-m到N-1for i=N-m+1:N-1for j=[i+1:N 1:i- N+m]r=rand(1);if r<=punconect=find(matrix(i,:)==0);r1=ceil(length(unconect)*rand(1));matrix(i,unconect(r1))=1;matrix(unconect(r1),i)=1;%matrix(i,j)=0;matrix(j,i)=0;endendend%逆时针的边重新连接,节点Nfor i=Nfor j=1:mr=rand(1);if r<=punconect=find(matrix(i,:)==0);r1=ceil(length(unconect)*rand(1));matrix(i,unconect(r1))=1;matrix(unconect(r1),i)=1;matrix(i,j)=0;matrix(j,i)=0;endendend%恢复小世界网络的邻接矩阵for m=1:Nmatrix(m,m)=0;% 去掉自身节点形成的环end%存储邻接矩阵%save data matrix;toc %计算程序耗时end上 述 程 序 建 立 了 一 个 NW 小 世 界 网 络 ， 求 出 了 其 邻 接 矩 阵 ， 用 tu_plot()函 数 画 出邻 接 矩 阵 的 图 ， 就 得 出 了 该 小 世 界 网 络 的 图 形 。

function tu_plot(rel,control)%由邻接矩阵画连接图，输入为邻接矩阵 rel，必须为方阵；%control 为控制量， 0 表示画出的图为无向图，1 表示有向图。