2 复 杂 网 络 拓 扑 连 接 优 化 控 制 2.1 理 论 基 础 设 图 G = (V,l) 是 一 个 无 自 环 的 无 向 连 通 网 络, 其 中 V = {v 1,v 2,,v n } 是 网 络 中 所 有 节 点 的 集 合 ; l = {l 1,l 2,,l m } 且 l

复 杂 网 络 系 统 拓 扑 连 接 优 化 控 制 方 法 周 漩 1)2) 杨 帆 3) 张 凤 鸣 1) 周 卫 平 2) 邹 伟 2) 1) ( 空 军 工 程 大 学 装 备 管 理 与 安 全 工 程 学 院, 西 安 710051 ) 2) ( 海 军 装 备 研 究 院, 北 京 100161 ) 3) ( 西 藏 大 学 师 范 学 院, 拉 萨 850000 ) ( 2012 年 9 月 9 日 收 到 ; 2013 年 4 月 17 日 收 到 修 改 稿 ) 为 了 增 加 实 际 网 络 系 统 连 接 增 益 减 少 网 络 连 接 成 本, 提 出 了 一 种 基 于 网 络 效 率 和 平 均 连 接 度 的 网 络 拓 扑 连 接 优 化 控 制 方 法, 该 方 法 利 用 网 络 效 率 来 表 征 网 络 连 接 收 益 用 网 络 平 均 连 接 度 来 表 征 网 络 连 接 成 本, 并 提 出 了 其 计 算 优 化 算 法, 该 算 法 的 时 间 复 杂 性 为 O(Mpn 2 ). 实 验 分 析 表 明, 可 以 采 取 一 定 的 方 式 对 实 际 复 杂 网 络 拓 扑 连 接 进 行 优 化 控 制, 小 世 界 和 无 标 度 网 络 均 存 在 一 个 最 佳 的 网 络 平 均 度 值 能 够 使 网 络 连 接 增 益 达 到 最 大. 关 键 词 : 复 杂 网 络, 拓 扑 连 接, 优 化 控 制, 连 接 增 益 PACS: 02.10.Ox DOI: 10.7498/aps.62.150201 1 引 言 复 杂 网 络 是 复 杂 系 统 的 抽 象, 它 无 处 不 在 [1 3], 许 多 现 实 系 统 都 可 以 抽 象 为 网 络 模 型 进 行 研 究 [4]. 复 杂 网 络 研 究 中 的 一 个 核 心 问 题 是 复 杂 系 统 结 构 与 功 能 之 间 的 关 系 问 题 [5], 因 此 优 化 网 络 结 构 改 善 系 统 功 能 吸 引 了 复 杂 网 络 领 域 许 多 学 者 的 注 意. 当 前 的 复 杂 网 络 优 化 研 究 中, 不 同 学 者 针 对 不 同 网 络 的 不 同 需 求, 优 化 目 标 也 不 尽 相 同. 有 的 学 者 侧 重 于 提 高 网 络 鲁 棒 性 : 文 献 [6] 提 出 了 一 种 基 于 Kleinberg 模 型 的 无 线 传 感 器 网 络 拓 扑 优 化 方 法, 通 过 优 化 能 够 显 著 改 善 网 络 的 容 错 性 和 可 靠 性 ; 文 献 [7] 通 过 对 现 有 复 杂 网 络 拓 扑 关 键 节 点 的 发 现 和 消 除 算 法 的 分 析 和 改 进 来 改 善 P2P 网 络 的 连 通 性 和 鲁 棒 性. 有 的 学 者 侧 重 于 改 善 网 络 的 拓 扑 特 性 : 文 献 [8] 研 究 了 网 络 边 重 连 算 法, 通 过 边 的 重 连 来 提 高 网 络 的 同 步 性 ; 文 献 [9] 提 出 了 一 种 异 质 的 连 接 策 略 来 优 化 动 态 无 线 网 络 的 拓 扑 结 构, 使 其 具 有 小 世 界 特 性 ; 文 献 [10] 提 出 了 一 种 城 市 交 通 无 线 传 感 器 网 络 优 化 方 法, 通 过 优 化 使 网 络 具 有 小 世 界 特 性. 有 的 学 者 侧 重 于 研 究 改 善 网 络 效 率 : 文 献 [11] 研 究 了 多 智 能 体 系 统 中 信 息 共 享 的 网 络 拓 扑 优 化 问 题, 并 运 用 混 合 整 数 规 划 方 法, 得 出 了 优 化 的 网 络 模 型 和 边 权 值 ; 文 献 [12] 为 了 提 高 网 络 传 输 效 率, 提 出 了 一 种 利 用 均 匀 和 非 均 匀 网 络 拓 扑 来 提 高 网 络 传 输 效 率 的 方 法 ; 文 献 [13] 为 了 减 少 光 纤 网 络 边 上 交 通 流 和 网 络 拥 堵 问 题 优 化 网 络 鲁 棒 性, 通 过 综 合 考 虑 网 络 拓 扑 优 化 和 生 存 策 略, 提 出 了 一 种 LCM-WP 方 法 来 优 化 光 纤 网 络. 从 当 前 的 研 究 情 况 看, 许 多 学 者 只 注 重 复 杂 网 络 优 化 的 目 的, 而 忽 略 了 网 络 优 化 所 需 成 本. 为 此, 本 文 提 出 一 种 综 合 考 虑 网 络 连 接 增 益 和 连 接 成 本 的 复 杂 网 络 拓 扑 连 接 优 化 控 制 方 法. 最 小 生 成 树 和 全 连 通 网 络 是 连 通 网 络 的 两 个 极 端, 虽 然 在 实 际 网 络 建 设 中 很 少 采 用, 但 两 者 之 间 却 存 在 着 巨 大 的 网 络 拓 扑 空 间. 为 了 实 现 复 杂 网 络 拓 扑 连 接 的 优 化 控 制 找 出 网 络 连 接 增 益 最 大 的 网 络 拓 扑, 本 文 通 过 对 网 络 信 息 连 接 收 益 连 接 成 本 以 及 网 络 增 益 进 行 定 义, 利 用 网 络 效 率 和 平 均 连 接 度 来 表 征 网 络 连 接 收 益 和 连 接 成 本, 提 出 一 种 复 杂 网 络 连 接 优 化 设 计 评 估 方 法, 为 实 际 复 杂 网 络 系 统 优 化 控 制 提 供 依 据. 通 讯 作 者. E-mail: zhouxuan 333@126.com c 2013 中 国 物 理 学 会 Chinese Physical Society http://wulixb.iphy.ac.cn 150201-1

2 复 杂 网 络 拓 扑 连 接 优 化 控 制 2.1 理 论 基 础 设 图 G = (V,l) 是 一 个 无 自 环 的 无 向 连 通 网 络, 其 中 V = {v 1,v 2,,v n } 是 网 络 中 所 有 节 点 的 集 合 ; l = {l 1,l 2,,l m } 且 l V V 是 节 点 间 边 的 集 合. ω i j 表 示 连 接 节 点 v i 和 v j 的 边 l i j 的 权 值. 定 义 1 对 于 图 G = (V,l), 用 a i j 表 示 G 中 节 点 v i 和 v j 之 间 边 的 权 值, 当 v i 与 v j 直 接 相 邻 时, a i j = ω i j, 否 则 a i j =, 则 n 阶 方 阵 A = (α i j ) n n 称 为 G 的 边 权 矩 阵. 边 权 矩 阵 A 用 来 表 示 网 络 各 节 点 一 步 可 达 的 距 离. 当 α i j = 时, 说 明 节 点 v i 与 v j 不 能 一 步 可 达, 它 们 不 相 邻. 网 络 中 的 边 权 用 来 表 示 节 点 之 间 信 息 流 通 的 难 易 程 度, 数 值 越 大, 消 耗 的 资 源 越 多. 定 义 2 对 于 图 G = (V,l), 用 a i j 表 示 G 中 节 点 v i 和 v j 之 间 的 相 邻 情 况, 当 v i 与 v j 直 接 相 邻 时, a i j = 1, 否 则 a i j = 0, 则 n 阶 方 阵 A = (α i j ) n n 称 为 G 的 邻 接 矩 阵. 定 义 3 对 于 图 G = (V,l), 用 z i j 表 示 G 中 与 节 点 v i 相 连 的 第 j 个 节 点, 当 a i j = 1 ( j = 1,,n) 时, 则 z ik = v j, k = k +1; 则 n p 阶 矩 阵 Z = (z i j ) n p 称 为 G 的 相 连 矩 阵. 定 义 4 节 点 距 离 是 指 两 节 点 之 间 所 有 路 径 边 权 之 和 的 最 小 值, 用 d 表 示. 如 果 v i 和 v j 之 间 不 存 在 路 径, 则 d i j. 网 络 中 节 点 之 间 距 离 的 最 大 值 为 网 络 的 直 径 R. 当 网 络 为 无 权 网 络 时, d 表 示 两 节 点 之 间 最 短 路 径 上 的 边 数. { d i j = min ω pq }, v p,v q r i j Rt, (1) pq d i j 表 示 节 点 v i 和 v j 之 间 的 距 离, r i j 表 示 连 接 节 点 v i 和 v j 的 某 一 条 路 径, Rt 表 示 连 接 节 点 v i, v j 的 路 径 集 合. 定 义 5 网 络 效 率 E 是 指 任 意 两 个 节 点 之 间 最 短 路 径 倒 数 之 和 的 平 均 值, 它 用 来 表 示 网 络 信 息 流 通 的 平 均 难 易 程 度. 网 络 效 率 越 高, 网 络 信 息 流 通 越 容 易, 1 E = n(n 1) 1, (2) i j d i j 式 中, n 为 网 络 中 节 点 数 目, d i j 为 节 点 i 和 j 之 间 的 距 离. 从 网 络 效 率 E 的 定 义 中 可 以 看 出, 网 络 效 率 E 表 达 了 网 络 中 所 有 节 点 对 之 间 的 平 均 接 近 程 度. 网 络 中 节 点 对 之 间 越 接 近 距 离 越 短, 网 络 效 率 值 越 大. 2.2 网 络 连 接 成 本 收 益 评 估 模 型 实 际 网 络 系 统 组 建 过 程 中, 由 于 不 同 节 点 之 间 通 信 需 求 地 理 位 置 和 系 统 功 能 等 要 求 的 不 同, 导 致 各 节 点 通 信 线 路 建 设 成 本 是 不 同 的. 本 文 用 节 点 之 间 的 路 径 长 度 来 衡 量 链 路 建 设 的 成 本 和 信 息 传 播 的 便 捷 程 度. 节 点 之 间 路 径 长 度 越 短, 链 路 建 设 成 本 越 小 信 息 传 播 越 容 易. 对 于 实 际 网 络 而 言, 较 短 的 网 络 平 均 路 径 长 度 可 以 使 得 信 息 快 速 传 播 节 省 网 络 建 设 所 消 耗 的 资 源, 提 高 网 络 的 整 体 效 率, 因 此 通 过 增 加 网 络 连 接 度 可 以 减 少 网 络 平 均 路 径 长 度, 节 省 资 源, 增 加 网 络 连 接 收 益 ; 但 由 于 网 络 平 均 连 接 度 的 增 大, 又 会 导 致 节 点 信 息 超 载 和 通 信 链 路 过 度 冗 余, 而 产 生 较 高 的 信 息 阻 塞 费 用 和 冗 余 费 用. 如 图 1 所 示 的 简 单 通 信 网 络, 相 同 数 目 节 点 之 间 可 以 存 在 多 种 连 接 方 式 ( 网 络 A, B, C 表 示 加 权 网 络, 网 络 D, E, F 分 别 表 示 网 络 A, B, C 所 对 应 的 无 权 网 络 连 接 模 式, 网 络 G, H, I 分 别 表 示 环 形 网 络 链 状 网 络 和 星 形 网 络 3 种 特 殊 连 接 模 式 ): 网 络 A 和 网 络 D 通 信 连 接 非 常 充 分, 信 息 可 以 在 全 部 节 点 中 快 速 传 播, 从 而 获 得 与 信 息 高 速 传 播 相 关 的 高 收 益, 但 也 使 得 网 络 连 接 成 本 的 增 加 ; 网 络 B, C 和 网 络 E, F 相 比 于 网 络 A 和 网 络 D 具 有 较 小 的 网 络 连 接 成 本, 各 节 点 之 间 也 能 实 现 信 息 的 有 效 传 播. 因 此, 对 于 任 意 规 模 的 网 络 都 可 以 采 取 一 定 的 方 式 对 其 连 接 模 式 进 行 优 化 和 控 制, 以 使 网 络 获 得 较 高 的 网 络 连 接 增 益. 从 图 1 可 以 看 出, 网 络 连 接 的 高 增 益 与 适 当 数 量 的 信 息 连 接 有 关 : 随 着 网 络 平 均 连 接 度 的 增 大, 会 使 得 网 络 节 点 之 间 最 短 路 径 长 度 的 减 小 而 增 大 网 络 连 接 的 增 益 ; 同 时, 过 大 的 网 络 平 均 连 接 度 又 会 产 生 由 于 过 量 的 信 息 连 接 所 带 来 的 较 高 的 网 络 连 接 成 本 费 用. 因 此, 本 文 综 合 考 虑 网 络 各 节 点 之 间 的 连 接 程 度 和 最 短 路 径 长 度, 对 网 络 连 接 增 益 I 进 行 定 义 : I = f (E) (1 C), (3) 式 中, f (E) 为 复 杂 网 络 连 接 的 收 益, C 为 复 杂 网 络 连 接 的 成 本, E 为 网 络 效 率. 150201-2

图 1 简 单 通 信 网 络 拓 扑 结 构 图 对 于 网 络 中 传 输 的 信 息 而 言, 如 果 节 点 对 之 间 距 离 很 大, 但 是 要 保 持 信 息 传 输 的 完 整 性, 那 么 该 节 点 对 之 间 信 息 传 输 所 消 耗 的 资 源 就 很 多 ; 反 之, 节 点 之 间 信 息 传 输 就 很 容 易. 由 于 网 络 效 率 表 征 了 网 络 中 节 点 的 平 均 接 近 程 度, 因 此 网 络 效 率 在 一 定 程 度 上 反 映 了 整 个 网 络 的 连 接 收 益. 网 络 效 率 越 高, 表 明 节 点 对 之 间 距 离 越 短 网 络 信 息 流 通 越 容 易 网 络 信 息 传 输 负 载 越 小 收 益 越 大. 因 此, 本 文 将 f (E) 定 义 如 下 : f (E) = E E max, (4) 式 中, E 和 E max 分 别 表 示 网 络 效 率 和 网 络 效 率 最 大 值. 对 于 网 络 效 率 最 大 值 E max, 我 们 考 虑 一 个 理 想 化 的 例 子 : 全 连 通 网 络. 由 于 全 连 通 网 络 中 节 点 之 间 充 分 连 接, 各 节 点 之 间 距 离 都 能 达 到 最 小 值, 使 得 它 们 之 间 的 信 息 能 够 以 最 高 的 效 率 进 行 传 播 ; 当 网 络 在 全 连 通 基 础 上 去 除 一 定 数 量 边, 会 导 致 一 定 数 量 节 点 之 间 最 短 距 离 的 增 大 而 减 少 网 络 的 效 率. 由 此 可 知, 全 连 通 网 络 的 效 率 才 能 达 到 最 大 值, 本 文 所 用 到 的 E max 是 指 全 连 通 网 络 的 效 率, 例 如 图 1 中 网 络 A 和 D 的 效 率 即 为 该 简 单 加 权 和 无 权 通 信 网 络 的 E max. 从 (4) 式 可 以 看 出, f (E) [0,1]. 当 我 们 利 用 网 络 模 型 来 分 析 现 实 网 络 时, 一 个 重 要 的 变 量 就 是 网 络 成 本. 我 们 期 望 一 个 网 络 边 数 增 加 时, 它 的 效 率 能 够 增 加 得 更 快 ; 或 者 网 络 边 数 目 固 定 的 情 况 下, 通 过 改 变 网 络 连 接 情 况 来 提 高 网 络 效 率. 因 此 现 实 网 络 的 构 建 往 往 围 绕 网 络 建 设 的 成 本 和 效 率 而 展 开. 对 于 网 络 节 点 所 消 耗 的 资 源, 单 纯 运 用 图 论 的 观 点 可 以 用 节 点 度 值 介 数 等 等 来 表 示, 但 是 许 多 实 际 的 通 信 网 络, 不 同 路 由 策 略 使 得 各 节 点 的 连 接 成 本 并 不 依 赖 于 网 络 的 度 值 和 介 数. 为 了 表 征 网 络 连 接 的 成 本 C, 本 文 用 网 络 边 连 接 程 度 来 表 示, 并 将 其 定 义 如 下 : C = n α i j γ(α i j) i j G, (5) C max 式 中, a i j 与 a i j 分 别 表 示 网 络 邻 接 矩 阵 和 边 权 矩 阵 中 的 元 素 ; γ( ) 表 示 网 络 边 连 接 的 成 本 因 子 函 数, 它 计 算 的 是 建 立 给 定 长 度 的 连 接 所 需 要 的 成 本 ; C max 表 示 网 络 成 本 最 大 值. 对 于 γ( ), 本 文 将 其 定 义 如 下 : β α i j, α i j d i j, γ(α i j ) = ρ α i j, d i j < α i j <, 0 α i j =, (6) 式 中, d i j 表 示 节 点 i 和 j 之 间 的 最 短 距 离 ; β, ρ 分 别 表 示 网 络 建 立 单 位 长 度 连 接 所 需 成 本 的 调 节 因 子. 一 般 情 况 下, 我 们 认 为 β ρ, 使 其 在 无 权 网 络 和 加 权 网 络 都 适 用. 定 义 (6) 式 的 目 的 是 为 了 辨 别 网 络 中 的 冗 余 边 和 必 需 边, 并 且 给 它 们 赋 予 不 同 的 网 络 建 设 成 本 值. 当 d i j < α i j 时, 可 知 该 边 为 网 络 的 冗 余 边, 通 过 β ρ, 使 得 网 络 冗 余 边 的 建 设 成 本 高 于 网 络 必 需 边. 对 于 C max, 由 于 全 连 通 的 网 络 各 节 点 之 间 充 分 连 接, 导 致 其 网 络 连 接 成 本 达 到 最 大 值, 因 此 可 以 将 C max 定 义 如 下 : C max = n i j G q i jγ(q i j ) = n i j G γ(q i j ), (7) 式 中, q i j 和 q i j 分 别 表 示 全 连 通 网 络 邻 接 矩 阵 和 边 权 矩 阵 中 的 元 素. 从 (5) 式 可 以 看 出, C [0,1]. 由 于 f (E) 和 C 被 分 别 定 义 在 [0,1] 之 间, 因 此 我 们 可 以 运 用 (3) 式 对 网 络 连 接 成 本 收 益 进 行 研 究. 当 网 络 为 全 连 通 网 络 时, 其 网 络 连 接 收 益 和 成 本 均 达 到 最 大 值 1, 而 它 的 网 络 连 接 增 益 却 为 0, 这 150201-3

也 是 全 连 通 网 络 在 现 实 世 界 中 很 少 采 用 的 重 要 原 因 之 一, 同 时 也 说 明 了 本 文 模 型 的 合 理 性. 2.3 算 法 设 计 下 面 我 们 给 出 评 估 网 络 连 接 增 益 的 简 单 算 法 步 骤 : 输 入 : 边 权 矩 阵 A = (α i j ) n n 邻 接 矩 阵 A = (α i j ) n n 相 连 矩 阵 Z = (z i j ) n p, β, ρ. 输 出 : 网 络 连 接 增 益 I. Begin 1) 根 据 A = (α i j ) n n, 计 算 所 有 节 点 对 之 间 的 最 短 距 离 矩 阵 [d i j ] n n //Floyd 算 法 ; 2) 构 造 相 同 规 模 的 全 连 通 网 络, 根 据 (2) 式 和 (7) 式 分 别 计 算 E max 和 C max ; 3) 根 据 [d i j ] n n, 利 用 (2) 式 和 (4) 式 计 算 f (E); 4) 根 据 [d i j ] n n 和 A = (α i j ) n n, 利 用 (5) 式 计 算 C; 5) 根 据 (3) 式, 输 出 I. End 从 上 述 算 法 步 骤 可 以 看 出, 对 网 络 连 接 成 本 收 益 的 评 估, 关 键 在 于 网 络 最 短 距 离 矩 阵 [d i j ] n n 的 确 定, 其 算 法 的 时 间 复 杂 度 为 O(n 3 ). 通 过 对 Floyd 算 法 的 分 析 可 知, Floyd 算 法 在 计 算 最 短 距 离 矩 阵 [d i j ] n n 过 程 中, 任 意 节 点 对 之 间 最 短 距 离 的 确 定 都 需 要 对 距 离 矩 阵 进 行 n 次 循 环, 但 是 当 网 络 中 所 有 节 点 对 之 间 的 最 短 距 离 都 已 经 找 到 时, 我 们 就 会 发 现 [d i j ] n n 在 后 续 循 环 过 程 中 保 持 不 变. 因 此, 在 求 解 [d i j ] n n 过 程 中, 如 果 盲 目 地 进 行 n 次 循 环, 势 必 会 造 成 计 算 资 源 的 浪 费 提 高 算 法 的 时 间 复 杂 度. 基 于 此, 本 文 在 运 用 Floyd 算 法 计 算 [d i j ] 过 程 中, 将 中 间 节 点 循 环 提 到 最 内 层 循 环, 运 用 网 络 相 连 矩 阵 Z = (z i j ) n p 对 其 进 行 优 化. 优 化 后 的 复 杂 网 络 最 短 路 径 计 算 算 法 流 程 如 图 2 所 示. 通 过 分 析 可 以 发 现, 网 络 相 连 矩 阵 Z = (z i j ) n p 的 列 数 值 p 为 网 络 中 节 点 的 最 大 度 值 ; 当 网 络 中 所 有 节 点 对 之 间 的 最 短 距 离 都 已 经 找 到 时, 网 络 节 点 之 间 的 最 大 距 离 ( 网 络 直 径 R) 也 已 经 确 定. 由 此, 图 2 所 示 算 法 时 间 复 杂 性 为 O(Mpn 2 ), M 表 示 确 定 网 络 直 径 R 所 需 的 循 环 次 数, p 表 示 网 络 节 点 的 最 大 度 值. 由 于 现 实 世 界 大 多 数 实 际 网 络 都 是 稀 疏 网 络 并 具 有 小 世 界 特 性, 网 络 节 点 之 间 连 接 不 是 很 充 分, 网 络 节 点 的 最 大 度 值 取 值 较 小 网 络 直 径 R n, 即 使 是 无 标 度 网 络 节 点 最 大 度 值 较 大, 也 只 有 少 数 节 点 具 有 较 大 度 值, 因 此 本 文 提 出 的 算 法 在 计 算 实 际 网 络 连 接 增 益 时 其 时 间 复 杂 性 可 以 达 到 O(n 2 ), 对 大 规 模 复 杂 网 络 拓 扑 连 接 优 化 控 制 可 以 获 得 理 想 的 计 算 能 力. 图 2 最 短 距 离 矩 阵 计 算 算 法 流 程 图 3 数 值 仿 真 与 分 析 3.1 模 型 有 效 性 分 析 为 了 对 本 文 所 提 模 型 有 效 性 进 行 分 析, 本 文 以 图 1 所 示 简 单 通 信 网 络 为 例, 对 其 网 络 连 接 增 益 进 行 比 较 分 析. 通 过 对 图 1 进 行 简 单 分 析, 可 以 发 现 加 权 网 络 A, B, C 中 : 网 络 A 存 在 多 条 冗 余 路 径, 如 l f e, l ae, l bc, l cd ; 网 络 B 也 存 在 冗 余 路 径 ; 只 有 网 络 C 连 接 相 对 合 理. 对 于 图 1 中 的 无 权 网 络, 虽 然 不 能 直 观 判 断 网 络 中 的 冗 余 路 径, 但 是 它 们 之 间 网 络 连 150201-4

接 增 益 是 不 同 的. 运 用 本 文 所 提 模 型 对 图 1 中 网 络 连 接 增 益 进 行 计 算, 结 果 如 表 1 所 示 (β = 1, ρ = 4). 通 过 表 1 可 以 看 出, 网 络 A 和 网 络 D 的 充 分 连 接, 使 得 它 各 节 点 之 间 能 够 以 最 小 的 路 径 长 度 进 行 信 息 交 互, 使 其 效 率 达 到 最 大 值, 增 大 了 网 络 连 接 收 益, 但 是 网 络 连 接 程 度 的 增 大, 造 成 了 网 络 连 接 的 过 度 冗 余 和 连 接 成 本 的 增 加, 导 致 网 络 A 和 网 络 D 具 有 最 小 的 网 络 连 接 增 益 ; 网 络 B 和 网 络 C 虽 然 具 有 相 同 的 网 络 效 率 值, 但 是 网 络 C 较 低 的 网 络 连 接 程 度 使 得 它 具 有 最 高 的 网 络 连 接 增 益 ; 网 络 F 也 具 有 相 同 的 特 性. 计 算 结 果 与 理 论 分 析 一 致, 说 明 了 本 文 方 法 的 有 效 性, 它 能 有 效 权 衡 加 权 与 无 权 网 络 构 建 过 程 中 网 络 连 接 收 益 和 网 络 连 接 成 本. 对 于 图 1 中 所 示 环 形 网 络 链 状 网 络 星 形 网 络 3 种 特 殊 网 络 连 接 模 式, 星 形 网 络 具 有 最 高 的 网 络 连 接 收 益 和 最 小 的 网 络 连 接 成 本, 其 连 接 模 式 最 优, 究 其 原 因 是 由 于 星 形 网 络 能 够 以 最 少 的 连 接 数 使 各 节 点 之 间 的 路 径 长 度 最 小. 无 权 网 络 计 算 结 果 表 明, 网 络 节 点 之 间 的 充 分 连 接 不 一 定 会 提 高 网 络 连 接 增 益, 适 当 地 对 复 杂 网 络 中 信 息 连 接 度 和 连 接 方 式 进 行 控 制, 可 以 获 得 最 优 的 网 络 连 接 性 能. 表 1 不 同 网 络 连 接 增 益 比 较 表 类 型 网 络 E max E f (E) C max C I 加 权 网 络 A 0.83 1 1 0 B 0.83 0.67 0.80 52 0.69 0.25 C 0.67 0.80 0.23 0.62 D 1 1 1 0 E 0.80 0.80 0.60 0.32 无 权 F 1 0.67 0.67 30 0.40 0.40 网 络 G 0.67 0.67 0.40 0.40 H 0.58 0.58 0.33 0.38 I 0.67 0.67 0.33 0.44 3.2 算 法 效 率 分 析 为 了 对 本 文 所 提 算 法 效 率 进 行 分 析, 运 用 该 优 化 算 法 在 Intel Core i5 3.10 GHz 微 机 上 运 行 MAT- LAB 程 序 对 边 权 为 1 的 不 同 规 模 小 世 界 网 络 [14] ( 每 个 节 点 与 周 围 80 个 节 点 相 连, 边 重 连 的 概 率 为 0.6) 的 网 络 连 接 增 益 进 行 计 算. 通 过 仿 真, 可 以 得 到 算 法 执 行 时 间 随 网 络 规 模 的 变 化 趋 势 如 图 3 所 示 ( 多 次 仿 真 平 均 值 ). 图 3 不 同 规 模 小 世 界 网 络 算 法 执 行 效 率 图 从 图 3 中 可 以 看 出, 本 文 优 化 算 法 相 比 于 Floyd 算 法 具 有 更 高 的 计 算 效 率, 计 算 节 点 规 模 为 1000 的 小 世 界 网 络 的 连 接 增 益 不 超 过 10 s, 能 够 适 用 于 大 规 模 小 世 界 网 络 拓 扑 连 接 优 化 控 制 方 法 中. 3.3 网 络 拓 扑 连 接 优 化 控 制 仿 真 分 析 为 了 优 化 小 世 界 网 络 的 连 接 模 式, 本 文 通 过 构 造 网 络 规 模 为 400, 边 权 为 1, 平 均 度 值 分 别 为 6, 12, 20, 30 的 小 世 界 网 络 进 行 分 析. 通 过 仿 真 计 算, 可 以 得 到 小 世 界 网 络 连 接 增 益 随 网 络 边 重 连 概 率 p 的 变 化 趋 势, 如 图 4 所 示 (β = 1, ρ = 2, 多 次 仿 真 平 均 值 ). 通 过 图 4 可 以 看 出, 当 网 络 平 均 度 值 一 定 时, 由 于 网 络 连 接 成 本 没 有 变 化, 网 络 边 重 连 概 率 p 的 增 大, 会 缩 短 网 络 节 点 对 之 间 的 最 短 路 径 长 度, 提 高 网 络 整 体 效 率, 增 加 网 络 连 接 收 益. 因 此, 网 络 连 接 的 增 益 随 p 的 增 大 而 增 加. 同 时, 网 络 连 接 增 益 150201-5

也 会 随 着 平 均 度 值 的 增 大 而 增 加, 但 是 当 网 络 平 均 度 值 达 到 一 定 数 值 时, 网 络 连 接 增 益 增 长 变 缓. 为 了 确 定 小 世 界 网 络 的 最 佳 平 均 度 值, 本 文 取 β = 1, ρ = 2, 边 重 连 概 率 p = 0.6, 构 造 网 络 规 模 为 400 的 小 世 界 网 络 进 行 仿 真 计 算, 可 得 小 世 界 网 络 平 均 度 值 对 网 络 连 接 增 益 的 影 响 图, 如 图 5 所 示 ( 多 次 仿 真 平 均 值 ). 点 与 不 同 数 目 节 点 相 连 的 无 标 度 网 络 进 行 比 较 分 析. 通 过 仿 真 计 算, 可 以 得 到 无 标 度 网 络 连 接 增 益 随 新 增 节 点 边 数 目 的 变 化 趋 势, 如 图 6 所 示 (β = 1, ρ = 2, 多 次 仿 真 平 均 值 ). 图 6 无 标 度 网 络 连 接 增 益 示 意 图 图 4 边 重 连 概 率 对 网 络 连 接 增 益 影 响 图 从 图 6 可 以 看 出, 当 网 络 规 模 一 定 时, 无 标 度 网 络 新 增 节 点 边 数 目 在 很 大 程 度 上 决 定 着 网 络 连 接 增 益, 并 且 存 在 一 个 边 阈 值 26, 能 够 使 网 络 的 连 接 增 益 达 到 最 大. 综 合 图 4 至 图 6 仿 真 结 果, 说 明 复 杂 网 络 构 建 过 程 中, 可 以 采 取 一 定 方 式 对 网 络 的 连 接 模 式 进 行 优 化, 小 世 界 网 络 和 无 标 度 网 络 均 存 在 一 个 最 优 的 网 络 平 均 度 值 能 够 使 网 络 取 得 最 优 的 网 络 连 接 增 益. 4 结 论 图 5 平 均 度 值 对 网 络 连 接 增 益 影 响 图 通 过 图 5 可 以 看 出, 当 网 络 平 均 度 值 小 于 一 定 数 值 时, 由 于 网 络 连 接 成 本 小, 增 大 网 络 的 平 均 连 接 度, 可 以 显 著 改 善 网 络 连 接 增 益 ; 但 是 网 络 平 均 度 值 增 大 到 一 定 程 度 时, 网 络 平 均 连 接 度 的 增 加, 会 使 得 网 络 连 接 成 本 大 于 网 络 平 均 路 径 长 度 减 小 所 带 来 的 网 络 连 接 收 益, 导 致 网 络 连 接 增 益 的 减 小. 在 小 世 界 网 络 中, 存 在 一 个 最 佳 的 网 络 平 均 度 值, 能 够 使 得 网 络 的 连 接 增 益 最 优. 为 了 优 化 无 标 度 网 络 连 接 模 式, 本 文 按 照 文 献 [15] 提 供 的 方 法, 通 过 构 造 网 络 规 模 为 400, 新 增 节 为 了 增 加 实 际 网 络 连 接 增 益 减 少 网 络 连 接 成 本, 提 出 了 一 种 基 于 网 络 效 率 和 平 均 连 接 度 的 网 络 拓 扑 连 接 优 化 控 制 方 法, 该 方 法 利 用 网 络 效 率 来 表 征 网 络 连 接 收 益 用 网 络 平 均 连 接 度 表 征 网 络 连 接 成 本, 并 提 出 了 其 计 算 优 化 算 法. 当 网 络 具 有 小 世 界 特 性, 且 M n 时, 算 法 的 时 间 复 杂 度 可 以 达 到 O(n 2 ). 实 验 分 析 表 明, 可 以 采 取 一 定 的 方 式 对 实 际 复 杂 网 络 拓 扑 连 接 进 行 优 化 控 制, 网 络 节 点 之 间 的 充 分 连 接 不 一 定 会 提 高 网 络 连 接 增 益, 适 当 地 对 复 杂 网 络 中 的 信 息 连 接 度 和 连 接 方 式 进 行 控 制, 可 以 获 得 最 优 的 网 络 连 接 性 能 ; 小 世 界 和 无 标 度 网 络 均 存 在 一 个 最 佳 的 网 络 平 均 度 值 能 够 使 网 络 取 得 最 优 的 网 络 连 接 增 益. 150201-6

[1] Zhao J, Li J P, Guo P, Zhang Y Z, Wang S H, Li X L 2009 International Conference on Computing and Intelligence Analysis Chengdu, China, October 23 25, 2009 p266 [2] Liu Y H, Chen H C, Yang C 2008 International Conference on Natural Computation Jinan, China, October 18 20, 2008 p267 [3] Li T, Pei W J, Wang S P 2009 Acta Phys. Sin. 58 5903 (in Chinese) [ 李 涛, 裴 文 江, 王 少 平 2009 物 理 学 报 58 5903] [4] Wu J J, Gao Z Y, Sun H J 2008 Physica A 387 1025 [5] Souza F S H, Cunha A S da, Mateus G R 2009 IEEE INFOCOM Workshops Rio de Janeiro, Brazil, April 19 25 2009 p1 [6] Jing W P, Liu Y Q, Zhang X 2010 International Symposium on Systems and Control in Aeronautics and Astronautics Harbin, China, June 8 10 2010 p1297 [7] Fan W, Ye D F, Yang M X, Zhang L 2011 Advanced Materials Research 267 738 [8] Wang L F, Wang Q L, Kong Z, Jing Y W 2010 Chin. Phys. B 19 080207 [9] Holme P, Kim B J, Fodor V 2010 European Physical Journal B 73 597 [10] Hu J M, Song J Y, Zhang M C, Kang X J 2008 Tsinghua Science and Technology 13 229 [11] Rafiee M, Bayen A M 2010 IEEE Conference on Decision and Control Atlanta, USA, December 15 17 2010 p3877 [12] Xue Y H, Wang J, Li L, He D R, Hu B B 2010 Phys. Rev. E 81 037101 [13] Ouveysi I, Shu F, Chen W, Shen G X, Zukerman M 2010 Optical Switching and Networking 7 95 [14] Watts D J, Strogatz S H 1998 Nature 393 440 [15] Barabási A L, Albert R 1999 Science 286 509 Control method for complex network topological connection optimization Zhou Xuan 1)2) Yang Fan 3) Zhang Feng-Ming 1) Zhou Wei-Ping 2) Zou Wei 2) 1) ( Material Management and Safety Engineering College, Air Force Engineering University, Xi an 710051, China ) 2) ( Navy Academy of Armament, Beijing 100161, China ) 3) ( Normal College, Tibet University, Lasa 850000, China ) ( Received 9 September 2012; revised manuscript received 17 April 2013 ) Abstract In order to enhance complex network connection income and reduce network connection cost, a network topological connection optimization control method was proposed based on network efficiency and average connection degree, which used network efficiency and average connection degree to denote the gain and cost of network connection respectively, and an optimized arithmetic whose time complexity was O(Mpn 2 ) was provided. Experimental analysis shows that the topological connection of complex network can be optimized by some measures, and an average degree threshold existed in small world network and scale-free network which can make the network s income reach the maximum value. Keywords: complex network, topological connection, optimization control, connection income PACS: 02.10.Ox DOI: 10.7498/aps.62.150201 Corresponding author. E-mail: zhouxuan 333@126.com 150201-7