网络科学作为一门不断发展的新兴交叉学科,以图论为基础,在不断吸收了其他专业的最新成果后终于以一门独立的学科出现。网络科学不仅可以作为新兴的网络工程、网络安全等理工科专业的理论基础,还可以作为网络经济、网络营销、社会科学研究的基本理论,而且是公共关系定量分析的重要工具之一。本书是一本很好地将理论和应用相结合的著作,首先系统地介绍了网络科学的发展历程,然后进一步阐述了大量网络分析与规划的实例,内容覆盖了社会关系网、生物网络、电力网络、病毒传播网、互联网等内容,试图为读者描述一种广义的网络模型。
本书适用于网络工程、网络通信、网络安全、网络营销、网络信息传媒、公共关系、应用数学等专业必修课,是研究人员、专业人员以及工程、计算、生物领域的技术人员不可缺少的参考资料,也可以作为相关领域研究的高年级和研究生教材。
网络科学
原理与应用
Network Science
Theory and Applications
(美)Ted G. Lewis 著 陈向阳 巨修练 等译
网络科学作为一门新兴的学科越来越引入瞩目。网络科学能帮助读者设计更快、更有弹性的通信网络;能用于调整电力网络、电信网络和飞行航线等基础设施系统;可以为市场动态建模;能帮助理解生物系统中的同步;能用于分析人与人之间的社会互动……
这是第一本全面审视新出现的网络科学的论著。书中研究了各种网络——规则网络、随机网络、小世界网络、影响网络、无标度网络和社会网络等,并将网络过程和行为应用于涌现、传染病、同步和风险方面。本书的独特之处在于将跨计算机科学、生物学、物理学、社会网络分析、经济学和市场营销等多学科的专业概念整合了起来。
本书为网络科学领域提供了全新的理解和阐释,是研究人员、专业人员以及工程、计算、生物领域的技术人员不可缺少的参考资料,也可以作为相关专业高年级本科生和研究生教材。
作者简介
Ted G. Lewis 博士是美国加州蒙特雷海军研究生院的计算机科学教授。他有丰富的工作阅历和广泛的学术研究,作为美国电气和电子工程师协会(IEEE)计算机协会的会员,他还担任《IEEE软件》和《计算机》杂志的总编,并已经编著出版了30余本著作。他曾任伊士曼柯达公司(Eastman Kodak Company)数字策略的副总裁。
在我写本书前言时,“网络科学”可能还不够成熟,目前就宣布将图论、控制论和交叉学科应用结合成一门“科学”还为时过早。的确,我的许多同事也表达了强烈的不同意见——他们认为网络科学是一种时尚,甚至是编造出来的东西。带着这种担心,从2006年起我开始写一系列有关无标度网络、小世界和自同步网络的论文。这一系列论文所表达出的粗糙理念逐渐演变成了目前捧在你手中的这本书。像大多数首次尝试一样,本书不可能没有缺陷。我写作本书是出自对科学的热衷——希望它能成为无偏见的、探索思想的有用资料。或许将来会建立一门几乎涉及每个学科、工程、医学和社会科学领域研究的新的网络科学。
只有时间才能证明这种将我们所知的新的网络科学编译成卷的初步尝试是否成功——而本书正是付诸实践之作!但是写作略微超前的主题并不是我的长处。风险在于选择了我称之为网络科学的主题。很显然,我们必须概括如Adamic、Albert、Barabasi、Barrat、Bollobas、Erdos、Granovetter、Kephart、Lin、Liu、Mihail、Milgram、Molloy、Moore、Newman、PastorSatorras、Renyi、Strogatz、Tadic、Wang、Watts、Weigt、White、Zhang和Zhu等先驱们的工作。本书共13章,我在前6章对上述这些作者的工作进行了概括。这些章节从图论基础领域,再到现代网络定义展开。最著名的话题——规则、随机、无标度和小世界网络都有整章的叙述。因此,本书前半部分是沿着发明者们绚丽的足迹追踪网络科学的发展。
我的第二个目的是在先驱们已知和已发表的内容基础之上添加新的内容。这里的风险在于我的自命不凡:大胆地假定已知这种新的领域会朝哪个方向发展。第7章介绍网络的新的自组织原则,并演示如何定制设计任意度序列分布的网络。第8章是将Z Wang、Chakrabarti、C Wang和Faloutsos的卓越工作尝试扩展到令人激动的为互联网设计的抗原对策中。这种工作可以用来解释人类传染病以及席卷整个互联网的传染病毒。第9章将Watts的早期工作提高到一个新的水平——强调网络同步仅仅是线性系统稳定性的特殊例子。简单的特征值工具可以用于决定几乎任意线性网络的稳定性和同步性。第10章几乎是全新材料,说明为了使社会网络达成共识需要满足什么条件。事实证明,群组达成共识并不容易!第11章是以Waleed AlMannai的博士论文为基础构建的,他形式化并扩展了我在网络风险方面的研究工作。Al Mannai的理论用来衡量关键基础系统并保护它们免受自然和人为(人造)的攻击,这对美国本土安全的实践已经有了深刻的影响。第12章是对商业模型的探索——将著名的Schumpeter创造性破坏过程与涌现过程关联起来,并将BassFisherPry方程映射到网络上。验证BassFisherPry方程可用于网络是值得欣慰的,但是更进一步,我还将演示如何将这些经典模型扩展应用到多产品市场和寡头垄断上。最后,第13章完全体现了网络科学中的最前沿内容。这一章向读者介绍激动人心的新领域——蛋白质表达网络,并就读者需要考虑的一些新的方向提供一些建议。
一般读者可以很容易地跳过有关数学内容,并仍能从将网络应用到各种学科(包括计算机科学与工程、商务、公共卫生(传染病)、互联网病毒防范、社会网络行为、生物学和物理学等)中搜集到很多信息。更加专业的读者和教师可能想要使用由出版商和作者提供的软件工具(tedglewis@frictionfreeeconomycom)。其中包括5个Java应用程序:Networkjar用来探索各类网络并用各种涌现过程实验;Influencejar用于研究影响网络和社会网络分析;NetworkAnalysisjar用来研究网络脆弱性和攻防双方的网络风险问题;NetGainjar用于商业建模;BioNetjar用于生物网络,特别是蛋白质表达网络。可执行代码和源代码都是以开源软件的形式提供的。如果你在大学课程中想要以指导教师的身份分发这些材料,可从出版商的Web站点下载教师手册。
本书只起到抛砖引玉的作用,还留下了许多未回答的问题。我希望本书能给新一代的研究人员及其研究工作带来灵感。如果我是正确的,那么术语“网络科学”在将来的十年就不会再存在争议。当然这留给读者作为练习!
我要感谢Steve Lieberman,他认真地对公式进行了排版并详细地审阅数遍草稿。还要感谢Rudy Darken和Tom Mackin,他们对我的思考过程带来影响,并帮助我纠正了几个错误构思。Waleed Al Mannai对第11章有很大的影响,并间接地对整本书产生了影响。非常高兴能与这些同事一起合作,历时3年完成了这本书的写作。
Ted GLewis
2008年3月22日
计算机\网络
网络科学作为一门新兴的学科越来越引入瞩目。网络科学能帮助读者设计更快、更有弹性的通信网络;能用于调整电力网络、电信网络和飞行航线等基础设施系统;可以为市场动态建模;能帮助理解生物系统中的同步;能用于分析人们之间的社会互动……
这是第一本全面审视新出现的网络科学的论著。书中研究了各种网络——规则网络、随机网络、小世界网络、影响网络、无标度网络和社会网络等,并将网络过程和行为应用于涌现、传染病、同步和风险方面。本书的独特之处在于将跨计算机科学、生物学、物理学、社会网络分析、经济学和市场营销等多学科的专业概念整合了起来。
本书为网络科学领域提供了全新的理解和阐释,是研究人员、专业人员以及工程、计算、生物领域的技术人员不可缺少的参考资料,也可以作为相关领域研究的高年级和研究生教材。
作者简介
Ted G. Lewis博士是美国加州蒙特雷海军研究生院的计算机科学教授。他有丰富的工作阅历和广泛的学术研究,作为美国电气和电子工程师协会(IEEE)计算机协会的会员,他还担任《IEEE软件》和《计算机》杂志的总编,并已经编著出版了30余本著作。他曾任伊士曼柯达公司(Eastman Kodak Company)数字策略的副总裁。
陈向阳 巨修练 等译:暂无简介
“我们被困在无法逃避的相互关系网络中,任何事情,如果直接地影响了一个人,就会间接地影响到所有人。”
——马丁·路德·金
目前,网络科学在不断汲取各学科最新成果的基础上继续深入发展、完善,其理论研究方法成为广泛的交叉科学的一种强有力的思想方法。2009年7月24日出版的《科学》杂志刊登专题——“复杂系统与网络”(Complex Systems and Networks),充分地表明网络科学进一步向众多学科渗透并向应用发展。从网络科学的角度来看,无论是自然界还是人类社会,网络都无处不在,从而深刻而广泛地影响着人们的日常生活和科学技术等各种活动。因此,利用网络科学,可以探讨自然界和人类社会的各种各样的复杂系统。网络科学正在与众多新兴科学相互交融和推动,它提供了新的科学发展观和方法论,使决定性与随机性、有序性与无序性、复杂性与简单性,达到了和谐统一,人类的认识产生了新的飞跃,成为人们认识客观世界的工具。在网络科学的思想、理论与方法的大框架下,无论从微观层次,还是宏观和宇宙观层次,人们都可以从全新的网络的角度、观点和方法来探讨世界万物的复杂性问题。
为了弥补和丰富国内有关网络科学方面的教材,同时也为了科研需要,我们组织翻译了美国蒙特雷海军研究生院的计算机科学教授特德·刘易斯(Ted Lewis)博士的《网络科学:原理与应用》这本书。本书由陈向阳、巨修练负责翻译,参加翻译的人员还包括徐清、陈晓明、徐茜、蹇贝、孙金余、费滕、李亚玲、孙克华、於照等。机械工业出版社刘立卿编辑、王春华编辑等在审稿过程中做了大量辛苦的工作,在此特别致以衷心的感谢!本书的翻译得到了绿色化工过程教育部重点实验室及武汉工程大学优秀学术著作出版资助项目的资助。
在翻译时,由于本书涉及的领域广泛,具体包括应用数学、计算机科学、生物学、物理、化学、医学、社会学、军事等专业,所以挑战在所难免。虽然我们参阅了大量复杂网络的相关译文资料——特别是中科院方锦清对本书的评价、武汉大学陆俊安等发布的网络科学博文,而且花了大量的时间尽力使这本译著完美,但由于自身水平和专业局限,译文中仍会有错误和不到之处。读者在使用本书时若遇到问题或者有好的建议,敬请联系我们(xychensun@yahoocomcn),以期共同做好网络科学的学习和研究。
译者
2011年3月
出版者的话
译者序
前言
第1章网络科学的起源
11什么是网络科学
12网络科学简史
121网前阶段 (1736—1966)
122中期网络阶段(1967—1998)
123现代阶段(1998—)
13总则
第2章图
21图的集合论定义
211节点、链路和映射函数
212节点度和hub
213路径和回路
214连通性和组件
215直径、半径和中心性
216介数和紧度
22图的矩阵代数定义
221连接矩阵
222邻接矩阵
223拉普拉斯矩阵
224路径矩阵
23哥尼斯堡七桥图
231欧拉路径和欧拉回路
232哥尼斯堡七桥问题的正式定义
233欧拉解
24图的谱属性
241谱半径
242谱隙
25图的类型
251杠铃形、线形和环形图
252结构化图与随机图
253k-规则图
254图密度
26拓扑结构
261度序列
262图的熵
263无标度拓扑
264小世界拓扑
27软件中的图实现
271Java节点和链路
272Java 网络
练习
第3章规则网络
31直径、中心性和平均路径长度
32二叉树网络
321二叉树网络的熵
322二叉树网络的路径长度
323二叉树网络的链路效率
33超环形网络
331超环形网络的平均路径长度
332超环形网络的链路效率
34超立方网络
341超立方网络的平均路径长度
342超立方网络的链路效率
练习
第4章随机网络
41随机网络的生成
411Gilbert随机网络
412ErdosRenyi随机网络
413锚定随机网络
42随机网络的度分布
43随机网络的熵
431随机网络熵的建模
432随机网络的平均路径长度
433随机网络的聚类系数
434随机网络的链路效率
44随机网络的属性
441随机网络的直径
442随机网络的半径
443利用Java计算紧度
444随机网络中的紧度
45随机网络中的弱联系
46规则网络的随机性
47分析
练习
第5章小世界网络
51生成一个小世界网络
511WattsStrogatz (WS)过程
512一般的WS过程
513小世界网络的度序列
52小世界网络属性
521熵与重联概率
522熵与密度
523小世界网络的路径长度
524小世界网络的聚类系数
525小世界中的紧度
53相变
531路径长度和相变
532材料中的相变
54小世界网络中的导航
55小世界网络中的弱联系
56分析
练习
第6章无标度网络
61生成一个无标度网络
611BarabasiAlbert(BA)网络
612生成BA网络
613无标度网络幂律分布
62无标度网络的属性
621BA网络熵
622hub度与密度对应关系
623BA网络平均路径长度
624BA网络紧度
625无标度网络聚类系数
63无标度网络中的导航
631最大度导航与密度对应关系
632最大度导航与hub度的对应关系
633在无标度Pointville网络中的弱联系
64分析
641熵
642路径长度和通信
643聚类系数
644hub度
练习
第7章涌现
71什么是网络涌现
711开环涌现
712反馈循环涌现
72科学中的涌现
721社会科学中的涌现
722物理科学中的涌现
723生物中的涌现
73遗传进化
731hub涌现
732聚类涌现
74设计者网络
741度序列涌现
742生成给定的度序列的网络
75排列网络涌现
751排列微规则
752排列和聚类系数
76涌现的一个应用
761随机排列的链路优化
762确定性排列的优化
763最小长度涌现模型
764二维布局
练习
第8章传染病
81传染病模型
811KermackMcKendrick模型
812传染病阈值
813易感-感染-消亡(SIR)模型
814结构化网络峰值感染密度
815易感-感染-易感(SIS)传染病
82网络中持续稳定的传染病
821随机网络传染病阈值
822一般网络中的传染病阈值
823一般网络中的固定点感染密度
83网络传染病仿真软件
84对策
841对策的算法
842接种策略对策
843Java抗原仿真
练习
第9章同步
91同步或不同步
911混沌映射
912网络稳定性
92蟋蟀社会网络
921蟋蟀社会网络的同步性质
922更加通用的模型:Atay网络
923Atay网络的稳定性
93基尔霍夫网络
931基尔霍夫网络模型
932基尔霍夫网络的稳定性
94Pointville电网
练习
第10章影响网络
101对buzz的剖析
1011buzz网络
1012buzz网络仿真器
1013buzz网络的稳定性
102社会网络的有用性
1021两方谈判
1022Inets状态方程
1023Inets的稳定性
1024Inets的共识
1025计算影响的Java方法
103 Inets中的冲突
1031冲突度
1032计算冲突度的Java方法
104命令层次结构
105Inets中的有用性涌现
1051加权涌现
1052加权涌现的Java方法
1053加权涌现的稳定性
1054链路涌现
练习
第11章脆弱性
111网络风险
1111将节点作为目标
1112将链路作为目标
112关键节点分析
1121杠铃模型
1122网络风险最小化
1123指数成本模型
1124攻击者-防御者模型
1125Java军备竞赛方法
113博弈论的考虑
114一般的攻击者-防御者网络风险问题
115关键链路分析
1151链路弹性
1152链路弹性模型
1153流弹性
1154流启发式的Java方法
1155网络流资源分配
1156结构化网络中的最大流量
116基尔霍夫网络的稳定性弹性
练习
第12章NetGain网络
121经典扩散方程
1211市场扩散方程
1212简单NetGain网络
122多产品网络
123NetGain网络涌现的Java方法
124新兴市场网络
1241新生市场的涌现
1242新兴市场固定点
125创造性破坏网络
1251创造性破坏的涌现
1252平方根律固定点
126企业并购网络
1261合并节点的Java方法
1262合并加速创造性破坏
练习
第13章生物学
131静态模型
1311无标度属性
1312小世界效应
132动态分析
1321线性连续网络
1322布尔网络
133蛋白质表达网络
134质量动力学建模
1341质量动力学状态方程
1342有界的质量动力学网络
练习
参考文献