复杂网络

来自集智百科
跳转到: 导航搜索

复杂网络是一种理解现实世界复杂系统的抽象模型。它将复杂系统中的实体抽象成点,而将实体之间的关系抽象成连线。虽然数学中的图论也在研究网络,但是,现实中的复杂网络会更多地展现出随机特性。因此,复杂网络一般更加关注网络的统计特征

目录

复杂网络研究简史

欧拉与格尼斯堡七桥问题

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

ER随机网

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

小世界网络

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

无标度网络

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

网络科学

网络科学是研究电信网络[33]、计算机网络[34]、生物网络[35]、认知语义网络[36]、社交网络[37]等复杂网络[38]的学术领域。该领域考虑节点(或顶点)所代表的不同元素或参与者,以及元素或参与者之间为链接(或边)的连接。该领域采用的理论和方法包括数学的图论[39]、物理的统计力学[40]、计算机科学的数据挖掘[41]和信息可视化[42]、统计学的推理建模[43]和社会学的社会结构[44]。美国国家研究委员https://en.wikipedia.org/wiki/National_Academies_of_Sciences,_Engineering,_and_Medicine美国国家研究委员会] 会将网络科学定义为“研究物理、生物和社会现象的网络表征,从而得出这些现象的预测模型”。

表示与分类

邻接矩阵

在图论[45]和计算机科学[46]中,邻接矩阵是用于表示有限图[47]的方阵[48]。矩阵的元素表明图中顶点对是否相邻。在有限简图[49]的特殊情况下,邻接矩阵是一个(0,1)对角线[50]上为0的矩阵。如果图是无向的,则邻接矩阵实对称的[51]。谱图理论[52]研究了图与其邻接矩阵的特征值[53]和特征向量[54]之间的关系。邻接矩阵应与图的关联矩阵[55]分开,邻接矩阵是一种不同的矩阵表示,其元素表示顶点——对边是否有关联,度矩阵[56]包含了每个顶点[57]的度[58]的信息。

链表表示

网络分类

有向网

加权网

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

流网络

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

空间网

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

二分网

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

统计指标

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

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

平均路径长度

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

直径

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

集聚系数

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

相关性

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

模块性

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

节点中心性

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

实证数据

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

统计特征

可观测性

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

统计特性

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

信息的统计

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

无标度

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

小世界

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

Rich Club系数

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

社区划分

基本模型

SW模型

BA模型

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

双曲几何模型

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

网络上的动力学

网络的动力学

个人工具
名字空间
操作
导航
工具箱