复杂网络

复杂网络是一种理解现实世界复杂系统的抽象模型。它将复杂系统中的实体抽象成节点 ，将实体之间的关系抽象成连线。虽然数学中的图论也在研究网络， 但是现实中的网络会有更多的随机特性。因此，复杂网络 一般更加关注网络的统计特征。在网络理论的背景下，复杂网络是一个具有非平凡拓扑特征的图(网络)ーー这些特征不会出现在简单的网络中，如格或随机图，而是经常出现在代表实际系统的网络中。复杂网络的研究是一个年轻而活跃的科学研究领域[1][2][3](自2000年以来) ，主要受到计算机网络、生物网络、技术网络、大脑网络、气候网络和社会网络等现实世界网络的经验性发现的启发。

定义

大多数社会、生物和技术网络显示了大量非平凡的拓扑特征，它们的元素之间的连接模式既不是纯规则的也不是纯随机的。这些特征包括程度分布的重尾，高集聚系数，顶点之间的协调性或不协调性，社团结构和等级结构。在有向网络的情况下，这些特征还包括互惠性、三元显著性特征和其他特征。相比之下，许多过去研究过的网络数学模型，例如格和随机图，并没有表现出这些特征。最复杂的结构可以通过具有中等数量相互作用的网络来实现。即对于中等概率而言，最大信息量(熵)是可获得的。

在网络理论的研究中，复杂网络是由数量巨大的节点和节点之间错综复杂的关系共同构成的网络结构。用数学的语言来说，就是一个有着足够复杂的拓扑结构特征的图。复杂网络具有简单网络，如晶格网络、随机图等结构所不具备的特性，而这些特性往往出现在真实世界的网络结构中。复杂网络的研究是现今科学研究中的一个热点，与现实中各类高复杂性系统，如互联网网络、神经网络和社会网络的研究有密切关系。

而无标度网络和小世界网络是复杂网络研究的热点，它们的发现和定义是该领域的典型案例。两者都拥有着各自独有的结构特征。即无标度网络的幂律度分布和小世界网络的短路径长度和高聚集性。然而，随着复杂网络研究的重要性和普及程度的不断提高，网络结构的许多其他方面也引起了人们的关注。

近年来，复杂网络的研究已经扩展到多层网络。如果这些网络是相互依存的，它们比单一网络更容易受到随机故障和有针对性的攻击，并出现级联故障和一级渗透过渡。此外，还研究了节点失效和恢复情况下网络的集体行为。人们已经发现，这样的网络可能会出现自发的失败和自发的恢复。

这个领域继续以快速的步伐发展，并且汇集了来自数学、物理学、电力系统、生物学、气候学、计算机科学、社会学、流行病学等许多领域的研究人员。来自网络科学和工程学的思想和工具已经应用于代谢和遗传调控网络的分析; 生态系统稳定性和稳健性的研究; 临床科学; 可扩展通信网络的建模和设计，如复杂无线网络的生成和可视化; 疫苗接种战略的发展以控制疾病; 以及广泛的其他实际问题。同时，网络理论最近被发现可以用来识别城市交通中的瓶颈。网络科学是各个领域许多会议的主题，也是众多外行人和专家著作的主题。

复杂网络研究简史

欧拉与格尼斯堡七桥问题

格尼斯堡的七桥是一个历史上著名的数学问题。1736年欧拉·莱昂哈德的负分辨率奠定了图论的基础，预示了拓扑学的概念。 普鲁士的格尼斯堡（现在是俄罗斯的加里宁格勒）坐落在普瑞格尔河的两侧，包括两个大岛——克内夫和洛姆斯，它们通过7座桥互相连接在一起，且与城市的两个大陆部分相连。问题是设计出一种穿越城市的方式，每座桥都要经过有且只有一次。 通过明确制定逻辑人物的方式，解决方案包括其中任何一个： 1.通过桥梁或其他途径到达岛屿或大陆彼岸 2.不经过另一端而经过桥（但，这是绝对不可能的） 欧拉证明了这个问题没有解决方案。他所面临的困难是开发出一种合适的分析技术，以及后面的测试，这些测试需要用精确的数学方法证明这一论断。

ER随机网

在数学领域的图论中，ER模型与两种用来生成随机图像的模型密切相关。它们是以两个于1959年首次介绍其中一个模型的数学家艾迪胥·保罗和瑞尼·阿尔弗莱德命名的，而吉尔伯特·埃德加介绍了另一个，同时也独立介绍了艾迪胥和瑞尼介绍的模型。在艾迪胥和瑞尼模型中，所有图形在一个固定的顶点及固定数量的边缘上是等可能的；在吉尔伯特介绍的模型中，每条边都有固定的出现或不出现的概率，与其他边无关。这些模型可用于概率方法，以证明满足各种性质的图像的存在，或提供一个它对几乎所有图形的属性的意义的严格的定义。

小世界网络

通过类比小世界现象（通常称作六度分离），网络可以称为小世界网路。由匈牙利作家卡林西·弗里杰什于1929首次提出，米尔格拉姆·斯坦利于1967年通过实验检验小世界的假设，阐述为任意两个人之间所间隔得人不会超过六个，即相应的社会关系图的直径不大于6。瓦特·詹姆斯·邓肯和斯托加茨·斯蒂芬于1988年发表了第一个小世界网络通过单个参数在随机图像和格子之间的平滑插值体现的模型。该模型证明了只有一小部分远程链接，正则图，在网络的直径大小成正比。该结论可以转换成一个“小世界”中任意两个顶点之间的边的平均数量是非常小的（精确地说，网络的尺寸呈对数增长），而聚类系数大。众所周知，各种各样的抽象图像都具有小世界的特性，例如：随机图像和无标度网络。此外，真实世界的网络，如万维网和代谢网络也显示出这种特性。 在有关网络的科学文献中，“小世界”一词有一些含糊不清的地方。除了表示网络直径的大小，还可以表示小直径和聚类系数的同时出现。聚类系数时表示网络中三角形密度的指标。例如，系数随机图的聚类系数可以忽略不计，而现实网络的聚类系数往往要大得多。科学家指出，这种差异表明，在现实世界的网络中，边缘是相关的。

无标度网络

无标度网络是一个符合幂律的度分布网络，至少是渐近的。也就是说，网络中有k个节点的节点分式P(k)对于k为较大的值，如，同时，γ参数的值通常是在2到3之间，虽然有时也可能在这些范围之外。 一些报告表明，许多网络是无标度的，尽管统计分析驳斥了其中许多的说法，并对其他说法提出了严重质疑，他们提出了优先依附和适应度模型作为解释真实网络中推测的幂律分布的机制。

对无标度网络的兴趣始于1990年代后期，当时报告了在现实世界网络中幂律分布的发现，如万维网、自治系统网络、一些互联网路由器网络、蛋白质互动网络、电子邮件网络等。建立具有幂律分布的网络有许多不同的方法。圣诞过程是幂定律的典型生成过程，自1925年就为人所知。然而，由于其频繁的重新发现，它被许多其他的名字所熟知，例如，赫伯特·西蒙的吉布拉特原则，马太效应，累积优势，巴拉巴西和阿尔伯特的幂律度分布的优先依恋。近年来，双曲几何图被认为是构造无标度网络的另外一种方法。一些具有幂律分布的网络(以及其他特定类型的网络结构)可以很好地抵抗节点的随机删除ーー也就是说，绝大多数节点保持连接在一个巨大的组件中。这种网络对于旨在快速破坏网络的有针对性的攻击非常敏感。

当图是均匀随机的，除了度分布，这些临界顶点是最高度的，因此牵涉到疾病(包括自然与人为)在社会和通信网络的传播、时尚的传播(两者都是模型渗流或分支过程)。随机图(ER)的节点间的顺序为 log N的平均距离，其中 N是节点数，无标度图可以有 log log N的距离。这样的图被称为超小世界网络。

网络科学

网络科学是研究电信网络、计算机网络、生物网络、认知语义网络、社会网络等复杂网络的学术领域。该领域考虑节点（或顶点）所代表的不同元素或参与者，以及元素或参与者之间为链接（或边）的连接。该领域采用的理论和方法包括数学的图论、物理的统计力学、计算机科学的数据挖掘和信息可视化、统计学的推理建模和社会学的社会结构。美国国家研究委员会 将网络科学定义为“研究物理、生物和社会现象的网络表征，从而得出这些现象的预测模型”。

表示与分类

邻接矩阵

在图论和计算机科学中，邻接矩阵是用于表示有限图的方阵。矩阵的元素表明图中顶点对是否相邻。在有限简图的特殊情况下，邻接矩阵是一个（0，1）对角线逻辑矩阵上为0的矩阵。如果图是无向的，则邻接矩阵实对称的对称图像。谱图理论研究了图与其邻接矩阵的特征值和特征向量之间的关系。邻接矩阵应与图的关联矩阵分开，邻接矩阵是一种不同的矩阵表示，其元素表示顶点——对边是否有关联，度矩阵包含了每个顶点（图论）的度（图论）的信息。

网络分类

加权网

加权网是直接点之间的连结具有分配给它们权值的网络。网络是一个元素以某种方式连接在一起的系统（沃瑟曼和浮士德，于1994年）。系统的元素表示为节点（也称为参与者或顶点），交互元素之间的连接被称为连结、边、弧或链接。节点可以是神经元、个人、团体、组织、航站楼，甚至是国家，而连结可以是友谊、交流、合作、联盟、流动或贸易等形式。 在许多现实世界的网络中，并非网络中的所有连结都具有相同的容量。事实上，连结往往与权数有关，以他们的力度、强度、能力 （巴拉特.et al.,于2004年；霍瓦特，于2011年）区分。一方面，格兰诺维·马克（于1973年）认为，社交网络中社交关系的强度是其持续时间、情感强度、亲密度和服务交换的函数。另一方面，非社会网络，权重通常指的是执行的函数关系，例如，在食物网中，物种之间的碳流量（毫克/m²/天）（拉士克维施.et al.，于2003年），神经结的数量和缝隙连接神经网络（沃茨和斯特里伽茨，于1998年），或在交通网络中的流动的流量（奥普萨尔 et al.,于2008年）。 通过记录连结强度，可以创建一个加权网络（也称价值网络）。下面是这样一个网络的例子（权重也可以通过赋予变换不同的宽度来可视化）： [[1]] 加权网络也广泛应用于基因组和系统生物学应用。（霍瓦特，于2011年）。例如，加权基因共表达网络分析（WGCNA）常用于构建基于基因表达（如微阵列）数据的基因（或基因产物）之间的加权网络（张某和霍瓦特，于2005年）。一般而言，加权相关网络可以用软阈值法定义变量之间的两两相关关系（如基因检测）。

流网络

在图论中，流网络（也称运输网络）是一个有向图，其中每条边都有一个容量，每条边接受一个流量。边缘上的流量不能超过边缘的流量。通常来说，在运筹学[2]中，有向图成为网络，那些顶点被称为节点，这些边称为弧。流量必须满足流入节点的流量等于流出节点的流量的限制，除非它是一个只有流出流或汇聚即只有流入流的源。一个网络可以用来模拟道路系统中的交通，需求环流，管道中的流体，电路中的电流，或任何类似的东西通过一个节点网络时的情况。

空间网

空间网络(有时也称为几何图形)是指顶点或边是与几何对象相关联的空间元素的图像，即节点位于具有一定度量的空间中。最简单的数学实现是格子或随机几何图形，它们的节点在二维平面上均匀分布；如果欧几里得距离小于给定的邻域半径，则连接一对节点。交通和移动网络、互联网、移动电话网络、电网、社交和联系网络以及神经网络都是底层空间相关的例子，而图的[3]本身并不包含所有信息。描述和理解空间网络的结构、弹性和演化对从城市主义到流行病学的许多不同领域都至关重要。

二分网

二分网是一类特殊的复杂网络，其节点被划分为两个集合X和Y，只允许不同集合中两个节点之间的连接。为了方便直接显示特定一组节点之间的关系结构，通常采用单模投影的方式压缩二分网。这意味着接下来的网络只包含两个集合中的任意一个节点，并且只有当两个X(或者Y)节点至少有一个公共相邻的Y(或者X)节点时，它们才会连接。 最简单的方法涉及到双方的网络投射到一个未加权的网络，但不考虑网络的拓扑结构或共享一个连接的频率对立的元素集。由于在这种情况下，双方的网络很大程度上与不同的结构可以有完全相同的一种模式表示,一个清晰的插图的原始网络拓扑通常需要使用一些加权法。[[4]]

统计指标

在统计和研究设计中，指标是一种复合统计——衡量一组具有代表性的单个数据点的变化，或者换句话说，综合多个指标的复合度量。指标总结和排列特定的观察。 社会科学领域的许多数据都用各种指数表示，如性别差距指数、人类发展指数或道琼斯工业平均指数。 各项指标通常权重相等，除非有一些理由违反(例如，如果两个项本质上反映了变量的相同方面，那么它们的权重可能为0.5)。 构建项目涉及四个步骤。首先，项目的选择应该基于它们的面部效度[5]、单维性、测量维度的特异性程度以及它们的方差。项目之间应该有经验上的联系，这引向了检验它们的多元关系的第二步。第三，设计索引得分，这涉及到确定它们的得分范围和项目的权重。最后，需要对指标进行验证，这涉及到是否能够预测与构建中未使用的测量变量相关的指标。

度

在图论中，图的顶点的度(或值)是指与该顶点关联的、循环数为2次的边的数量。一个顶点v是表示程度的度(v)或度诉一个图G的最大程度,用Δ(G)和最低程度的一个图表,用δ(G),最大和最小程度的顶点。在右边的图中，最大值是5，最小值是0。在一个普通的图中，所有的度都是一样的，所以我们可以说这个是图的度。[[6]]

平均路径长度

平均路径长度是拓扑网络中的一个概念，定义为所有可能的网络节点对的最短路径上的平均步数。它是网络上信息或大众运输效率的一种度量。

直径

在几何学中，圆的直径是任何穿过圆中心、端点在圆上的直线段。它也可以定义为圆的最长弦。这两个定义对于球体的直径也是有效的。 在现代化的用法中，直径的长度也被称为直径。从这个意义上说，我们谈论的是直径（指距离）而不是直径(指的是直线本身)，因为一个圆或球体的所有直径都有相同的长度，这是半径r的两倍。 d = 2r⇒r = d / 2。 对于平面上的凸形，其直径定义为两条相切于其边界的平行线之间可以形成的最大距离，而宽度通常定义为这种距离的最小值。这两个量都可以用旋转卡尺有效地计算出来。对于一个等宽的曲线，例如鲁洛三角形，其宽度和直径是相同的，因为所有的平行切线的长度相同。 而对于椭圆，标准术语是不同的。椭圆的直径是任何穿过椭圆中心的弦。例如，共轭直径具有这样的性质:其中一个端点与椭圆的切线平行于另一个端点。最长的直径称为长轴。 “直径”一词来源于希腊διάμετρος(diametros)、“一圈直径”,从διά(dia)”,通过“和μέτρον(密特隆),“衡量”。[3]通常缩写DIA,dia,d,或⌀。

集聚系数

在图论中，聚类系数是图中节点聚类的程度的度量。有证据表明，在大多数真实世界的网络中，特别是在社交网络中，节点往往以相对高密度的联系为特征，形成紧密的群体;这种可能性往往大于两个节点之间随机建立平局的平均概率(霍兰德和莱因哈特，于1971年; 瓦茨和斯托盖茨，于1998年)。 这种方法有两种版本:全局和局部。全局版本的设计是为了给出网络中集群的总体指示，而局部版本则表示单个节点的嵌入性。

相关性

关联性是指一个主题与另一个主题之间的联系，在考虑第一个主题时考虑第二个主题是有作用的。关联的概念被研究在许多不同的领域，包括认知科学，逻辑，图图书馆信息科学。然而，最根本的是，它属于认识学（也称认识论）的研究范围。不同的知识理论对被认为相关的东西有不同的含义，这些基本观点对所有其他领域也都有影响。

模块性

从广义上讲，模块化是指系统的组件可以分离和重组的程度，通常具有灵活性和多样化的使用优势。模块化的概念主要用于通过将系统分解为不同程度的相互依赖和独立性来降低复杂性，并“将每个部分的复杂性隐藏在抽象和接口之后”。然而，模块化的概念可以扩展到多个学科，每个学科都有自己的概念上的细微差别。尽管有这些细微的差别，关于模块化系统的一致主题还是出现了。

节点中心性

在图论和网络分析中，中心性指标确定图中最重要的顶点。应用程序包括识别社交网络中最有影响力的人、互联网或城市网络中的关键基础设施节点和疾病的超级传播者。中心性概念最早出现在社会网络分析中，许多衡量中心性的术语反映了它们的社会学渊源。它们不应该与节点影响度量相混淆，节点影响度量试图量化网络中每个节点的影响。[[7]]

实证数据

实证数据，也被称为感觉经验，是通过感觉获得的信息，特别是通过观察和记录通过实验的模式和行为。该词来自希腊语的经验,ἐμπειρία(empeiria)。 在康德·伊曼努尔之后，哲学中通常把获得的知识称为后验知识(与先验知识相反)。

统计特征

可观测性

统计量是一种可观察的随机变量，它不同于描述统计总体特性的一般不可观察量的参数，也不同于不可观察的随机变量，例如观察到的测量值和总体平均值之间的差值。如果整个总体可以观察到没有误差，一个参数只能精确地计算；例如，在一个完美的人口普查或标准化考试的考生群体中。 统计学家经常考虑一个参数化的概率分概率分布布族参数族，其中的任何成员都可能是人口中每个成员的某种可测量方面的分布，从中随机抽取一个样本。例如，这个参数可能是北美25岁男性的平均身高。测量了100个这样的人的样本的身高;这100个数字的平均值是一个统计数据。人口中所有成员的平均身高不是一个统计数据，除非这个数据也以某种方式被确定(例如通过测量人口中的每一个成员)。所有25岁北美男性的平均身高是一个参数，而不是一个统计数据。

统计特性

统计的重要潜在特性包括完整性、一致性、充分性、无偏性、最小均方误差、低方差、稳健性和计算便利性。

信息的统计

模型参数的统计信息可以用几种方法定义。最常见的是费雪信息，它是在由统计量引起的统计模型上定义的。也可以使用库尔贝克信息度量。

无标度

一个网络的度分布被称为无标度，即一个均匀随机选择的节点有一定数量链路度的概率，遵循一个被称为幂律的特殊数学函数。幂律表明，这些网络的度分布没有特征尺寸。相比之下，具有单一的、规模定义明确的网络在某种程度上类似于网格，因为每个节点（大致）都在同一个程度。单一的规模网络的例子，包括Erdős-Renyi(ER)随机图像和超立方体。产生尺度不变的度分布的网络模型有巴拉巴西-艾伯特模型和适应度模型。在一个具有无标度度分布的网络里，一些顶点有大于平均梯度的阶的等级——这些顶点通常被称为枢纽，尽管这有点误导因为它没有固定的阈值，一个节点可以被视为一个枢纽。如果有这样的阈值，网络就不会是无标度。 人们对无标度网络的兴趣起始于1990年代末的关于幂律度分布在真实世界的网络如万维网、自制系统网络（ASs)，一些互联网路由器网络、蛋白质相互作用网络、电子邮件网络等的发现报告。大部分在报告幂律时，在挑战严格的统计测试时，都失败了，但是，对于重尾度分布的较普遍看法——许多这样的网络确实表现出这种分布（在有限尺寸影响发生之前）——与人们所预期的边缘独立存在且随机存在（即假设它们遵循泊松分布）。建立一个幂律度分布的网络有很多种不同的方法。尤尔过程[8]是幂律的典型生成过程，自1925年以来就为人所知。然而，由于其频繁的再创造，它的许多其他名字被人们所熟知，例如，西蒙·亚历山大·赫伯特的直布陀罗原则、马太效应、累积优势，以及i巴拉巴西和艾伯特的幂律度分布的优先链接。近期，双曲几何图形被认为是另一种构建无标度网络的方法。 一些具有幂律度分布的网络（以及特定的其他类型的结构）可以高度抵抗垂直的随机删除——即绝大多数顶点仍然与一个巨大的指数连接在一起。这样的网络对旨在快速破坏网络的攻击也异常敏感。当图像是除度分布外均匀随机的时候，这些关键的顶点是最高阶的，因此在社会和通信网络涉及疾病和病毒的传播（自然和人工），以及时尚的传播（这两种都是由渗流或分支流程建模的）。而随即图像（ER)节点间的平均距离为o(log N),其中N为节点数，无标度图像的距离为log log N。这种图像被称为超小世界网络。

小世界

这个小世界实验由米尔格拉姆·斯坦利和其他研究人员进行的几个实验组成，他们研究了美国人社交网络的平均路径长度。该研究具有开创性，它表明人类社会是一个以短路径长度为特征的小世界网络。这些实验经常与“六度分离”联系在一起，尽管米尔格拉姆本人并没有使用这个术语。

Rich Club系数

Rich-club系数是图形和网络的度量标准，旨在衡量连接良好的节点之间相互连接的程度。具有较高Rich-club系数的网络具有较强的Rich-club效应，且节点间的连接程度较高。这种效应已经在科学协作网络和航空运输网络中得到了测量和注意。蛋白质相互作用网络明显缺乏Rich-club系数。

社团划分

在社交网络中，用户相当于每一个点，用户之间通过互相的关注关系构成了整个网络的结构，有的用户之间的连接较为紧密，有的用户之间的连接关系较为稀疏，反映在网络中，连接较为紧密的部分可以被看成一个社团，其内部的节点之间有较为紧密的连接，而在两个社团间则相对连接较为稀疏。社团划分就是划分出上述的社团。

基本模型

BA模型

艾伯特-巴拉巴西（BA）模型是一种使用优先连接机制生成随机无标度网络的算法。一些自然的和人为的系统，包括因特网、万维网、引文网络和一些社交网络，被认为是近似无尺度的，并且肯定包含很少的节点(称为集线器)，与网络的其他节点相比具有异常高的程度。BA模型试图解释真实网络中存在这样的节点。该算法以发明者艾伯特·拉斯洛·巴拉巴西和艾伯特·瑞卡的名字命名，它是一种更通用的模型的特例，称为普利斯模型。

双曲几何模型

有很多不同的伪球面在很大范围内都有一个恒定的负高斯曲率，其中伪球面是最著名的。 但是在其他模型上做双曲几何比较容易。 [[9]] [[10]] 双曲几何常用的模型有四种：克莱恩模型、庞加莱圆盘模型、庞加莱半平面模型和洛伦茨或双曲面模型。这些模型定义了满足双曲几何公理的双曲平面。尽管它们的名字，上面提到的前三个模型是由贝尔特拉米作为双曲空间模型引入的，而不是由庞加莱或克莱恩提出的。所有这些模型都可以扩展到更多的维度。

参考文献

1.

相关wiki

Complex network英文版wiki百科