本书试图将网络、信息科学、信号处理和统计物理学的研究团体结合在一起，从工程学角度重点关注通信、网络以及信号处理等方面，为理解复杂网络提供了一种新颖的研究方式。
相对于其他复杂网络著作，本书另辟蹊径，从网络和信号处理的视角对复杂网络技术进行讨论
复杂网络是一种具有复杂和不规则连接模式的网络。与在节点和边的组织上具有清晰模式的正则网络不同，理解和刻画复杂网络是一件非常困难的工作。由于复杂网络在我们的生活中随处可见，例如生物网络、分子网络、社交网络、交通网络、电网、通信网络以及因特网等都属于复杂网络的范畴，因此研究复杂网络具有十分重要的意义。事实上，大多数物理和生物系统都呈现为一种复杂网络，它们由子系统及子系统之间的连接所构成。因此复杂网络建模涉及大量的自然网络和人造网络，对复杂网络的研究有助于大多数物理系统的研究。此外，互联网、社交网络、生物网络和计算机网络以巨型网络的形式促进了大数据的发展。本书试图将网络、信息科学、信号处理和统计物理学的研究团体结合在一起。
本书从工程学角度重点关注通信、网络以及信号处理等方面，为理解复杂网络提供了一种新颖的研究方式。本书的内容主要面向高年级本科生以及研究生教学，同时可以作为相关领域研究人员和从业人员的参考书目。为了满足课堂教学的需求，我们提供了大量的例子和章末习题。对于相关研究人员，书中每一章都包含了很多如开放性研究问题这类讨论主题。
这本书主要是为高年级本科生和研究生设计的课堂教材。为了更适合教学，本书包含100多个例子、200多张图以及20多个对照表。从第3章开始，每一章都有一节列出相应的开放性研究问题并提供一组练习题。此外，本书的附录部分包括以下附加信息：相关基本概念和定义；顶级研究会议列表；研究期刊列表；常用复杂网络分析软件工具列表；可供复杂网络研究的数据集；来自世界各地的复杂网络知名研究团队。
我们所提供的主要教辅资料包括：为教师提供的习题解答；每章附有LaTeX源码的演示幻灯片；部分图、仿真和例子的代码段；除了出版社所提供的在线信息外，我们还提供了一个网站（https://complexnetworksbook.github.io）用于分享有关复杂网络的最新信息。
我们要感谢我们的同行、同事和学生，他们在本书撰写过程中的反馈极大地帮助了我们。感谢印度班加罗尔印度科学研究所的K. R. Ramakrishnan教授在澄清图信号处理某些特征方面的帮助；真诚感谢美国艾奥瓦州立大学的Aleksandar Dogand~i教授在图信号处理方面所进行的讨论；感谢我们在印度空间科学与技术研究所（IIST）的同事Deepak Mishra教授、Gorthi Sai Subramanyam教授以及Vineeth Bala Sukumaran教授在图信号处理和复杂网络方面的帮助；感谢我们的合作者C. Siva Ram Murthy教授、Ramesh Rao教授、Bheemarjuna Reddy Tamma教授和Venkata Ramana Badarla教授；感谢Theodore S. Rappaport教授采用我们的书作为其备受推崇的Prentice Hall通信工程和新技术系列讲座的部分内容；感谢Chetan Kumar Verma先生、Aditi Verma女士、Sarath Babu先生、Nivedita Gaur女士、Gaurav Jain先生和Priti Singh女士。培生公司的组稿编辑Kim Boedigheimer女士在这项工作中为我们提供了所有必要的支持。我们在IIST系统与网络实验室的辅导员Divya R. S.女士在编写本书期间提供了很多后勤帮助。我们感谢IIST图书馆及其图书管理员Abdunnasar先生和IIST图书馆复印科的工作人员在本书编写过程中给予我们的复印支持。
同时要感谢我们的家人在本书的撰写过程中所给予的默默支持。
感谢位于特里凡得琅的印度空间科学与技术研究所及其主任Vinay Kumar Dadhwal博士允许我们出版这本书。
我们也感谢培生公司及相关机构的审稿人和编辑在审阅、编辑和出版本书过程中给予的帮助。我们特别感谢Angela Urquhart、Julie Nahil和Andrea Archer协助我们按时完成了这本书。
这本书综述或引用了200多部科学著作。然而，在复杂网络领域，讨论所有相关的贡献并不现实，我们根据本书的重点和结构做出了选择。无论如何，我们的主题选择并不意味着书中未包含的作品价值不够高，我们事先向所有认为自己的作品被忽视的研究人员和学生道歉。
在书中我们已经非常谨慎地避免印刷错误、图片错误和其他不一致的地方。然而，书中难免还有一些错误未被发现，请读者通过电子邮件或其他联系方式告知可能的任何错误。作者简介中提供了我们当前的电子邮件地址，读者可以通过该地址与我们联系，提出咨询、评论、建议或报告错误。
B. S. Manoj
Abhishek Chakraborty
Rahul Singh
计算机\网络
复杂网络是一种具有复杂和不规则连接模式的网络。这种网络在我们的生活中随处可见，例如生物网络、分子网络、社交网络、交通网络、电网、通信网络以及因特网等都属于复杂网络的范畴，因此研究复杂网络具有十分重要的意义。
本书试图将网络、信息科学、信号处理和统计物理学的研究结合在一起，从工程学角度重点关注通信、网络以及信号处理等方面，为理解复杂网络提供一种新颖的研究方式。
通过本书，你将习得
什么因素使网络复杂化，以及如何成功地描述它们。
图论基础、定义和概念。
小世界网络、无标度网络、小世界无线网格和小世界无线传感器网络的相关内容。
复杂网络的谱和图信号处理的概念和技术。
通过变换和小波进行多尺度分析。
[印度] B.S. 马努基（B.S.Manoj） 阿布舍克·查克拉博蒂（Abhishek Chakraborty） 拉胡尔·格（Rahul Singh） 著：B.S.马努基（B.S. Manoj）目前是印度空间科学与技术研究所航空电子部负责人、教授。Manoj的研究领域包括复杂网络、网络安全、认知网络、ad hoc无线网络、无线mesh网络、软件定义网络、延迟容忍网络和无线传感器网络。2015年，Manoj获得IEEE自然计算国际会议(ICNC)杰出领导奖，他与人合著的多篇论文获得了许多奖励。
复杂网络是一门涉及数学、物理学、非线性科学、信息科学和生物科学等众多学科的交叉学科，本质上刻画了系统内各元素之间复杂和不规则的交互关系。该理论一经诞生，便被作为探索各类系统复杂性的一种新途径，在自然科学与社会科学等领域掀起了研究热潮。
关于复杂网络的研究历史，尽管之前有一些相关领域的工作，但学术界一般认为，美国康奈尔大学博士生Watts及其导师Strogatz教授于1998年6月在《Nature》杂志上发表的“小世界网络的集体动力学”，以及美国圣母大学物理系的Barabasi教授等人于1999年10月在《Science》杂志上发表的“随机网络中标度的涌现”这两篇论文标志着复杂网络系统性研究工作的开启。经过20年左右的研究，复杂网络的理论模型和分析方法都取得了长足进展，形成了大量的研究成果，并有力指导了其他学科的发展。
相对于现有的各类复杂网络著作，本书作者另辟蹊径，从网络和信号处理的视角对复杂网络技术进行分析。本书具有如下一些特点：
从全新的视角讨论了复杂网络技术，将网络、信息科学、信号处理和统计物理学等领域的研究结合在一起，从通信、网络以及信号处理等方面对复杂网络技术进行分析，为理解复杂网络提供了一种新颖的方式。尤其是本书中复杂网络的图信号处理技术，是近年来发展起来的一种分析复杂网络的全新手段，对于读者深入了解这一领域具有非常大的帮助。
采用循序渐进的方法组织内容，对复杂网络的形成与演进过程进行了系统的讨论，能够帮助读者快速理解复杂网络的形成、发展和典型场景等，使读者不仅知其然，更知其所以然。
分析了多种物理世界复杂网络的例子。作者在本书中对复杂网络的讨论并不局限于概念模型，而是将该技术与无线网状网、无线传感器网络等结合在一起，更加直观地给出了复杂网络在物理世界中的形成背景及其作用价值等。
本书作者Manoj教授的研究领域涵盖了复杂网络理论以及各种互联网络技术，在相关领域成果颇丰，相信他这本从全新视角出发的复杂网络著作能够为读者带来不一样的体验和收获。
感谢陆军工程大学指挥控制工程学院有关领导和同事对本书翻译给予的支持，感谢机械工业出版社为我国读者引进这本优秀的著作，感谢编辑的辛勤和出色工作，也感谢译者的家人对译者的支持。本书的第1~7章由陆军工程大学邢长友副教授翻译，第8～11章以及附录部分由陆军工程大学淦文燕副教授翻译，南京航空航天大学陈鸣教授审阅了全稿并提出了很多建设性的意见。
专业著作的翻译是一项对译者要求很高的工作，在翻译过程中，译者力求以信达雅的方式将原著意思表达出来，但限于时间与水平，本书翻译可能存在不妥、不到甚至错漏之处，请识者指正。
邢长友
2019年7月于南京
复杂网络是一个与人类社会、自然界密切相关的研究领域。从概念上讲，任何包含大量组成单元（或子系统）的复杂系统（如互联网、朋友圈、生态系统、食物链、蛋白质等），若将组成单元抽象为节点，单元之间的相关关系抽象为边，都可以作为复杂网络来研究。复杂网络关注的是系统中个体相互关联作用的拓扑结构，研究复杂网络的规律是利用网络来描述物理、生物和社会现象的预测模型的科学。
目前已有不少复杂网络或网络科学的著作或教材面市，这些书籍大多是以概念介绍和现象叙述为主。而这本由培生集团推出的复杂网络著作，用一种新颖的方式研究了复杂网络。本书作者Manoj教授等人是在互联网领域研究成果丰硕、技术视野开阔的专家，他们从工程学角度重点关注通信、网络以及信号处理等方面，利用图论和矩阵论等数学工具定量分析复杂网络的特征，对于深入分析复杂系统和复杂网络内在规律提出了新方法，本书值得相关学科的学生、教师和研究人员学习和参考。
本书的译者邢长友、淦文燕两位博士是陆军工程大学副教授，长期从事计算机网络、无人系统、分布式系统等领域的研究，对复杂网络有深入理解和研究。为了向读者奉献一本高质量的专业技术译著，他们在忠实原文、准确达意和便于中国读者理解等方面花费了大量精力，相信本书中译本的出版能够推动我国复杂网络的研究水平更上一层楼。
陈 鸣
2019.8.28于南京
出版者的话
推荐序
译者序
前言
致谢
作者简介
第1章 概述1
1.1 复杂网络1
1.2 复杂网络类型2
1.3 研究复杂网络的好处4
1.3.1 建模和刻画复杂物理世界系统4
1.3.2 设计新的高效物理世界系统5
1.3.3 制定复杂真实世界问题的解决方案5
1.3.4 通过分子网络建模提高生物医学研究水平5
1.3.5 发展网络医学5
1.3.6 摧毁反社会网络6
1.3.7 通过社交网络强化社会科学研究6
1.4 复杂网络研究面临的挑战6
1.5 本书内容概述6
1.6 本书内容组织7
1.6.1 对本书内容的阅读建议8
1.7 面向教师的辅助材料9
1.8 小结9
第2章 图论预备知识10
2.1 引言10
2.2 图11
2.2.1 子图12
2.2.2 补图13
2.3 与图相关的矩阵13
2.3.1 权重矩阵14
2.3.2 邻接矩阵14
2.3.3 关联矩阵15
2.3.4 度矩阵15
2.3.5 拉普拉斯矩阵15
2.4 基本图测度17
2.4.1 平均邻居度17
2.4.2 平均聚类系数17
2.4.3 平均路径长度18
2.4.4 平均边长度19
2.4.5 图的直径与体积20
2.5 图的基本定义与属性20
2.5.1 途径、路径以及回路20
2.5.2 连通性21
2.5.3 无环性22
2.5.4 同构24
2.5.5 平面性24
2.5.6 可着色性25
2.5.7 可遍历性26
2.5.8 网络流27
2.5.9 乘积图28
2.6 图的类型30
2.6.1 正则图30
2.6.2 二分图30
2.6.3 完全图31
2.6.4 树31
2.6.5 线图33
2.6.6 冲突图34
2.7 图的其他重要测度34
2.7.1 Cheeger常数35
2.7.2 团数35
2.8 图寻路算法35
2.8.1 Dijkstra最短路径算法36
2.8.2 所有节点对之间的最短路径算法37
2.9 小结38
练习题38
第3章 复杂网络概述42
3.1 复杂网络的主要类型42
3.1.1 随机网络42
3.1.2 小世界网络43
3.1.3 无标度网络43
3.2 复杂网络测度43
3.2.1 平均邻居度43
3.2.2 平均路径长度44
3.2.3 网络直径44
3.2.4 平均聚类系数44
3.2.5 度分布44
3.2.6 中心性测度44
3.2.7 复杂网络中的度-度相关性48
3.2.8 节点临界性49
3.2.9 网络电阻距离49
3.3 复杂网络中的社区发现50
3.3.1 模块度最大化50
3.3.2 Surprise最大化51
3.3.3 基于冲突图变换的社区发现51
3.4 复杂网络中的熵60
3.4.1 网络熵60
3.4.2 节点度熵60
3.4.3 链路长度变化熵60
3.4.4 链路影响熵60
3.5 随机网络68
3.5.1 随机网络的演进68
3.5.2 Erd鰏-Rényi随机网络模型69
3.5.3 随机网络的属性69
3.6 开放性研究问题71
3.7 小结72
练习题72
第4章 小世界网络75
4.1 引言75
4.2 Milgram小世界实验76
4.3 小世界网络的特征77
4.4 现实世界的小世界网络80
4.5 小世界网络的生成与演进83
4.5.1 重连现有链路83
4.5.2 纯随机添加新的LL83
4.5.3 基于欧氏距离添加新的链路86
4.6 基于容量的确定性新链路添加86
4.6.1 最大流最小割定理87
4.6.2 基于最大流容量策略的链路添加89
4.7 建立确定性的小世界网络90
4.7.1 基于最小APL的链路添加90
4.7.2 基于最小AEL的链路添加93
4.7.3 基于最大BC的链路添加93
4.7.4 基于最大CC的链路添加93
4.8 线性拓扑小世界网络的锚点93
4.8.1 锚点的重要性94
4.8.2 锚点的位置94
4.9 基于启发式方法的确定性链路添加97
4.9.1 最大接近中心性差异97
4.9.2 顺序确定性LL添加102
4.9.3 基于小世界特征的平均流容量增强106
4.10 小世界网络中的路由111
4.10.1 分布式路由算法112
4.10.2 自适应分布式路由算法112
4.10.3 前瞻式路由算法115
4.11 小世界网络的容量116
4.11.1 以重连现有NL方式生成的小世界网络的容量117
4.11.2 以LL添加方式生成的小世界网络的容量117
4.12 开放性研究问题118
4.13 小结118
练习题119
第5章 无标度网络122
5.1 引言122
5.1.1 无标度的含义是什么123
5.2 无标度网络的特征123
5.3 现实世界的无标度网络126
5.3.1 作者引用网络126
5.3.2 因特网中的自治系统126
5.3.3 空中交通网络127
5.3.4 识别无标度网络127
5.4 无标度网络的形成133
5.4.1 通过偏好连接创建无标度网络134
5.4.2 通过适应度建模创建无标度网络134
5.4.3 通过可变内在适应度创建无标度网络134
5.4.4 通过优化创建无标度网络134
5.4.5 通过指数1创建无标度网络134
5.4.6 通过贪心全局决策创建无标度网络135
5.5 基于偏好连接的无标度网络创建135
5.5.1 Barabási-Albert网络模型135
5.5.2 观察和讨论136
5.6 基于适应度建模的无标度网络创建136
5.6.1 基于适应度的网络模型137
5.6.2 观察和讨论137
5.7 基于可变内在适应度的无标度网络创建138
5.7.1 基于可变内在适应度的网络模型138
5.7.2 观察和讨论138
5.8 基于优化的无标度网络创建139
5.8.1 观察和讨论139
5.9 基于指数1的无标度网络创建140
5.9.1 通过重连创建无标度网络140
5.9.2 观察和讨论142
5.10 基于贪心全局决策的无标度网络创建142
5.10.1 贪心全局LL添加142
5.10.2 基于贪心全局决策的无标度网络中的一些观察144
5.11 确定性的无标度网络创建145
5.11.1 确定性无标度网络模型145
5.11.2 对确定性无标度网络创建的一些观察146
5.12 开放性研究问题147
5.13 小结148
练习题148
第6章 小世界无线mesh网络150
6.1 引言150
6.1.1 小世界特征152
6.1.2 小世界无线mesh网络152
6.2 小世界无线mesh网络的分类152
6.3 随机LL的创建153
6.3.1 通过重连普通链路创建随机LL153
6.3.2 通过添加新的链路创建随机LL154
6.4 基于纯随机链路添加的小世界155
6.5 基于欧氏距离的小世界155
6.6 基于天线度量的小世界网络的实现156
6.6.1 基于传输功率的LL添加156
6.6.2 基于随机波束形成的LL添加156
6.6.3 基于传输功率和波束形成的LL添加157
6.7 创建小世界无线mesh网络的算法机制158
6.7.1 基于接触的LL添加158
6.7.2 基于遗传算法的LL添加158
6.7.3 基于小世界协同路由的LL添加159
6.8 以网关路由器为中心的小世界网络形成159
6.8.1 基于单网关路由器的LL添加160
6.8.2 基于多网关路由器的LL添加164
6.9 创建确定性的小世界无线mesh网络167
6.9.1 基于穷举搜索的确定性LL添加167
6.9.2 基于启发式方法的确定性LL添加168
6.10 创建非持久小世界无线mesh网络168
6.10.1 基于数据骡子的LL创建168
6.10.2 负载感知的LL创建169
6.11 小世界无线mesh网络中的非持久路由171
6.11.1 负载感知的非持久小世界路由172
6.11.2 LNPR算法的性能评估173
6.12 现有解决方案的定性比较175
6.13 开放性研究问题177
6.14 小结178
练习题178
第7章 小世界无线传感器网络180
7.1 引言180
7.2 小世界无线mesh网络和小世界无线传感器网络181
7.3 为何选择小世界无线传感器网络182
7.4 将WSN转换为SWWSN面临的挑战185
7.5 SWWSN的远程链路类型186
7.6 将WSN转换为SWWSN的方法187
7.6.1 现有方法的分类187
7.6.2 性能评估测度188
7.6.3 将正则拓扑WSN转换为SWWSN189
7.6.4 随机模型异构SWWSN192
7.6.5 基于Newman-Watts模型的SWWSN193
7.6.6 基于Kleinberg模型的SWWSN193
7.6.7 基于有向随机模型的SWWSN194
7.6.8 基于可变速率自适应调制的SWWSN196
7.6.9 基于度的LL添加创建SWWSN198
7.6.10 基于禁止距离的LL添加创建SWWSN199
7.6.11 同构SWWSN200
7.7 基于有线LL的SWWSN201
7.8 开放性研究问题202
7.9 小结204
练习题204
第8章 复杂网络的谱207
8.1 引言207
8.2 图的谱208
8.3 图的邻接矩阵谱209
8.3.1 特征值的边界209
8.3.2 特殊图的邻接矩阵谱210
8.4 复杂网络的邻接矩阵谱212
8.4.1 随机网络213
8.4.2 随机正则网络213
8.4.3 小世界网络214
8.4.4 无标度网络214
8.5 图的拉普拉斯谱216
8.5.1 拉普拉斯算子特征值的界217
8.5.2 归一化拉普拉斯算子特征值的界217
8.5.3 矩阵树定理218
8.5.4 拉普拉斯谱和图的连通性218
8.5.5 谱图聚类220
8.5.6 特殊图的拉普拉斯谱220
8.6 复杂网络的拉普拉斯谱222
8.6.1 随机网络222
8.6.2 随机正则网络223
8.6.3 小世界网络223
8.6.4 无标度网络224
8.7 使用谱密度进行网络分类225
8.8 开放性研究问题225
8.9 小结226
练习题226
第9章 复杂网络上的信号处理229
9.1 图信号处理简介229
9.1.1 图信号的数学表示231
9.2 经典信号处理和图信号处理的比较231
9.2.1 图傅里叶变换与经典离散傅里叶变换的关系232
9.3 图拉普拉斯算子233
9.3.1 图拉普拉斯算子的性质233
9.3.2 图谱234
9.4 量化图信号的变化234
9.5 图傅里叶变换235
9.5.1 频率和频率排序的概念237
9.5.2 带宽受限的图信号240
9.5.3 顶点索引的影响240
9.6 图信号的广义算子242
9.6.1 滤波242
9.6.2 卷积244
9.6.3 平移245
9.6.4 调制246
9.7 应用246
9.7.1 节点中心性的谱分析246
9.7.2 图傅里叶变换中心性252
9.7.3 传感器网络中的故障检测255
9.8 窗口图傅里叶变换255
9.8.1 窗口图傅里叶变换的示例257
9.9 开放性研究问题258
9.10 小结259
练习题259
第10章 图信号处理方法263
10.1 引言263
10.2 基于拉普拉斯矩阵的图信号处理263
10.3 DSPG框架264
10.3.1 线性图滤波器和移位不变性264
10.4 基于权重矩阵的DSPG框架265
10.4.1 移位算子265
10.4.2 线性移位不变图滤波器266
10.4.3 总方差267
10.4.4 图傅里叶变换268
10.4.5 线性移位不变图滤波器的频率响应270
10.5 基于有向拉普拉斯算子的DSPG框架271
10.5.1 有向拉普拉斯算子271
10.5.2 移位算子272
10.5.3 线性移位不变图滤波器272
10.5.4 总方差273
10.5.5 基于有向拉普拉斯算子的图傅里叶变换274
10.5.6 线性移位不变图滤波器的频率响应278
10.6 图信号处理方法的比较278
10.7 开放性研究问题279
10.8 小结279
练习题280
第11章 复杂网络的多尺度分析285
11.1 引言285
11.2 复杂网络数据的多尺度变换286
11.2.1 顶点域设计286
11.2.2 谱域设计286
11.3 Crovella-Kolaczyk小波变换287
11.3.1 CK小波287
11.3.2 小波变换287
11.3.3 小波的性质288
11.3.4 示例288
11.3.5 优点和缺点289
11.4 随机变换289
11.4.1 优点和缺点290
11.5 基于提升的小波290
11.5.1 将图拆分为偶数节点和奇数节点290
11.5.2 基于提升的变换291
11.6 双通道图小波滤波器组291
11.6.1 图中的下采样和上采样292
11.6.2 双通道图小波滤波器组294
11.6.3 图正交镜像滤波器组295
11.6.4 任意图的多维可分小波滤波器组296
11.7 谱图小波变换296
11.7.1 SGWT的矩阵形式297
11.7.2 小波生成核297
11.7.3 SGWT的示例299
11.7.4 优点和缺点300
11.8 基于有向拉普拉斯算子的谱图小波变换300
11.8.1 小波300
11.8.2 小波生成核301
11.8.3 示例302
11.9 扩散小波303
11.9.1 优点和缺点303
11.10 开放性研究问题303
11.11 小结304
练习题304
附录A 向量和矩阵307
附录B 经典信号处理314
附录C 锚点位置分析319
附录D 函数的渐近行为322
附录E 相关学术课程及项目324
附录F 相关期刊和会议327
附录G 相关数据集和可视化工具330
附录H 相关研究组332
符号335
缩略语338
参考文献342
索引355
