作者：陈增强、雷辉、史永堂 著
出版社：化学工业出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
网络科学中的度量分析与应用试读：
前言
人类社会是由复杂网络交织而成的，我们生活中处处都有网络的存在，如互联网、交通网络、代谢网络、社交网络、合作网络、生物网络、电力网络、智能物联网络、智能制造网络等，复杂网络的研究是当今科学研究中的一个热点，与现实中各类高复杂性系统的研究有密切关系。复杂网络的研究可以追溯到1736年的哥尼斯堡七桥问题，复杂网络研究的热潮源于两篇著名的文章。1998年，Nature发表了两位年轻的物理学家D.J.Watts和S.H.Strogatz关于网络的一篇论文。一年多之后，Science发表了另外两位年轻的物理学家A.L.Barabasi和R.Albert关于网络的另一篇论文。这两篇论文引发了关于复杂网络的研究热潮，这个热潮迅速席卷全球，涉及数学、物理学、计算科学、控制科学、管理科学、社会科学、金融经济科学等许多科学领域和通信、交通、能源、制造等工程技术领域。
复杂网络的表示、分析、比较和建模都十分依赖于对网络拓扑结构的属性进行定量地刻画，这些定量的描述和刻画，就是所谓的复杂网络度量。基于不同的研究目的和研究需求，引入了很多的度量，Costa等于2007年年初在Advances in Physics上发表了一篇文章，全面系统地综述了复杂网络中的各种度量。随着学者们对网络研究的不断深入，越来越多的度量被挖掘、定义和研究，但是目前还没有见到有一本专门介绍复杂网络度量的专著。
本书共分10章，第1章介绍了网络相关的基本概念以及常见的复杂网络模型，并对复杂网络度量进行了简要阐述。第2章叙述了进行复杂网络研究所需的图论领域的基础知识。第3章介绍了与距离相关的一些度量，并对特殊的距离度量:平均距离和直径，给出了幂律随机图的一些经典结果。第4章提出了一些为研究网络的聚类和圈结构而建立的度量，并讨论了一个无标度随机图的聚类系数。度分布是网络的一个重要拓扑特征，第5章主要研究了网络的度分布及相关关系，并总结了与度相关的度量。熵在离散数学、通信科学、计算机科学、信息理论、统计学、化学、生物学等不同领域有着重要的应用，学者们引进网络熵来衡量网络和图的性质，第6章我们将简要介绍网络熵的相关内容。第7章首先概述了近年来在网络特征谱方面的进展，然后利用特征谱来研究网络的一些特性。在机器学习和数据挖掘中，我们经常需要知道个体间差异的大小，进而评价个体的相似性和类别。相似性度量，即为综合评定两个事物之间相近程度的一种度量。第8章介绍一些常见的衡量网络相似性的度量。第9章进一步叙述了一些常见的复杂网络度量。第10章列举了复杂网络度量的一些相关应用，包括网络度量的极值问题、网络度量在分子网络中的应用、网络度量在社会网络中的应用等。
本书在前人工作的基础上，从图论和数学的角度为大家呈现一个网络度量的深入描绘，全面系统地介绍复杂网络的各种度量及其性质，对于从事图论、网络科学以及相关工程领域的研究人员和工程技术人员具有很好的参考价值。
本书的内容包含了作者近几年一些新的研究成果。本书在写作过程得到了许多专家学者的支持和鼓励，特别感谢上海交通大学的李少远教授，正是因为他的邀请，本书才得以入选“中国制造2025”出版工程。本书的完成也得到了国家自然科学基金、天津市人才发展特殊支持计划“青年拔尖人才”、天津市自然科学基金、中央高校基本科研业务费以及南开大学百优青年学者基金等的资助和支持。
由于作者水平有限，书中难免会有疏漏之处，敬请同行和读者不吝赐教，我们当深表感谢。著 者第1章 复杂系统与复杂网络1.1 复杂系统与复杂网络简介1.1.1 复杂系统[1，2]
系统在自然界和人类社会中是普遍存在的，如太阳系是一个系统，人体是一个系统，一个家庭是一个系统，等等。系统的种类很多，可以依据不同的原则对系统进行分类。根据系统的本质属性，从系统内子系统的关联关系角度可划分为简单系统和复杂系统。简单系统指组成系统的子系统或简单个体数量较少，因而它们之间的关系也比较简单，或尽管子系统数目多或巨大，但之间关联关系比较简单，也称为简单系统。另一类系统统称为复杂系统，它们最主要的特征是系统具有众多的子系统和状态变量，关联及反馈结构复杂，输入与输出呈现非线性特征。
复杂系统试图解释在不存在中央控制的情况下，大量简单个体如何自行组织成能够产生模式、处理信息甚至能够进化和学习的整体。这是一个交叉学科研究领域。“复杂”一词源自拉丁词根plectere，意为编织、缠绕。在复杂系统中，大量简单成分相互缠绕纠结，而复杂性研究本身也是由许多研究领域交织而成。复杂系统专家认为，自然界中的各种复杂系统，比如昆虫群落、免疫系统、大脑和经济，这些系统在细节上很不一样，但如果从抽象层面上来看，则会发现它们有很多有趣的共性。（1）局部信息，没有中央控制
在复杂系统中，个体一般都遵循相对简单的规则，不存在中央控制或领导者。每个主体只可以从个体集合的一个相对较小的集合中获取信息，处理“局部信息”，做出相应的决策。系统的整体行为是通过个体之间的相互竞争、协作等局部相互作用而涌现出来的。最新研究表明，在一个蚂蚁王国中，每一只蚂蚁并不是根据“国王”的命令来统一行动，而是根据同伴的行为以及环境调整自身行为，从而实现一个有机的群体行为。（2）信号和信息处理
所有这些系统都利用来自内部和外部环境中的信息和信号，同时也产生信息和信号。（3）智能性和自适应性
所有这些系统都通过环境和接收信息来调整自身的状态和行为进行适应，即改变自身的行为以增加生存或成功的机会。系统在整体上显现出更高层次、更加复杂、更加协调职能的有序性。
另外，复杂系统还具有突现性、不稳性、非线性、不确定性、不可预测性等特征。[3]
现在我们可以对复杂系统加以定义:复杂系统是由大量可能相互作用的组成成分构成的网络，不存在中央控制，通过简单运作规则产生复杂的集体行为和复杂的信息处理，并通过学习和进化产生适应性。如果系统有组织的行为不存在内部和外部的控制者或领导者，则也称之为自组织。由于简单规则以难以预测的方式产生复杂行为，这种系统的宏观行为有时也称为涌现。这样就有了复杂系统的另一个定义:具有涌现和自组织行为的系统。复杂性科学的核心问题是:涌现和自组织行为是如何产生的?
复杂系统理论是系统科学中的一个前沿方向，它是复杂性科学的主要研究任务。复杂性科学被称为21世纪的科学，它的主要目的就是要揭示复杂系统的一些难以用现有科学方法解释的动力学行为。与传统的还原论方法不同，复杂系统理论强调用整体论和还原论相结合的方法去分析系统。目前，复杂系统理论还处于萌芽阶段，它可能蕴育着一场新的系统学乃至整个传统科学方法的革命。生命系统、社会系统都是复杂系统，复杂系统理论在系统生物学、生物系统、社会与经济系统、计算机及通信系统、智能制造及智能交通等系统中具有重要的应用前景。1.1.2 复杂网络
网络是一组项目的集合，将这些项目称为节点，它们之间的连接，称为边。如果节点按照确定的规则连线，所得到的网络就称为规则网络。如果网络按照某种（自）组织原则方式连接，将演化成各种不同的网络，称为复杂网络。近年来，复杂网络引起了许多相关领域研究人员的关注。复杂网络是具有复杂拓扑结构和动力学行为的大规模网络，复杂网络的节点可以是任意具有特定动力学和信息内涵的系统的基本单位，而边则表示这些基本单位之间的关系或联系。例如，[4，5][6～11]Internet网、WWW网络、社会关系网络、无线通信网络、[12][13～16]食物链网络、科研合作网、流行病传播网络等都是复杂网络，如图1-1所示。生活中存在着大量的复杂网络，这促使人们去研究这些复杂网络的行为。图1-1 万维网真实连接和食物链网络示意图
钱学森先生给出了复杂网络的一个较严格的定义:具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络称为复杂网络。从目前的研究来看，复杂网络主要包含两层含义:一，它是大量真实系统的拓扑抽象;二，它介于规则网络和随机网络之间，比较难以实现，目前还没有生成能够完全符合统计特征的复杂网络。
复杂网络，简而言之，即呈现高度复杂性的网络。汪小帆教授、[17]李翔教授、陈关荣教授在《网络科学导论》一书中指出，复杂网络的复杂性主要表现在以下几个方面。
① 结构复杂性。表现在网络节点数目巨大。由于节点连接的产生与消失，网络结构不断发生变化。例如WWW，网页或链接随时可能出现或断开，节点之间的连接具有多样性。例如节点之间的连接权重存在差异，且有可能存在方向性。从而，网络结构呈现多种不同特征。
② 节点多样性。复杂网络中的节点可以代表任何事物，例如，人际关系构成的复杂网络节点代表单独个体，万维网组成的复杂网络节点可以表示不同网页。而且，在同一个网络中可能存在多种不同类型的节点。例如，控制哺乳动物细胞分裂的生化网络就包含各种各样的基质和酶。
③ 动力学复杂性。节点集可能属于复杂非线性行为的动力系统。例如节点状态随时间发生复杂变化。
④ 多重复杂性融合。即以上多重复杂性相互影响，导致更为难以预料的结果。例如，设计一个电力供应网络需要考虑此网络的进化过程，其进化过程决定网络的拓扑结构。当两个节点之间频繁进行能量传输时，它们之间的连接权重会随之增加，通过不断的学习与记忆逐步改善网络性能。
图1-2为复杂网络示例。图1-2 复杂网络示例
目前，复杂网络研究的内容主要包括:网络的几何性质、网络的形成机制、网络演化的统计规律、网络上的模型性质以及网络的结构稳定性、网络的演化动力学机制等问题。其中在自然科学领域，网络研究的基本测度包括:度及其分布特征、度的相关性、集聚程度及其分布特征、最短距离及其分布特征、介数及其分布特征，连通集团的规模分布等。
网络化是今后许多研究领域发展的一个主流方向，因此对复杂网络的研究具有重大的科学意义和应用价值。
定义1-1 如果一个网络中的任意两个节点之间都有边直接相连，那么就称这个网络为全局耦合网络（如图1-3所示）。如果一个网络中，每一个节点只和它周围的邻居节点相连，那么就称该网络为最近邻耦合网络。图1-3 6个顶点的全局耦合网络
在具有N个节点的所有网络中，全局耦合网络具有最多的边数N（N-1）/2。最近邻耦合网络是最普通的规则网络，属于该类的常见网络有三种:一维链、二维网格和一般最近邻耦合网络，如图1-4所示。三者的相同之处在于每个节点只与靠近自己的节点相连，而与远离自己的节点不相连;不同之处在于每个节点的邻点数不同。而对于拥有N个节点的最近邻耦合网络，网络中的每个节点至少有两个邻点，最多有k个邻点，k必须为偶数且不大于N。图1-4 几种不同的规则网络1.2 随机图模型
在现实世界中，不确定现象是普遍存在的。例如，漂浮在液面上的微小粒子不断地进行着杂乱无章的运动，粒子在任一时刻的位置是不确定的;又如公共汽车站等车的人数在任一时刻也是不确定的，因为随时都可能有乘客的到来和离去。这类不确定现象，表面看来无法把握，其实，在其不确定的背后，往往隐藏着某种确定的概率规律，因此，以概率和数理统计为基础的随机模型就成为解决此类问题最有效的工具之一。
如果网络的节点不是按确定的规则连线，譬如按纯粹的随机方式连线，所得到的网络就称为随机网络。1960年现代数学大师、匈牙利数学家Erds和Reni建立了随机图理论，研究复杂网络中随机拓扑模型（ER），自此ER模型一直是研究复杂网络的基本模型。
随机网络的第一个模型:给定网络节点总数N，网络中任意两个节点以概率p连线，生成的网络全体记为G（N，p），构成一个概率空间。由于网络中连线数目是一个随机变量X，取值可以从0到N（N-1）/2，有m条连线的网络数目为，其中一个具有m[NN（-1）/2]-m条连线的特定网络出现的概率为P（G）=p（1-p）mmNN（-1）/2。因此，该模型可生成的不同网络的总数为2，它们服从二项分布。网络中平均连线数目为pN（N-1）/2。
随机网络的第二个模型:给定网络节点总数N和连线总数m，而这些连线是从总共N（N-1）/2条可能的连线中随机选取的，生成的网络全体记为G（N，p），构成一个概率空间。这样可以生成不同网络的总数为，它们出现的概率相同，服从均匀分布。网络中两个节点连线的概率为p=2m/[N（N-1）]。1.3 小世界网络
Watts和Strogatz在分析了规则网络和随机网络后发现:前者不存在短路径，后者缺乏群集性;规则网络是秩序的象征，随机网络是混乱的代表;但现实网络不太可能是这两个极端之一。1967年美国社会[18]心理学家Milgram通过“小世界实验”提出了“六度分离推断”，即地球上任意两人之间的平均距离为6，也就是说只要中间平均通过5个人，你就能联系到地球上的任何人。随后，一些数学家也对此进[19]行了严格的证明。于是，1998年Watts和Strogatz在《自然》杂志上发表了一篇开创性的论文，提出了网络科学中著名的小世界网络模型（WS模型），刻画了真实网络所有的大聚簇和短平均距离的特性。小世界网络的基本模型是WS模型，算法描述如下。
① 一个环状的规则网络开始:网络含有N个节点，每个节点向与它最临近的K个节点连出K条边，并满足N≥K≥lnN≥1。
② 随机化重连:以概率p随机地重新连接网络中的每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。这样就会产生pNK/2条长程的边把一个节点和远处的节点联系起来。改变p值可以实现从规则网络（p=0）向随机网络（p=1）的转变。当p=0时，每个节点都有K个邻点，完全没有“随机跳跃边”，显示一个规则网络模型;而在0 由于WS小世界模型构造算法中的随机化过程有可能破坏网络的连通性，出现孤立的集团，而且不便于理论分析。于是，Newman和[20]Watts提出了NW小世界网络模型，该模型是通过用“随机化加边”取代WS小世界网络模型构造中的“随机化重连”。NW小世界模型构造算法如下。 ① 一个环状的规则网络开始:网络含有N个节点，每个节点向与它最临近的K个节点连出K条边，并满足N≥K≥lnN≥1。 ② 随机化加边:以概率p在随机选取的一对节点之间加上一条边。其中，任意两个不同节点之间至多只能有一条边，并且每个节点都不能有边与自身相连。改变p值可以实现从最近邻耦合网络（p=0）向全局耦合网络（p=1）转变。当p足够小且N足够大时，NW小世界模型本质上等同于WS小世界模型。1.4 无标度网络 WS模型能够反映现实网络的小世界特征，然而现实世界中的网络还被统计到极少节点拥有大量的连接，而众多的节点仅具有少量连接的特征，这些也无法用随机模型加以合理解释。 ER随机图和WS小世界模型的一个共同特征就是网络的度分布可近似用泊松分布来表示，该分布在度平均值 考虑幂律函数y（x）=cx和指数函数z（x）=c。现在改变测量单位（标度），即乘以因子λ，看看这两个函数对标度改变的反应。显然 （1-1） （1-2） 式（1-1）说明函数图形的形状没有变化，同时函数的指数也不变。然而，从式（1-2）可知:函数图形的形状已经改变，或者函数的指数需乘以因子。这说明幂律函数具有标度不变性，即不依赖于所采用的测量单位;而指数函数则不具备这种特性。 Barabsi和Albert指出ER随机图和WS小世界模型忽略了实际网络的两个重要特性: ① 增长特性，即网络的规模是不断扩大的; ② 优先连接特性，即新的节点更倾向于与那些具有较高连接度的hub节点相连接。这种现象也称为“富者更富”或“马太效应”。 基于上述增长和优先连接特性，Barabsi和Albert提出了BA无标度网络模型，见如下算法。 BA无标度网络模型构造算法如下。 ① 初始:开始给定N个节点。增长:在每个时间步重复增加一个新0节点和K（K≤N）个节点新连线。0 ② 择优:新节点按照择优概率选择旧节点i与之连线，其中k是旧节点i的度数。i 实证研究发现，许多现实网络，包括社会网络、信息网络、技术网络和生物网络都具有标度不变性，因此无标度网络的提出，极大地激发了科学界对网络科学的研究热情。1.5 社团结构的网络 近年来对众多实际网络的研究发现，它们存在一个共同的特征，称之为网络中的社团结构。它是指网络中的节点可以分成组，组内节[25]点间的连接比较稠密，组间节点的连接比较稀疏，见图1-5。社团结构在实际系统中有着重要的意义:在社会网络中，社团可能代表具[26]有类似兴趣爱好的人群;在引文网中，不同社团可能代表了不同的研究领域;在食物链网中，社团可能反映了生态系统中的子系统;在万维网中，不同社团反映网络的主题分类。图1-5 一个小型的具有社团结构性质的网络 总之，分析大型网络中的社团结构有很大的潜在价值，因为属于同一社团结构的点往往具有某些相同的属性，这便于人们发现隐藏在网络中个体连接背后的信息。因此，对网络中社团结构的研究是了解整个网络结构和功能的重要途径，网络社团结构的划分与度量成为新的热点。 关于网络中的社团结构，目前还没有被广泛认可的唯一的定义，较为常用的是基于相对连接频数的定义:网络中的节点可以分成组，组内连接稠密而组间连接稀疏。这一定义中提到的“稠密”和“稀疏”都没有明确的判断标准，所以在探索网络社团结构的过程中不便使用。因此人们试图给出一些定量化的定义，如提出了强社团和弱社团的定义。强社团的定义为:子图H中任何一个节点与H内部节点连接的度大于其与H外部节点连接的度。弱社团的定义为:子图H中所有节点与H内部节点的度之和大于H中所有节点与H外部节点连接的度之[27]和。此外，还有比强社团更为严格的社团定义——LS集。LS集是一个由节点构成的集合，它的任何真子集与该集合内部的连边都比与该集合外部的连边多。另一类定义则是以连通性为标准定义的社团，[28]称之为派系。派系是指由3个或3个以上的节点组成的全连通子图，即任何两点之间都直接相连。这是要求最强的一种定义，它可以通过弱化连接条件进行拓展，形成n-派系。例如，2-派系是指子图中的任意两个节点不必直接相连，但最多通过一个中介点就能够连通;3-派系是指子图中的任意两个节点，最多通过两个中介点就能连通。随着n值的增加，n-派系的要求越来越弱。这种定义允许社团间存在重叠[29]性。所谓重叠性是指单个节点并非仅仅属于一个社团，而是可以同时属于多个社团。社团与社团由这些有重叠归属的节点相连。有重叠的社团结构问题有很好的研究价值，因为在实际系统中，个体往往同时具有多个群体的属性。 上述社团的定义来自文献[27]，除这个定义外，还有多种其他定义方式，文献[6]进行了更为详细的介绍。1.6 网络的网络 网络科学的跨学科领域在过去二十年中引起了广泛的关注，尽管大多数研究成果都是通过分析单一网络获得的。然而，现实世界总是存在着大量相互关联和彼此依存的错综复杂的网络。 长期以来，人们想弄明白参与者——不管是身体器官、人员、公交车站、公司还是国家——是如何连接、交互，创造出网络结构的。20世纪90年代后期，随着网络科学的突飞猛进，网络如何运作以及为何有时又会发生故障，这些问题都得到了深入而细致的分析。但是近来一些研究者意识到，仅仅了解独立的网络如何工作是不够的，研究网络之间如何交互同样重要。如今，前沿领域不再是网络科学，而是研究“网络的网络”的科学。 网络的网络是常见的，多样化的关键基础设施系统通常耦合在一起，包括水、食品和燃料供应系统以及通信、金融市场和电力供应。人体、大脑、呼吸和心脏系统中的不同系统经常相互作用并相互依存，包括Facebook、Twitter和微博在内的社交网络在数亿人生活中都扮演着重要角色，并将用户连接到跨地域的互动网络系统。深化对“网络的网络”的了解，对于许多学科来说是重要的，并具有现实世界的应用。“网络的网络”或超网络，实际上都是典型的复杂开放系统，网络之间相互嵌套、相互依存、彼此关联、相互影响，它们至少具有下列诸多特点之一:多层性、多维性、多属性、多重性、多目标、多参数、多准则、多选择。在文献[29]中，方锦清教授详细阐述了“网络的网络”的特点。 Boccaletti等12人在国际著名的《物理报告》中发表“多层网络[29][30]的结构与动力学”综述，从多层网络角度，结合“网络的网络”的主要特点，首次从数学上给出正式定义。他们给出的这个定义很适合描述社会系统以及其他复杂网络系统中的多层次网络及其许多现象。例如，可以同时考虑在不同社群之间的相互链接、不同层之间的关联性质以及每个层次的特殊性与整体网络的关系。 在相互依赖的网络中，一个网络中节点的故障导致其他网络中依赖节点的故障，这又可能对第一个网络造成进一步的损害，导致级联故障和可能的灾难性后果。因此，目前的研究结果表明，网络的网络产生灾难性危害的风险高于单独的网络系统。一个看似无害的干扰可以像涟漪一般造成扩散性的负面效应。有时候这种效应造成的损失可达数百万甚至数十亿美元之巨，比如股票市场崩溃、半个印度停电或者冰岛火山喷发造成航线关闭以及酒店和租车公司倒闭等。在另外一些情况下，网络的网络内部是否发生故障可能意味着疾病是小规模爆发还是大面积流行，一场恐怖袭击是被挫败还是夺去几千人生命。“当我们孤立地考量单一的一个网络，我们便错失了相当多的背景信息。”加州大学戴维斯分校的物理学家、工程师雷萨·德苏萨说，“我们会做出与真实系统不符的错误预测。” 揭示未知的相互作用只是网络的网络研究的课题之一。网络之间的联结强度也很重要。如今，科学家们有了一幅网络科学的未来地图，网络的网络提供了一片令人兴奋的新疆域，但人们才只是刚刚踏足其中。“我们需要定义新的数学工具。”维斯皮那尼说，“我们需要收集很多数据。我们需要不断探索才能真正摸清这片领域的情况。”1.7 大数据时代的网络分析 我们生活在一个互联实体构成的复杂世界中。人类涉足的所有领域，从生物学到医学、经济学和气候科学，都充满了大规模数据集。 大数据时代的数据呈现大量、多样、真实、快速、价值等特点。这些数据集将实体模拟为节点，节点之间的连接被模拟为边，从不同且互补的角度描述着复杂的真实世界系统。 数据时代的到来给致力于复杂网络的研究带来了新的机遇和挑战。国务院于2015年8月颁发的《促进大数据发展行动纲要》中明确要求要“融合数理科学、计算机科学、社会科学及其他应用学科，以研究相关性和复杂网络为主，探讨建立数据科学的学科体系”。 复杂网络的研究历程体现了人们处理数据的能力不断提升。以小世界实验为例，米尔格拉姆当初的实验只涉及到300人左右。2001年，Watts等人建立了一个“小世界项目”网站以检验六度分离假说，有6万多名志愿者参加了该实验。近年来，各种在线社会网络不断涌现，产生了规模越来越庞大的网络数据。2011年，Facebook信息平台对于其平台上大约7.21亿个活跃用户的研究表明，两个用户之间的平均[31]距离仅为4.74;2016年2月发布的结果表明，Facebook上大约15.9亿[32]活跃用户之间的平均距离缩短到了4.57。汪小帆教授在文献[33]中总结了数据时代的网络科学研究特别关注的一些问题，其中包括基于数据的网络构建、特征挖掘、特征建模、网络控制等重要问题。（1）基于数据的网络构建 随着人们能够收集的数据规模越来越大，种类日益增多，如何基于大数据构建合适的网络也变得日益重要。例如，互联网和WWW等网络通常通过爬取等方式获得不完整节点和连边，而生物网络中的许多连边（如蛋白质之间的相互作用）目前尚未能通过实验获取。因此，对实际复杂网络进行分析面临如下问题:如何获得高质量的网络结构数据?如何科学地分析数据质量?对不完整的网络结构数据所做的分析在多大程度上能够推广到整个网络?此外，即使有了高质量的网络数据，针对所研究的问题，往往也需要对数据做恰当的预处理以生成合适的网络。（2）基于网络的特征挖掘 近年来，人们从不同的角度尝试揭示实际复杂网络的各种结构性质，并取得了不少有价值的成果。但是，网络科学发展到今天已远不能仅仅停留在计算小世界和无标度等性质的水平上，必须要有新的发现与认识，解决新的问题，如:哪些拓扑性质对刻画网络结构具有重要性?各种拓扑性质之间具有什么样的关系?同时，如何有效处理包含数千万乃至数亿节点的网络等相关的算法问题也是在大数据背景下面临的新挑战。基于大数据的算法研究有可能成为复杂性科学研究的技术基础之一，从节点重要性分析、社团结构挖掘到链路预测和推荐算法等，其算法复杂性分析、快速近似算法、并行计算、分布式图存储问题等都值得深入研究。（3）基于特征的网络建模 前些年网络科学研究主要集中于固定拓扑结构的网络，而现实网络很多是随时间和空间变化的。在含有时间空间的网络上的动力学过程可能会呈现出与静态网络和非空间网络极为不同的规律。许珺等在《中国计算机学会通讯》上发表的文章对空间网络数据挖掘作了很好[34]的综述。此外，以前网络科学研究主要针对的是单个网络，而事实上许多网络都不是孤立存在的，而是与其他网络之间存在着相互依赖、合作或竞争等关系。随着数据获取能力的不断增强，对多层网络[35]（也称网络的网络）的理论与应用研究将会不断深入。（4）数据驱动的网络控制 在控制界，对大系统控制的研究已有较长的历史并取得了不少成果。对于大规模复杂网络系统的控制而言，近年关注的重点是能否以[31]及如何通过对部分节点直接施加控制而达到控制目标。一些挑战性问题包括:①可行性问题，当网络规模很大时，控制理论中已有的判据和算法的计算复杂度往往难以承受，因此需要寻找新的有效算法;②有效性问题，如何选取受控节点才能使得达到控制目标所花的代价尽可能小;③鲁棒性问题，大规模复杂网络往往面临由于随机故障或者有意攻击而导致的节点或连边失效，需要给出判别大规模网络控制系统中的关键节点和连边的有效算法。1.8 复杂网络度量简介 复杂网络的研究可以被概念化为图论和统计力学之间的交叉，具有真正的多学科性质。每个复杂网络都会呈现一些特定的拓扑特性，它们描述了复杂网络的连通性和在网络上执行过程的动态的高度影响。复杂网络的分析、辨别、合成要依靠度量来描述。 2012年，《Nature Physics》第一期聚焦复杂性，Barabsi在题[36]为“网络取而代之”的评论中犀利地指出，基于数据的复杂系统的数学模型正以一种全新的视角快速发展成为一个新的学科:“网络科学”。网络科学的普适性使得利用网络来建模并研究现实系统的功能和性质成为可能。网络的拓扑结构属性刻画了个体的连接方式并深刻影响着网络上的动态功能过程，因此识别、分析网络功能和性质就依赖于对网络拓扑结构属性的有效量化。 对大规模网络结构性质的有效度量方法也是一个值得关注的重要课题。例如，对节点数在百万以上的大规模复杂网络的社团结构分析仍然缺乏有效的计算方法，需要在算法速度和精度之间做很好的折中。此外，尽管无标度被认为是许多实际网络的一个特性，如何判断实际网络的度分布是否可以近似用幂律分布来表示仍然需要仔细分析。 复杂网络的广泛研究源于其在建模真实数据结构时表现出的灵活性和普适性。一个复杂网络可以展示出刻画系统中个体的连接关系以及影响系统动态功能行使的结构特性。关于复杂网络结构特性度量方面的研究工作涉及到:将一个目标系统表示成网络结构;通过一系列富含系统结构信息的度量指标，分析网络拓扑结构属性;量化演化网络的结构属性值的变化，说明系统动态演化过程中网络的连接关系是如何变化的;使用拓扑结构度量指标来挖掘不同结构类型的子图模式;以及比较人们提出的模型网络和真实网络中特定度量值，来验证模型的正确性。可以看出，复杂网络的表示、分析、比较和建模都十分依赖于网络拓扑结构属性的定量刻画。 为了描述复杂网络的结构和特性，引入了多种度量方法，包括基于距离的度量、聚类系数、度相关性、网络熵、中心性、子图、谱分析、基于社团的测量、分层度量和分形维数。在2003年，[37]Newman对各种技术和模型进行了回顾，以帮助人们理解或预测这些系统的行为，包括诸如此类的概念，如小世界效应、度分布、集群、网络相关性、随机图模型、网络增长模型和优先附件，以及在网络上[38]发生的动态过程。2007年，Costa等人撰写了关于复杂网络度量的综述。可能这是针对这个话题的第一个比较全面的综述，得到了越来越多研究人员的关注。众所周知，图论在复杂网络的研究中起着重要[39～41]的作用，计量图论是属于图论和网络科学的一个新分支。基于Costa等人的综述文章，南开大学的陈增强教授、Dehmer教授和史永[42]堂教授撰写了一篇新的综述文章，收录在《Modern and Interdisciplinary Problems in Network Science:A Translational Research Perspective》一书中，从图论和数学的角度为大家呈现了一个网络度量的简明综述。参考文献[1] 钱学森，于景元，戴汝为.一个科学新领域——开放的复杂巨系统及其方法论[J].自然杂志，1990，（1）:3-10. [2] 赵亚男，刘焱宇，张国伍.开放的复杂巨系统方法论研究[J].科技进步与对策，2001，18（2）:21-23. [3] 梅拉妮·米歇尔.复杂[M].唐璐译.长沙:湖南科学技术出版社，2011.[4] Albert R，Jeong H，Barabasi A L.Diameter of the World-Wide Web[J].Nature，1999，401（6749）:130-131.[5] Broder A，Kumar R，Maghoul F，Raghavan P，Rajalopagan S，Stata R，Tomkins A and Wiener J.Graph Structure in the Web[J].Compuer Networks，2000，33:309-320.[6] Wasserman S，Faust K.Social Network Analysis:Methods and Applications[M].Cambridge，UK:Cambridge Univ Press，1994.[7] Scott J.Social Network Analysis:A Handbook[M].London:Sage Publications，2000.[8] Freeman L.The Development of Social Network Analysis[M].Vancouver:Empirical Press，2006. [9] 刘军.社会网络分析导论[M].北京:社会科学文献出版社，2004.[10] Borgatti S P，Mehra A J，et al.Network Analysis in the Social Sciences[J].Science，2009，323（5916）:892-895. [11] 周涛，汪秉宏，韩筱璞，等.社会网络分析及其在舆情和疫情防控中的应用[J].系统工程学报，2010，25（6）:742-754.[12] Pimm S L.Food Webs[M].Chicago:University of Chicago Press，2002.[13] Newman M E J.Scientific Collaboration Network:I，Network Construction and Fundamental Results[J].Physical Review E，2001，64（1）:016131.[14] Newman M E J.Scientific Collaboration Network:II，Shortest Paths，Weighted Networks，and Centrality[J].Physical Review E，2001，64（1）:016132.[15] Newman M E J.The Structure of Scientific Collaboration Networks[J].Proceeding of the National Academy of Sciences of the United States of America，2001，98（2）:404-409.[16] Barabsi A L，Jeong H，Nda Z，et al.Evolution of the Social Network of Scientific Collaborations[J].Physica A:Statistical Mechanics and its Application，2002，311（3-4）:590-614. [17] 汪小帆，李翔，陈关荣.网络科学导论[M].北京:高等教育出版社，2012.[18] Travers J，Milgram S.An Experimental Study of the Small World Problem[J].Sociometry，1969:425-443.[19] Watts D J，Strogatz S H.Collective Dynamics of‘Small-World’Networks[J].Nature，1998，393（6684）:440-442.[20] Newman M E J，Watts D J.Renormalization Group Analysis of the Small-World Network Model[J].Physics Letters A，1999，263（4）:341-346.[21] Jeong H，Mason S P，Barabsi A L，et al.Lethality and Centrality in Protein Networks[J].Nature，2001，411（6833）:41-42.[22] Maslov S，Sneppen K.Specificity and Stability in Topology of Protein Networks[J].Science，2002，296（5569）:910-913.[23] Barabsi A L，Albert R.Emergence of Scaling in Random Networks[J].Science，1999，286（5439）:509-512.[24] 史定华.网络度分布理论[M].北京:高等教育出版社，2011.[25] Girvan M，Newman M E J.Community Structure in Social and Biological Networks[J].Proceeding of the National Academy of Sciences of the United States of America，2002，99:7821-7826.[26] Redner S.How popular is your paper?An Empirical Study of the Citation Distribution[J].The European Physical Journal B-Condensed Matter and Complex Systems，1998，4:131-134.[27] 李晓佳，张鹏，狄增如，等.复杂网络中的社团结构[J].复杂系统与复杂性科学，2008，5（3）:19-42.[28] Palla G，Dernyi I，Farkas I，et al.Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society[J].Nature，2005，435（7043）:814-818.[29] 方锦清.从单一网络向《网络的网络》的转变进程——略论多层次超网络模型的探索与挑战[J].复杂系统与复杂性科学，2016，13（1）:40-47.[30] Kurant M，Thiran P.Layered Complex Networks[J].Physical Review Letters，2006，96（13）:138701.[31] Backstrom L，Boldi P，Rosa M，et al.Four Degrees of Separation[C].New York:AMC，2012:33-42.[32] Edunov S，DiukIsmail C，Filiz O，et al.Three and a Half Degrees of Separation[J].Research at Facebook Blog，2016.[33] 汪小帆.数据时代的网络科学[J].中国计算机学会通讯，2016，4.[34] 许，陈娱，徐敏政.空间网络的数据挖掘和应用[J].中国计算机学会通讯，2015，11（11）:40-49.[35] Gao Jianxi，Buldyrev S V，Stanley H E，et al.Networks Formed from Interdependent Networks[J].Nature Physics，2012，8:40-48.[36] Barabsi A L.The Network Takeover[J].Nature Physics，2012，8（1）:14-16.[37] Newman M E J.The Structure and Function of Complex Networks[J].SIAM Review，2003，45（2）:167-256.[38] Costa L F，Rodrigues F A，Travieso G.Characterization of Complex Networks:A Survey of Measurements[J].Advances in Physics，2007，56:167-242. [39] Dehmer M，Emmert-Streib F.Quantitative Graph Theory-Mathematical Foundati ons and Applications[M].Boca Raton:CRC Press，2015.[40] Dehmer M，Emmert-Streib F，Shi Yongtang.Quantitative Graph Theory:A New Branch of Graph Theory and Network Science[J].Information Sciences，2017，418:575-580. [41] Lang Rongling，Li Tao，Mo Desen，et al.A Novel Method for Analyzing Inverse Problem of Topological Indices of Graphs Using Competitive Agglomeration[J].Applied Mathematics & Computation，2016，291:115-121.[42] Chen Zengqiang，Dehmer M，Shi Yongtang.Measurements for Investigating Complex Networks.In:Modern and Interdisciplinary Problems in Network Science:A Translational Research Perspective[M].Boca Raton:CRC Press，2018. 第2章 图论简介 图论是一门应用十分广泛的数学分支，应用图论解决运筹学、物理、化学、生物、计算机科学、网络理论、信息论、控制论、社会科学以及管理科学方面的问题都有其独特的优越性。图论与数学的其他分支如群论、矩阵论、概率论、拓扑、数值分析、组合数学等都有着密切的关系。事实上，图为任何一个包含一种二元关系的系统提供了一种数学模型。 众所周知，图论起源于一个非常经典的问题——哥尼斯堡七桥问题（见图2-1）。普莱格尔河流经哥尼斯堡小城，河中有两个小岛，在四块陆地之间修建了七座小桥，将河中间的两个岛和河岸联结起来。是不是可能存在路径，使得人们可以走遍四个地区，而且把每座桥走一次并且只走一次?这在图论中称为“欧拉图”问题。图2-1 七桥问题 1738年，瑞典数学家欧拉解决了哥尼斯堡七桥问题。他将四块陆地视为结点，七座小桥成为连接四个结点的连线，从而证明了这样的路径是不存在的。由此图论诞生，欧拉也成为图论的创始人。 本章主要介绍一些图论的基本概念、符号和相关结果，供初学者[1～3]入门。2.1 基本概念和符号 一个图G是包含点集V（G）和边集E（G）的有序对，其中每条边是两个顶点的一个集合。一条边的顶点称为它的端点，用uv表示一条具有端点u和v的边。一条边的端点称为与这条边关联，反之亦然。与同一条边关联的两个点称为相邻的，与同一个顶点关联的两条边也称为相邻的。端点重合为一点的边称为环，有相同端点对的边称为重边。如果一个图既没有自环也没有重边，就称这个图为简单图，否则，称为重图。 一个图如果它的顶点集和边集都有限，则称为有限图。没有顶点的图称为零图。不含边的图称为空图。只有一个顶点的图称为平凡图，其他所有的图都称为非平凡图。 一条路是顶点被安排在一个线性序列里使得两个点是相邻的，当且仅当它们在这个序列里是连续的一个简单图。同样，一个圈是顶点被安排在一个圈序列里使得两个点是相邻的，当且仅当它们在这个序列里是连续的一个具有相同数目顶点和边的图。一条路或一个圈的长度是它们所包含边的数目。对一个圈，按照所含边的数目是奇数还是偶数，称这个圈是奇圈还是偶圈。图2-2描述了一条长为3的路和一个长为5的圈。图2-2 一条长为3的路和一个长为5的圈 每对顶点之间均有一条边连接的简单图称为完全图。简单图G=（V，E）的一个团是指V中的一个子集S，使得G[S]是完全图。G的团数是G中所有团的最大顶点数。若G=（V，E）中，可以把顶点集合V分割为两个互补的子集S，T（S∪T=V，S∩T=⌀），使得每条边都有一个端点在S中，另一个端点在T中，则称G为二部图。这样一种分类（S，T）称为图G的一个二分类。完全二部图是具有二分类（S，T）的简单二部图，其中S中的每个顶点都与T中每个顶点相连。星是满足|S|=1或|T|=1的完全二部图。利用圈的概念，可以给出二部图的一个特征:一个图是二部图当且仅当它不包含奇圈。图2-3展示了一个完全图、一个完全二部图和一个星。
试读结束[说明：试读内容隐藏了图片]