描述
开 本: 16开包 装: 平装胶订是否套装: 否国际标准书号ISBN: 9787030664730
编辑推荐
计算机网络,网络理论
目 录
目录
前言
第1章 绪论 1
1.1 引言 1
1.2 网络理论的发展简史 1
1.2.1 网络理论的起源 1
1.2.2 规则网络理论阶段 3
1.2.3 随机网络理论阶段 3
1.2.4 复杂网络理论阶段 4
1.3 网络的矩阵表示与分类 5
1.3.1 网络的邻接矩阵表示方式 5
1.3.2 网络分类 5
1.4 复杂网络的定义和特性 7
1.4.1 复杂网络的定义 7
1.4.2 复杂网络的特性 7
1.4.3 小世界网络和无标度网络 8
1.5 复杂网络理论在物流快递领域的应用研究 9
1.5.1 复杂网络理论在物流快递网络的应用研究 9
1.5.2 复杂网络理论在快递产业竞争领域的应用研究 11
1.6 本书内容安排 12
1.7 本章小结 13
第2章 复杂网络理论研究的基本框架 14
2.1 复杂网络拓扑描述及结构特征度量 14
2.1.1 复杂网络及其拓扑描述 14
2.1.2 复杂网络结构特征度量 18
2.2 复杂网络模型 26
2.2.1 规则网络模型 27
2.2.2 随机网络模型 28
2.2.3 小世界网络模型 29
2.2.4 无标度网络模型 30
2.2.5 其他复杂网络模型 33
2.3 复杂网络的动力学行为 36
2.3.1 复杂网络上的疾病扩散 37
2.3.2 复杂网络上的同步 39
2.3.3 复杂网络上的博弈 40
2.4 本章小结 44
第3章 网络分析软件基础 45
3.1 网络分析软件简介 45
3.1.1 UCINET简介 45
3.1.2 Pajek简介 45
3.1.3 NetMiner简介 46
3.1.4 STRUCTURE简介 46
3.1.5 MultiNet简介 46
3.1.6 StOCNET简介 47
3.2 UCINET软件基础 48
3.2.1 UCINET概述 48
3.2.2 UCINET的主菜单功能简介 50
3.2.3 UCINET的数据格式 54
3.2.4 UCINET数据预处理 56
3.3 Pajek软件基础 57
3.3.1 Pajek开发背景 57
3.3.2 Pajek数据类型结构 58
3.3.3 Pajek工作界面详解 62
3.3.4 Pajek的可视化成图功能 67
3.4 本章小结 68
第4章 MATLAB软件基础 69
4.1 MATLAB简介 69
4.1.1 MATLAB的发展沿革 69
4.1.2 MATLAB的安装和启动 70
4.1.3 MATLAB的操作界面 76
4.1.4 MATLAB的通用命令 81
4.1.5 MATLAB的各种文件 82
4.2 MATLAB语言基础 83
4.2.1 MATLAB的数据类型 83
4.2.2 常量与变量 86
4.2.3 标量、向量、矩阵与数组 87
4.2.4 字符串 88
4.2.5 运算符 89
4.2.6 命令、函数、表达式和语句 92
4.3 向量、矩阵和数组的运算 93
4.3.1 向量运算 93
4.3.2 矩阵运算 98
4.3.3 数组运算 112
4.4 结构数组 117
4.4.1 结构数组的创建 118
4.4.2 结构数组的操作 119
4.5 MATLAB程序设计 124
4.5.1 M文件 124
4.5.2 MATLAB程序控制结构 126
4.5.3 MATLAB程序调试 137
4.6 MATLAB数据可视化 140
4.6.1 MATLAB的图形窗口 140
4.6.2 二维图形绘制 140
4.6.3 三维图形绘制 146
4.7 本章小结 149
第5章 复杂网络拓扑图的软件绘制方法 150
5.1 复杂网络拓扑图的UCINET绘制方法——以快递网络为例 150
5.1.1 航空快递数据信息详细来源 150
5.1.2 航空快递网络的拓扑描述 150
5.1.3 UCINET绘制网络拓扑图 150
5.2 复杂网络拓扑图的Pajek绘制方法——以快递产业竞争关系网络为例 154
5.2.1 快递企业间竞争关系的定义 154
5.2.2 快递企业数据信息来源 155
5.2.3 快递产业竞争关系网络拓扑描述 155
5.2.4 Pajek绘制网络拓扑图——以国内跨省业务竞争关系网络为例 158
5.3 本章小结 161
第6章 复杂网络结构特征的度量方法 162
6.1 复杂网络的拓扑结构特征度量方法——以快递网络为例 162
6.1.1 小世界特性的UCINET计算方法 162
6.1.2 社区结构的UCINET计算方法 163
6.1.3 度分布特性的MATLAB计算方法 165
6.1.4 富人俱乐部的MATLAB计算方法 167
6.1.5 匹配形式的MATLAB计算方法 169
6.2 复杂网络加权结构特征的MATLAB计算方法——以快递产业竞争关系网络为例 171
6.2.1 强度分布特性的MATLAB计算方法 171
6.2.2 强度-度相关性的MATLAB计算方法 174
6.2.3 加权集聚性的MATLAB计算方法 180
6.2.4 加权匹配性的MATLAB计算方法 185
6.3 本章小结 189
第7章 复杂网络模型构建及MATLAB仿真 190
7.1 经典复杂网络模型的仿真 190
7.1.1 规则网络模型的MATLAB仿真 190
7.1.2 随机网络模型的MATLAB仿真 192
7.1.3 小世界网络模型的MATLAB仿真 195
7.1.4 BA无标度网络模型的MATLAB仿真 198
7.2 快递网络演化模型构建及MATLAB仿真 201
7.2.1 快递网络模型构建思路 201
7.2.2 快递网络演化模型构建 201
7.2.3 演化模型的MATLAB仿真框架 201
7.2.4 快递网络演化模型的MATLAB仿真程序及结果 202
7.3 快递产业竞争关系网络演化模型构建及MATLAB 仿真 207
7.3.1 快递产业竞争关系网络模型构建思路 207
7.3.2 快递产业竞争关系网络演化模型构建 210
7.3.3 演化模型的MATLAB仿真框架 211
7.3.4 快递产业竞争关系网络演化模型的MATLAB仿真程序 212
7.4 本章小结 219
第8章 复杂网络博弈模型构建及MATLAB仿真 219
8.1 经典复杂网络博弈模型的构建及MATLAB仿真 219
8.1.1 方格网上囚徒困境博弈模型的构建及MATLAB仿真 219
8.1.2 BA无标度网络上囚徒困境博弈模型的构建及MATLAB仿真 227
8.2 规则格子上牡鹿捕捉博弈模型构建及MATLAB仿真 235
8.2.1 规则网络上的牡鹿捕捉博弈 235
8.2.2 规则格子上博弈合作行为激励模型的构建 235
8.2.3 随机作用下牡鹿捕捉博弈的演化均衡解分析 237
8.2.4 规则格子上博弈合作行为激励模型的MATLAB仿真 238
8.3 异质社区网络上博弈模型的构建及MATLAB仿真 243
8.3.1 社区网络上的博弈研究概述 243
8.3.2 异质社区网络上的博弈 245
8.4 快递产业竞争关系网络上的价格博弈模型构建及MATLAB仿真 264
8.4.1 快递产业竞争关系网络上价格竞争博弈模型构建思路 264
8.4.2 快递产业竞争关系网络上的价格博弈模型构建 265
8.4.3 快递产业竞争关系网络上价格博弈模型的MATLAB 仿真 269
8.5 本章小结 289
参考文献 290
附录1 航空快递网络的关系矩阵A(N，N) 302
附录2 国内跨省业务快递企业经营城市列表 305
附录3 国内跨省业务快递企业经营地域城市编号对应表 308
附录4 国内跨省业务快递企业的竞争关系矩阵C(N2，N2) 317
彩图
前言
第1章 绪论 1
1.1 引言 1
1.2 网络理论的发展简史 1
1.2.1 网络理论的起源 1
1.2.2 规则网络理论阶段 3
1.2.3 随机网络理论阶段 3
1.2.4 复杂网络理论阶段 4
1.3 网络的矩阵表示与分类 5
1.3.1 网络的邻接矩阵表示方式 5
1.3.2 网络分类 5
1.4 复杂网络的定义和特性 7
1.4.1 复杂网络的定义 7
1.4.2 复杂网络的特性 7
1.4.3 小世界网络和无标度网络 8
1.5 复杂网络理论在物流快递领域的应用研究 9
1.5.1 复杂网络理论在物流快递网络的应用研究 9
1.5.2 复杂网络理论在快递产业竞争领域的应用研究 11
1.6 本书内容安排 12
1.7 本章小结 13
第2章 复杂网络理论研究的基本框架 14
2.1 复杂网络拓扑描述及结构特征度量 14
2.1.1 复杂网络及其拓扑描述 14
2.1.2 复杂网络结构特征度量 18
2.2 复杂网络模型 26
2.2.1 规则网络模型 27
2.2.2 随机网络模型 28
2.2.3 小世界网络模型 29
2.2.4 无标度网络模型 30
2.2.5 其他复杂网络模型 33
2.3 复杂网络的动力学行为 36
2.3.1 复杂网络上的疾病扩散 37
2.3.2 复杂网络上的同步 39
2.3.3 复杂网络上的博弈 40
2.4 本章小结 44
第3章 网络分析软件基础 45
3.1 网络分析软件简介 45
3.1.1 UCINET简介 45
3.1.2 Pajek简介 45
3.1.3 NetMiner简介 46
3.1.4 STRUCTURE简介 46
3.1.5 MultiNet简介 46
3.1.6 StOCNET简介 47
3.2 UCINET软件基础 48
3.2.1 UCINET概述 48
3.2.2 UCINET的主菜单功能简介 50
3.2.3 UCINET的数据格式 54
3.2.4 UCINET数据预处理 56
3.3 Pajek软件基础 57
3.3.1 Pajek开发背景 57
3.3.2 Pajek数据类型结构 58
3.3.3 Pajek工作界面详解 62
3.3.4 Pajek的可视化成图功能 67
3.4 本章小结 68
第4章 MATLAB软件基础 69
4.1 MATLAB简介 69
4.1.1 MATLAB的发展沿革 69
4.1.2 MATLAB的安装和启动 70
4.1.3 MATLAB的操作界面 76
4.1.4 MATLAB的通用命令 81
4.1.5 MATLAB的各种文件 82
4.2 MATLAB语言基础 83
4.2.1 MATLAB的数据类型 83
4.2.2 常量与变量 86
4.2.3 标量、向量、矩阵与数组 87
4.2.4 字符串 88
4.2.5 运算符 89
4.2.6 命令、函数、表达式和语句 92
4.3 向量、矩阵和数组的运算 93
4.3.1 向量运算 93
4.3.2 矩阵运算 98
4.3.3 数组运算 112
4.4 结构数组 117
4.4.1 结构数组的创建 118
4.4.2 结构数组的操作 119
4.5 MATLAB程序设计 124
4.5.1 M文件 124
4.5.2 MATLAB程序控制结构 126
4.5.3 MATLAB程序调试 137
4.6 MATLAB数据可视化 140
4.6.1 MATLAB的图形窗口 140
4.6.2 二维图形绘制 140
4.6.3 三维图形绘制 146
4.7 本章小结 149
第5章 复杂网络拓扑图的软件绘制方法 150
5.1 复杂网络拓扑图的UCINET绘制方法——以快递网络为例 150
5.1.1 航空快递数据信息详细来源 150
5.1.2 航空快递网络的拓扑描述 150
5.1.3 UCINET绘制网络拓扑图 150
5.2 复杂网络拓扑图的Pajek绘制方法——以快递产业竞争关系网络为例 154
5.2.1 快递企业间竞争关系的定义 154
5.2.2 快递企业数据信息来源 155
5.2.3 快递产业竞争关系网络拓扑描述 155
5.2.4 Pajek绘制网络拓扑图——以国内跨省业务竞争关系网络为例 158
5.3 本章小结 161
第6章 复杂网络结构特征的度量方法 162
6.1 复杂网络的拓扑结构特征度量方法——以快递网络为例 162
6.1.1 小世界特性的UCINET计算方法 162
6.1.2 社区结构的UCINET计算方法 163
6.1.3 度分布特性的MATLAB计算方法 165
6.1.4 富人俱乐部的MATLAB计算方法 167
6.1.5 匹配形式的MATLAB计算方法 169
6.2 复杂网络加权结构特征的MATLAB计算方法——以快递产业竞争关系网络为例 171
6.2.1 强度分布特性的MATLAB计算方法 171
6.2.2 强度-度相关性的MATLAB计算方法 174
6.2.3 加权集聚性的MATLAB计算方法 180
6.2.4 加权匹配性的MATLAB计算方法 185
6.3 本章小结 189
第7章 复杂网络模型构建及MATLAB仿真 190
7.1 经典复杂网络模型的仿真 190
7.1.1 规则网络模型的MATLAB仿真 190
7.1.2 随机网络模型的MATLAB仿真 192
7.1.3 小世界网络模型的MATLAB仿真 195
7.1.4 BA无标度网络模型的MATLAB仿真 198
7.2 快递网络演化模型构建及MATLAB仿真 201
7.2.1 快递网络模型构建思路 201
7.2.2 快递网络演化模型构建 201
7.2.3 演化模型的MATLAB仿真框架 201
7.2.4 快递网络演化模型的MATLAB仿真程序及结果 202
7.3 快递产业竞争关系网络演化模型构建及MATLAB 仿真 207
7.3.1 快递产业竞争关系网络模型构建思路 207
7.3.2 快递产业竞争关系网络演化模型构建 210
7.3.3 演化模型的MATLAB仿真框架 211
7.3.4 快递产业竞争关系网络演化模型的MATLAB仿真程序 212
7.4 本章小结 219
第8章 复杂网络博弈模型构建及MATLAB仿真 219
8.1 经典复杂网络博弈模型的构建及MATLAB仿真 219
8.1.1 方格网上囚徒困境博弈模型的构建及MATLAB仿真 219
8.1.2 BA无标度网络上囚徒困境博弈模型的构建及MATLAB仿真 227
8.2 规则格子上牡鹿捕捉博弈模型构建及MATLAB仿真 235
8.2.1 规则网络上的牡鹿捕捉博弈 235
8.2.2 规则格子上博弈合作行为激励模型的构建 235
8.2.3 随机作用下牡鹿捕捉博弈的演化均衡解分析 237
8.2.4 规则格子上博弈合作行为激励模型的MATLAB仿真 238
8.3 异质社区网络上博弈模型的构建及MATLAB仿真 243
8.3.1 社区网络上的博弈研究概述 243
8.3.2 异质社区网络上的博弈 245
8.4 快递产业竞争关系网络上的价格博弈模型构建及MATLAB仿真 264
8.4.1 快递产业竞争关系网络上价格竞争博弈模型构建思路 264
8.4.2 快递产业竞争关系网络上的价格博弈模型构建 265
8.4.3 快递产业竞争关系网络上价格博弈模型的MATLAB 仿真 269
8.5 本章小结 289
参考文献 290
附录1 航空快递网络的关系矩阵A(N，N) 302
附录2 国内跨省业务快递企业经营城市列表 305
附录3 国内跨省业务快递企业经营地域城市编号对应表 308
附录4 国内跨省业务快递企业的竞争关系矩阵C(N2，N2) 317
彩图
免费在线读
第1章 绪论
1.1 引言
从20 世纪七八十年代开始，复杂性问题的研究已引起国内外不同学科的科学家的关注。物理学家、生物学家、计算机科学家和经济学家等都开始不约而同地讨论和研究各自领域的复杂性问题，如自组织现象和自组织临界性、自适应问题、计算机与智能问题、生命与生物的演化、全球经济的演化、人类文化和语言的演变等。
随着人类认识能力的提高，人们发现自然界、人类社会、生物群体中的许多复杂系统都可以通过网络的概念加以描述。尤其是20 世纪九十年代以来，随着计算机技术和Internet 技术的迅猛发展，人类迈入了网络时代。人类已经生活在一个充满各种各样复杂网络的世界：从互联网(Internet)到万维网(WWW)，从大型电力网络到全球交通网络，从生物体的神经网络到各种新陈代谢网络，从科研合作网络到各种经济、政治、社会关系网络等。在上述背景下，网络科学成为多学科交叉的研究领域，它关注复杂网络的共性和处理它们的有效方法，从而增进人类对各种自然和人工复杂网络的理解。
尤其在近20 年间，复杂网络的研究飞速发展，其原因主要有以下几个方面：**，随着计算机技术的不断发展，人们数据获取能力的不断增强，建立了很多关于各种实际网络拓扑结构的大型数据库；第二，计算机计算能力的不断提高，使得人们可以处理的网络规模由以前的几十、几百个节点上升到了百万甚至是千万级的节点规模；第三，学科之间相互渗透，交叉学科的研究不断发展，使得人们可以获取不同领域的数据，从而发现不同数据类型隐藏下的一般控制规律。随着网络研究的不断深入，人们发现不同类型的网络中的网络结构特征和行为机制常常是一致的，在一个网络上得到的规律可以很容易地映射到另一个网络的研究中。这种不同网络具有一致或相似的结构性质或行为特征的现象，推动着网络研究以一个前所未有的速度向前发展，这类研究的对象常常被称作复杂网络(complex networks)。
1.2 网络理论的发展简史
1.2.1 网络理论的起源
网络理论研究起源于十八世纪欧拉对于哥尼斯堡“七桥问题”的研究，这是一个历史上著名的数学问题。普鲁士的哥尼斯堡(现在是俄罗斯的加里宁格勒)坐落在普瑞格尔河的两侧，包括两个大岛——克内夫和洛姆斯，它们通过7 座桥互相连接在一起，且与城市的两个大陆部分相连，如图1-1 所示。
图1-1 1736 年的哥尼斯堡镇[1]
当时，在哥尼斯堡镇流传着这样一个有趣的问题：一个人能否一次走完七座桥，且每座桥只走一次，*后返回原地？1736 年，著名数学家欧拉通过仔细观察哥尼斯堡镇七座桥的布局结构，向圣彼得堡学院提交了《哥尼斯堡七桥》的论文，并*终利用数学抽象法将这个问题抽象为一个由四个点、七条线构成的图，如图1-2 所示。由此，欧拉便将该问题转化为一个严格的数学问题：从图中任意一点出发，是否存在经过每条边一次而后返回原点的回路？这便是著名的“七桥问题”，也称为“一笔画问题”。
图1-2 哥尼斯堡镇“七桥问题”网络抽象图
不难看出，要一笔画成该图，必然只能有一个起点和一个终点，且由于该图中所有点均有两条以上的线与之相连(即所有点均构成了回路)，所以起点与终点必然重合，而一笔经过每一点总会产生一条入线和一条出线，故每一点都只能有偶数条线与之相连。在图1-2 中，四个点均是奇数条线与之相连，所以不存在经过每条边一次而后返回原点的回路。欧拉对“七桥问题”的研究，不仅成功地解决了“七桥问题”，而且开创了两个新的研究领域，即图论和拓扑学。这是复杂网络理论研究的起源。
1.2.2 规则网络理论阶段
自18 世纪开始，经过200 多年的发展，图在很多研究领域得到了应用，成为重要的研究工具。在*初的一个世纪，许多科学家们一直将复杂系统中各个实体之间的关系用某种规则的网络结构来表示。在这些网络中，每个节点仅与相近的几个节点存在关联，与其他大部分网络节点并不存在联系，并且呈现出某种规则的状态，如*近邻耦合网络、规则格子、星形网络等。
1.2.3 随机网络理论阶段
在图论及复杂网络理论的发展历程中，随机图理论(random graph theory)是继“七桥问题”之后提出的一个重要的、具有开创性意义的理论，由两个著名数学家Erdós 和Rényi 在20 世纪60 年代建立。
1959 年，数学家Erdós 和Rényi 对图论有了第二个里程碑式的贡献。他们用相对简单的随机图来描述网络，简称ER-随机图理论。Erdós 被称为20 世纪的欧拉，于1984 年获得沃尔夫奖。他善于与人合作，打破了数学领域的学者们喜欢个人独立研究的传统，一生中与众多合作者联合开展学术研究，发表过千余篇论文，涉及许多领域，与许多伟大的物理学家和数学家，如爱因斯坦、哥德尔、奥本海姆等有都密切学术交往。
ER-随机图理论对图论的研究影响非常大。在随后的近半个世纪，ER-随机图理论一直是科学家研究真实网络*有力的武器。随机网络是指，在由N 个节点构成的图中，以概率p 随机连接任意两个不存在连接的节点，重复这一过程而形成的网络，即两个节点之间连边与否不再是确定的事，而是由概率p 决定。换个角度来理解，在由N 个节点构成的图中，*多可以存在条边，从中随机连接M 条边所构成的网络就叫随机网络。如果选择，则这两种构造随机网络模型的方法就可以联系起来。随机网络和规则网络之间**的区别在于随机网络中引入了随机的方法形成网络。Erdós 和Rényi 系统研究了随机网络性质与概率p 的关系。他们发现，随机网络的许多重要的性质都是随着网络规模的扩大而突然出现的，也就是说对于给定概率p ，随着网络规模的扩大，要么几乎所有的随机图都具有某种性质，要么几乎每一个图都不具有该性质。
从数学观点看来，随机图理论处于图论和概率论的交叉地带。随机图理论的随机性体现在边的分布上，通过一定的概率模型连接节点对并形成随机网络。随机网络理论是复杂网络研究的理论基础，研究人员在复杂网络中发现了典型的随机特性。
1.2.4 复杂网络理论阶段
由于真实网络结构并非完全随机，单纯利用随机性并不能全面刻画复杂网络的结构关系。20 世纪末，随着计算机技术的不断发展、人们获取数据的能力不断增强以及计算机的计算能力不断提高，学术界对复杂网络科学的研究也随之发生了重要转变。研究者开始关注现实世界的大规模复杂系统，研究的重点从20 世纪分析小规模网络转移到了研究由几千、几万甚至是百万节点组成的大规模网络，不仅研究这些网络的统计结构特征，还关注网络表示的复杂系统动力学特征。
复杂网络研究新纪元开始的标志为：康奈尔大学Watts 和 Strogatz 在Nature 杂志上发表的题为Collective dynamics of Small world networks 的文章；美国东北大学的Barábasi 和Albert 在Science 杂志上发表的题为Emergence of scaling in randomnetworks 的文章。这两篇文章分别揭示了复杂网络的小世界特性和无标度性质，并建立了相应的模型以阐述这些特性的产生机理，成为复杂网络理论具有开创性和里程碑式的标志性工作。
传统的网络模型建立在随机图理论基础上，认为网络节点两两之间的连边是以一定概率且相互独立存在的。因此，对于网络节点数充分大的网络，每个节点所关联的边数目(节点度)近似于泊松分布(Possion distribution)。上述两项标志性研究工作表明，实际网络并不是随机的，而且不同的实际网络间存在一系列共同的结构统计特性和控制规律。其中，*先引起关注的三个网络结构特征分别是小世界性(smallworld)、集聚性(clustering)和网络节点度的幂律分布(power law distribution)特性。
网络的小世界性和集聚性，以及节点度的幂律分布特征，深刻地揭示了从社会网络、信息网络到生物网络等各种实际复杂网络的拓扑结构特征，极大地激发了各个领域研究者的兴趣，推动了复杂网络理论研究在近20 年内快速发展。目前，复杂网络研究领域主要包含三个层面的研究内容：①通过实证研究发现现实世界中各种系统的复杂网络结构特征，如小世界、度分布、集聚性以及匹配性等；②建立复杂网络模型理解实证研究发现的各种网络结构特征的生成机理，如WS 小世界网络模型、BA 无标度网络模型等；③探讨发生在复杂网络上的各种动力学行为，如疾病扩散、交通拥塞、博弈、同步等。这三个层面的基本内容将在本书第2 章进行详细讲解。
1.3 网络的矩阵表示与分类
1.3.1 网络的邻接矩阵表示方式
一个网络是由一些节点(nodes、points、vertexes)以及节点之间的连线(connections、links、lines、edges)所组成的。在数学意义上，网络可以用图论的语言来进行描述。
一个图是由节点和边共同组成的，记为G(V， L)，其中，V = {v1，v2 ， ，vN }是节点的集合，V≠Φ，L = {l1，l2 ， ，lK }是边的集合，li必须与V 中的节点相关联，即li的两个端点都在集合V 中。N 是网络中节点的总数， K 是网络中边的总数。当一个网络中的任何两节点之间都有一条边时，这个网络是一个完全图(complete graph)，K达到其**值。网络中一个特定的节点表示为vi，一条连接节点vi和vj 的边表示为lij。当vi和vj 之间有一条边时，它们被称为相邻点或邻居。在一个图中，由两两相邻的节点及其相关联的边构成的点边序列称为链。若链中的节点均不相同，则称为初等链。当一个图的任意两点之间至少有一条初等链时，这个图是一个连通图(connected graph)。
在图论描述的基础上，网络可以用邻接矩阵的方法表示。对于图G(V， L)，对应邻接矩阵表达Aij 是一个N × N 的方阵。如果网络中的点vi和vj 之间有一条边lij，则矩阵元素aij =1，否则aij = 0。图1-3 给出一个6× 6维的邻接矩阵及其对应的网络图。
图1-3 一个6× 6维的邻接矩阵及其对应网络图
1.3.2 网络分类
1．无权网络和加权网络
根据网络中的边所描述的节点之间的交互作用的含义，边可以是有权重的或是无权重的，对应的网络也就成为加权网络或者无权网络。如果在一个网络中，所有节点之间的交互作用都是一样的或者相似的，或者说节点之间边仅表示交互作用是否存在，则网络是无权网络，对应的邻接矩阵的所有元素aij为1 或者0，如图1-3所示。否则，如果网络中存在不同类型的交互作用，如某些交互作用更加重要或者更加频繁，那么网络中的边是有权重的。
为了描述加权网络，需要在无权图G(V，L)的定义基础上引入关于边的权重信息，即加权图G(V， L，W)，其中，W = {w1，w2 ， ，wK }表示权重的集合，对应着L集合中的每一条边。大多数情况下，权重是一个正数，其值越大表示交互作用越重要或越频繁或越强烈，但在有的情况下也会出现负数，如描述一种互相排斥的作用[2]。权重代表的含义也可根据网络的性质不同而不同。例如，图1-4 给出一个6× 6维的加权邻接矩阵及其对应的加权网络图，图中边的不同类型表示边的不同权值。
图1-4 一个6× 6维的加权邻接矩阵及其对应网络图
2．无向网络和有向网络
如果一条边lij表示节点i对节点j有作用，而节点j对节点i没有作用，例如，节点i认为节点j是自己的朋友，而节点j不认为节点i是自己的朋友，边lij就是有方向的。相应地，邻接矩阵将不再是对称的，对应网络是一个有向网络。图1-5 给出一个6×6维的有向邻接矩阵及其对应的有向网络图，图中的边具有方向，用箭头表示。
图1-5 一个6× 6
1.1 引言
从20 世纪七八十年代开始，复杂性问题的研究已引起国内外不同学科的科学家的关注。物理学家、生物学家、计算机科学家和经济学家等都开始不约而同地讨论和研究各自领域的复杂性问题，如自组织现象和自组织临界性、自适应问题、计算机与智能问题、生命与生物的演化、全球经济的演化、人类文化和语言的演变等。
随着人类认识能力的提高，人们发现自然界、人类社会、生物群体中的许多复杂系统都可以通过网络的概念加以描述。尤其是20 世纪九十年代以来，随着计算机技术和Internet 技术的迅猛发展，人类迈入了网络时代。人类已经生活在一个充满各种各样复杂网络的世界：从互联网(Internet)到万维网(WWW)，从大型电力网络到全球交通网络，从生物体的神经网络到各种新陈代谢网络，从科研合作网络到各种经济、政治、社会关系网络等。在上述背景下，网络科学成为多学科交叉的研究领域，它关注复杂网络的共性和处理它们的有效方法，从而增进人类对各种自然和人工复杂网络的理解。
尤其在近20 年间，复杂网络的研究飞速发展，其原因主要有以下几个方面：**，随着计算机技术的不断发展，人们数据获取能力的不断增强，建立了很多关于各种实际网络拓扑结构的大型数据库；第二，计算机计算能力的不断提高，使得人们可以处理的网络规模由以前的几十、几百个节点上升到了百万甚至是千万级的节点规模；第三，学科之间相互渗透，交叉学科的研究不断发展，使得人们可以获取不同领域的数据，从而发现不同数据类型隐藏下的一般控制规律。随着网络研究的不断深入，人们发现不同类型的网络中的网络结构特征和行为机制常常是一致的，在一个网络上得到的规律可以很容易地映射到另一个网络的研究中。这种不同网络具有一致或相似的结构性质或行为特征的现象，推动着网络研究以一个前所未有的速度向前发展，这类研究的对象常常被称作复杂网络(complex networks)。
1.2 网络理论的发展简史
1.2.1 网络理论的起源
网络理论研究起源于十八世纪欧拉对于哥尼斯堡“七桥问题”的研究，这是一个历史上著名的数学问题。普鲁士的哥尼斯堡(现在是俄罗斯的加里宁格勒)坐落在普瑞格尔河的两侧，包括两个大岛——克内夫和洛姆斯，它们通过7 座桥互相连接在一起，且与城市的两个大陆部分相连，如图1-1 所示。
图1-1 1736 年的哥尼斯堡镇[1]
当时，在哥尼斯堡镇流传着这样一个有趣的问题：一个人能否一次走完七座桥，且每座桥只走一次，*后返回原地？1736 年，著名数学家欧拉通过仔细观察哥尼斯堡镇七座桥的布局结构，向圣彼得堡学院提交了《哥尼斯堡七桥》的论文，并*终利用数学抽象法将这个问题抽象为一个由四个点、七条线构成的图，如图1-2 所示。由此，欧拉便将该问题转化为一个严格的数学问题：从图中任意一点出发，是否存在经过每条边一次而后返回原点的回路？这便是著名的“七桥问题”，也称为“一笔画问题”。
图1-2 哥尼斯堡镇“七桥问题”网络抽象图
不难看出，要一笔画成该图，必然只能有一个起点和一个终点，且由于该图中所有点均有两条以上的线与之相连(即所有点均构成了回路)，所以起点与终点必然重合，而一笔经过每一点总会产生一条入线和一条出线，故每一点都只能有偶数条线与之相连。在图1-2 中，四个点均是奇数条线与之相连，所以不存在经过每条边一次而后返回原点的回路。欧拉对“七桥问题”的研究，不仅成功地解决了“七桥问题”，而且开创了两个新的研究领域，即图论和拓扑学。这是复杂网络理论研究的起源。
1.2.2 规则网络理论阶段
自18 世纪开始，经过200 多年的发展，图在很多研究领域得到了应用，成为重要的研究工具。在*初的一个世纪，许多科学家们一直将复杂系统中各个实体之间的关系用某种规则的网络结构来表示。在这些网络中，每个节点仅与相近的几个节点存在关联，与其他大部分网络节点并不存在联系，并且呈现出某种规则的状态，如*近邻耦合网络、规则格子、星形网络等。
1.2.3 随机网络理论阶段
在图论及复杂网络理论的发展历程中，随机图理论(random graph theory)是继“七桥问题”之后提出的一个重要的、具有开创性意义的理论，由两个著名数学家Erdós 和Rényi 在20 世纪60 年代建立。
1959 年，数学家Erdós 和Rényi 对图论有了第二个里程碑式的贡献。他们用相对简单的随机图来描述网络，简称ER-随机图理论。Erdós 被称为20 世纪的欧拉，于1984 年获得沃尔夫奖。他善于与人合作，打破了数学领域的学者们喜欢个人独立研究的传统，一生中与众多合作者联合开展学术研究，发表过千余篇论文，涉及许多领域，与许多伟大的物理学家和数学家，如爱因斯坦、哥德尔、奥本海姆等有都密切学术交往。
ER-随机图理论对图论的研究影响非常大。在随后的近半个世纪，ER-随机图理论一直是科学家研究真实网络*有力的武器。随机网络是指，在由N 个节点构成的图中，以概率p 随机连接任意两个不存在连接的节点，重复这一过程而形成的网络，即两个节点之间连边与否不再是确定的事，而是由概率p 决定。换个角度来理解，在由N 个节点构成的图中，*多可以存在条边，从中随机连接M 条边所构成的网络就叫随机网络。如果选择，则这两种构造随机网络模型的方法就可以联系起来。随机网络和规则网络之间**的区别在于随机网络中引入了随机的方法形成网络。Erdós 和Rényi 系统研究了随机网络性质与概率p 的关系。他们发现，随机网络的许多重要的性质都是随着网络规模的扩大而突然出现的，也就是说对于给定概率p ，随着网络规模的扩大，要么几乎所有的随机图都具有某种性质，要么几乎每一个图都不具有该性质。
从数学观点看来，随机图理论处于图论和概率论的交叉地带。随机图理论的随机性体现在边的分布上，通过一定的概率模型连接节点对并形成随机网络。随机网络理论是复杂网络研究的理论基础，研究人员在复杂网络中发现了典型的随机特性。
1.2.4 复杂网络理论阶段
由于真实网络结构并非完全随机，单纯利用随机性并不能全面刻画复杂网络的结构关系。20 世纪末，随着计算机技术的不断发展、人们获取数据的能力不断增强以及计算机的计算能力不断提高，学术界对复杂网络科学的研究也随之发生了重要转变。研究者开始关注现实世界的大规模复杂系统，研究的重点从20 世纪分析小规模网络转移到了研究由几千、几万甚至是百万节点组成的大规模网络，不仅研究这些网络的统计结构特征，还关注网络表示的复杂系统动力学特征。
复杂网络研究新纪元开始的标志为：康奈尔大学Watts 和 Strogatz 在Nature 杂志上发表的题为Collective dynamics of Small world networks 的文章；美国东北大学的Barábasi 和Albert 在Science 杂志上发表的题为Emergence of scaling in randomnetworks 的文章。这两篇文章分别揭示了复杂网络的小世界特性和无标度性质，并建立了相应的模型以阐述这些特性的产生机理，成为复杂网络理论具有开创性和里程碑式的标志性工作。
传统的网络模型建立在随机图理论基础上，认为网络节点两两之间的连边是以一定概率且相互独立存在的。因此，对于网络节点数充分大的网络，每个节点所关联的边数目(节点度)近似于泊松分布(Possion distribution)。上述两项标志性研究工作表明，实际网络并不是随机的，而且不同的实际网络间存在一系列共同的结构统计特性和控制规律。其中，*先引起关注的三个网络结构特征分别是小世界性(smallworld)、集聚性(clustering)和网络节点度的幂律分布(power law distribution)特性。
网络的小世界性和集聚性，以及节点度的幂律分布特征，深刻地揭示了从社会网络、信息网络到生物网络等各种实际复杂网络的拓扑结构特征，极大地激发了各个领域研究者的兴趣，推动了复杂网络理论研究在近20 年内快速发展。目前，复杂网络研究领域主要包含三个层面的研究内容：①通过实证研究发现现实世界中各种系统的复杂网络结构特征，如小世界、度分布、集聚性以及匹配性等；②建立复杂网络模型理解实证研究发现的各种网络结构特征的生成机理，如WS 小世界网络模型、BA 无标度网络模型等；③探讨发生在复杂网络上的各种动力学行为，如疾病扩散、交通拥塞、博弈、同步等。这三个层面的基本内容将在本书第2 章进行详细讲解。
1.3 网络的矩阵表示与分类
1.3.1 网络的邻接矩阵表示方式
一个网络是由一些节点(nodes、points、vertexes)以及节点之间的连线(connections、links、lines、edges)所组成的。在数学意义上，网络可以用图论的语言来进行描述。
一个图是由节点和边共同组成的，记为G(V， L)，其中，V = {v1，v2 ， ，vN }是节点的集合，V≠Φ，L = {l1，l2 ， ，lK }是边的集合，li必须与V 中的节点相关联，即li的两个端点都在集合V 中。N 是网络中节点的总数， K 是网络中边的总数。当一个网络中的任何两节点之间都有一条边时，这个网络是一个完全图(complete graph)，K达到其**值。网络中一个特定的节点表示为vi，一条连接节点vi和vj 的边表示为lij。当vi和vj 之间有一条边时，它们被称为相邻点或邻居。在一个图中，由两两相邻的节点及其相关联的边构成的点边序列称为链。若链中的节点均不相同，则称为初等链。当一个图的任意两点之间至少有一条初等链时，这个图是一个连通图(connected graph)。
在图论描述的基础上，网络可以用邻接矩阵的方法表示。对于图G(V， L)，对应邻接矩阵表达Aij 是一个N × N 的方阵。如果网络中的点vi和vj 之间有一条边lij，则矩阵元素aij =1，否则aij = 0。图1-3 给出一个6× 6维的邻接矩阵及其对应的网络图。
图1-3 一个6× 6维的邻接矩阵及其对应网络图
1.3.2 网络分类
1．无权网络和加权网络
根据网络中的边所描述的节点之间的交互作用的含义，边可以是有权重的或是无权重的，对应的网络也就成为加权网络或者无权网络。如果在一个网络中，所有节点之间的交互作用都是一样的或者相似的，或者说节点之间边仅表示交互作用是否存在，则网络是无权网络，对应的邻接矩阵的所有元素aij为1 或者0，如图1-3所示。否则，如果网络中存在不同类型的交互作用，如某些交互作用更加重要或者更加频繁，那么网络中的边是有权重的。
为了描述加权网络，需要在无权图G(V，L)的定义基础上引入关于边的权重信息，即加权图G(V， L，W)，其中，W = {w1，w2 ， ，wK }表示权重的集合，对应着L集合中的每一条边。大多数情况下，权重是一个正数，其值越大表示交互作用越重要或越频繁或越强烈，但在有的情况下也会出现负数，如描述一种互相排斥的作用[2]。权重代表的含义也可根据网络的性质不同而不同。例如，图1-4 给出一个6× 6维的加权邻接矩阵及其对应的加权网络图，图中边的不同类型表示边的不同权值。
图1-4 一个6× 6维的加权邻接矩阵及其对应网络图
2．无向网络和有向网络
如果一条边lij表示节点i对节点j有作用，而节点j对节点i没有作用，例如，节点i认为节点j是自己的朋友，而节点j不认为节点i是自己的朋友，边lij就是有方向的。相应地，邻接矩阵将不再是对称的，对应网络是一个有向网络。图1-5 给出一个6×6维的有向邻接矩阵及其对应的有向网络图，图中的边具有方向，用箭头表示。
图1-5 一个6× 6
评论
还没有评论。