南 京 航 空 航 天 大 学硕 士 学 位 论 文一 类 图 值 过 程 不 具 有 大 团 聚 性 的 一 个 充 分 条 件姓 名 ： 乔 小 燕申 请 学 位 级 别 ： 硕 士专 业 ： 概 率 论 与 数 理 统 计指 导 教 师 ： 耿 显 民2010-12南 京 航 空 航 天 大 学 硕 士 学 位 论 文摘 要复 杂 网 络 近 年 来 在 国 内 外 掀 起 了 研 究 的 热 潮 ， 受 到 来 自 科 学 与 工 程 各 个 领 域 研 究 者 的 强 烈关 注 。 现 实 世 界 中 的 许 多 系 统 都 可 以 通 过 复 杂 网 络 进 行 描 述 ， 例 如 ： 社 会 网 、 万 维 网 、 因 特 网等 。 从 数 学 的 角 度 看 ， 任 何 一 个 网 络 都 可 以 抽 象 为 一 个 由 点 集 V 和 边 集 E 构 成 的 图 ， 其 中 ， 结点 代 表 网 络 中 的 元 素 ， 边 代 表 个 体 间 的 关 联 性 。 许 多 网 络 演 化 模 型 都 可 以 被 看 作 状 态 空 间 是 图集 的 马 尔 可 夫 过 程 。 与 经 典 随 机 图 过 程 不 同 ， 图 值 随 机 过 程 研 究 节 点 和 边 都 随 机 变 化 的 图 过 程 。这 里 ， 随 时 间 的 变 化 ， 节 点 的 增 加 和 删 除 是 随 机 的 ， 在 删 除 节 点 的 同 时 也 删 除 该 节 点 所 连 接 的边 。 图 值 过 程 的 团 聚 性 是 人 们 感 兴 趣 的 一 个 主 要 性 质 ， 特 别 是 具 有 这 种 特 性 的 图 值 过 程 满 足 的充 分 条 件 ， 更 是 引 起 人 们 极 大 的 关 注 。 为 了 搞 清 复 杂 网 络 特 征 的 形 成 机 制 ， 研 究 人 员 提 出 了 众多 的 网 络 演 化 模 型 。 然 而 ， 到 目 前 为 止 ， 对 于 图 值 过 程 演 化 模 型 的 特 征 研 究 大 都 停 留 在 数 值 仿真 或 是 平 均 场 ， 主 方 程 等 统 计 物 理 的 方 法 ， 有 些 模 型 缺 乏 数 学 上 的 严 格 性 。 本 文 研 究 具 有 加 点加 边 机 制 的 图 值 马 氏 过 程 ， 从 随 机 分 析 角 度 出 发 ， 给 出 这 类 图 值 马 氏 过 程 不 具 有 大 团 聚 性 的 一个 充 分 条 件 。关键词：复 杂 网 络 ， 图 值 马 氏 过 程 ， 团 聚 系 数 ， 确 定 性 连 接 ， 无 标 度 性I一 类 图 值 过 程 不 具 有 大 团 聚 性 的 一 个 充 分 条 件AbstractIn recent years, complex networks have set off a wave of domestic and foreign research, andhave been strongly concerned by the researchers in all areas from the science and engineering. Manyreal world systems can be described by complex networks, such as social networks, the World WideWeb, the Internet and so on. From the mathematical point of view, any network can beabstracted as a graph consisting of node-set V and edge-set E , where nodes representthe elements of the network and edges represent the relationship between elements.Many evolution network models can be viewed as graph-valued Markov processes.Different from the classical random graph process, graph-valued stochastic process discusses thegraph process where nodes and edges vary randomly. Here, add and remove nodes randomly over thetime, when a node is removed, the edges linking to it are also removed. The scale-free behavior forthe high clustering property of the graph-valued process are the main property that people areinterested in, especially the sufficient condition for graph-valued process possessing the propertyreally catches researchers attention. To find out features of the formation mechanism of complexnetworks, researches have propose many models of evolution networks. However, up to date, thefeatures researches of graph-valued process of evolution models have been remained mostly innumerical simulation or the mean-field theory and the main equation and so on, which are themethods of statistical physics, and some models even lack rigorly mathematically. In this paper, westudy the graph-valued Markov process with new nodes and edges, from the perspectiov of stochasticanalysis, we get the sufficient condition for the Markov processes which do not express the highclustering property.Keywords: complex networks, graph-valued Markov process, clusteing cofficient, intrinsic link,scale-free propertyII一 类 图 值 过 程 不 具 有 大 团 聚 性 的 一 个 充 分 条 件注 释 表t 时 刻 ， 操 作 步N(t) t 时 刻 网 络 总 节 点 数, , P VtGtki (t)P(k )完 备 的 概 率 空 间t 时 刻 网 络 中 节 点 构 成 的 集 合t 时 刻 所 有 可 能 生 成 的 图 的 集 合节 点 i 在 t 时 刻 的 度稳 态 时 网 络 的 度 分 布 标 度 指 数ni (t)ci (t)节 点 i 在 t 时 刻 邻 点 间 边 数节 点 i 在 t 时 刻 的 团 聚 系 数C 稳 态 时 网 络 的 团 聚 系 数IV承诺书本 人 声 明 所 呈 交 的 博 士 学 位 论 文 是 本 人 在 导 师 指 导 下 进行 的 研 究 工 作 及 取 得 的 研 究 成 果 。 除 了 文 中 特 别 加 以 标 注 和 致谢 的 地 方 外 ， 论 文 中 不 包 含 其 他 人 已 经 发 表 或 撰 写 过 的 研 究 成果 ， 也 不 包 含 为 获 得 南 京 航 空 航 天 大 学 或 其 他 教 育 机 构 的 学 位或证书而使用过的材料。本 人 授 权 南 京 航 空 航 天 大 学 可 以 将 学 位 论 文 的 全 部 或 部分 内 容 编 入 有 关 数 据 库 进 行 检 索 ， 可 以 采 用 影 印 、 缩 印 或 扫 描等复制手段保存、汇编学位论文。（保密的学位论文在解密后适用本承诺书）作 者 签 名 ：日 期 ：南 京 航 空 航 天 大 学 硕 士 学 位 论 文第 一 章 绪 论1.1 选 题 背 景网 络 是 顶 点 或 节 点 以 及 边 的 集 合 。 网 络 形 式 的 系 统 随 处 可 见 ， 我 们 可 通 过 形 形 色 色 的 网 络来描述自然界中存在的大量复杂系统 1。例如，因特网、社会关系网络、万维网、组织网络、神 经 网 络 、 公 司 间 商 务 关 系 网 络 食 物 网 、 新 陈 代 谢 网 络 、 分 布 网 络 、 邮 政 运 输 路 线 分 布 、 论 文之 间 互 引 述 而 形 成 的 网 络 ， 以 及 其 它 种 种 形 式 的 网 络 。 数 学 中 以 图 论 形 式 开 展 的 网 络 研 究 是 离散 数 学 的 基 柱 之 一 。 1735 年 ， 欧 拉 提 出 的 著 名 的 七 桥 问 题 ， 这 个 问 题 解 是 首 个 真 正 的 网 络 理 论证 明 。 二 十 世 纪 期 间 ， 网 络 发 展 成 为 一 个 重 要 的 知 识 实 体 。钱 学 森 给 复 杂 网 络 的 一 个 较 严 格 的 定 义 ： 具 有 自 组 织 、 自 相 似 、 吸 引 子 、 小 世 界 、无 标 度 中 部 分 或 全 部 性 质 的 网 络 称 为 复 杂 网 络 。 复 杂 网 状结构 描 述 各种各 样 的 有着高 智 能及高技术重要性的系统。例如，国际互联网 2被描述为通过各种物理的或无线的连接把计算机和 路 由 器 连 接 在 一 起 的 复 杂 网 络 ； 细 胞 3-4就 被 完 美 地 描 述 为 通 过 细 胞 内 的 各 种 物 质 的 化 学 反 应连 接 化 学 物 的 复 杂 网 络 ； 万 维 网 5-6是 一 个 网 页 通 过 超 链 接 而 连 接 起 来 的 巨 大 的 虚 拟 网 ； 计 算 机网 络 7被 描 述 为 计 算 机 通 过 通 信 介 质 相 互 连 接 形 成 的 网 络 ； 奇 想 和 理 念 在 社 会 网 8-9上 传 播 ， 其节 点 就 是 人 类 ， 边 就 表 示 各 种 社 会 关 系 等 等 。 这 几 个 实 际 的 例 子 具 有 典 型 性 ， 它 们 代 表 了 近 年来 引 起 科 学 界 各 领 域 进 行 研 究 复 杂 网 络 的 拓 扑 结 构 ， 但 由 于 研 究 条 件 和 试 验 条 件 的 限 制 等 原 因 ，了 解 这 类 交 叉 系 统 的 愿 望 遇 到 了 很 大 的 困 难 。 在 过 去 几 年 中 ， 我 们 渐 渐 认 识 到 统 计 力 学 的 工 具也 为 描 述 这 些 交 叉 系 统 提 供 了 一 个 理 想 的 结 构 方 法 。复 杂 网 络 研 究 传 统 上 属 图 论 范 畴 。 图 论 研 究 最 初