更改

复杂网络 (查看源代码)

2021年11月23日 (二) 21:13的版本

删除22字节、 2021年11月23日 (二) 21:13

无编辑摘要

第8行：第8行：

==定义==

大多数社会、生物和技术网络显示了大量非平凡的拓扑特征，它们的元素之间的连接模式既不是纯规则的也不是纯随机的。这些特征包括程度分布的重尾，高集聚系数，顶点之间的协调性或不协调性，社团结构和等级结构。在有向网络的情况下，这些特征还包括互惠性、三元显著性特征和其他特征。相比之下，许多过去研究过的网络数学模型，例如格和随机图，并没有表现出这些特征。最复杂的结构可以通过具有中等数量相互作用的网络来实现。<ref>{{cite journal|last=T. Wilhelm|first=J. Kim|title=What is a complex graph?|journal=Physica A|year=2008|volume=387|issue=11|pages=2637–2652|doi=10.1016/j.physa.2008.01.015|bibcode = 2008PhyA..387.2637K }}</ref>即对于中等概率而言，最大信息量(熵)是可获得的。

−

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

−

而[[无标度网络]]<ref name = "frst">{{cite journal|last=A. Barabasi|first=E. Bonabeau|title=Scale-Free Networks|journal=Scientific American|date= 2003|volume=288|issue=5|pages=50–59|doi=10.1038/scientificamerican0503-60|pmid=12701331|bibcode=2003SciAm.288e..60B}}</ref>和[[小世界网络]]<ref name = "sec">{{cite journal|last=S. H. Strogatz|first=D. J. Watts|title=Collective dynamics of 'small-world' networks|journal=Nature|year=1998|volume=393|pages=440–442|doi=10.1038/30918|pmid=9623998|issue=6684|bibcode = 1998Natur.393..440W}}</ref><ref>{{cite journal|last=H.E. Stanley|first=L.A.N. Amaral, A. Scala, M. Barthelemy|title=Classes of small-world networks|journal=PNAS|year=2000|volume=97|issue=21|pages=11149–52|doi= 10.1073/pnas.200327197 |arxiv = cond-mat/0001458 |bibcode = 2000PNAS...9711149A|pmid=11005838|pmc=17168|doi-access=free}}</ref>是复杂网络研究的热点，它们的发现和定义是该领域的典型案例。两者都拥有着各自独有的结构特征。即无标度网络的幂律度分布和小世界网络的短路径长度和高聚集性。然而，随着复杂网络研究的重要性和普及程度的不断提高，网络结构的许多其他方面也引起了人们的关注。

−

近年来，复杂网络的研究已经扩展到多层网络。<ref name="BuldyrevParshani2010">{{cite journal|last1=Buldyrev|first1=Sergey V.|last2=Parshani|first2=Roni|last3=Paul|first3=Gerald|last4=Stanley|first4=H. Eugene|last5=Havlin|first5=Shlomo|title=Catastrophic cascade of failures in interdependent networks|journal=Nature|volume=464|issue=7291|year=2010|pages=1025–1028|issn=0028-0836|doi=10.1038/nature08932|pmid=20393559|arxiv = 0907.1182 |bibcode = 2010Natur.464.1025B}}</ref>如果这些网络是相互依存的，它们比单一网络更容易受到随机故障和有针对性的攻击，并出现级联故障和一级渗透过渡。<ref name="ParshaniBuldyrev2010">{{cite journal|last1=Parshani|first1=Roni|last2=Buldyrev|first2=Sergey V.|last3=Havlin|first3=Shlomo|title=Interdependent Networks: Reducing the Coupling Strength Leads to a Change from a First to Second Order Percolation Transition|journal=Physical Review Letters|volume=105|issue=4|year=2010|issn=0031-9007|doi=10.1103/PhysRevLett.105.048701|bibcode=2010PhRvL.105d8701P|arxiv = 1004.3989|pmid=20867893|pages=048701}}</ref><ref>{{cite journal | title = Networks formed from interdependent networks | authors = J. Gao, S.V. Buldyrev, H.E. Stanley, S. Havlin | journal = Nature Physics | volume = 8 | pages = 40–48 | date = 2012| issue = 1 | doi = 10.1038/nphys2180 | bibcode = 2012NatPh...8...40G }}</ref>此外，还研究了节点失效和恢复情况下网络的集体行为。<ref name="MajdandzicPodobnik2013">{{cite journal|last1=Majdandzic|first1=Antonio|last2=Podobnik|first2=Boris|last3=Buldyrev|first3=Sergey V.|last4=Kenett|first4=Dror Y.|last5=Havlin|first5=Shlomo|last6=Eugene Stanley|first6=H.|title=Spontaneous recovery in dynamical networks|journal=Nature Physics|volume=10|issue=1|year=2013|pages=34–38|issn=1745-2473|doi=10.1038/nphys2819|bibcode=2014NatPh..10...34M|doi-access=free}}</ref>人们已经发现，这样的网络可能会出现自发的失败和自发的恢复。

−

第36行：第32行：

2.不经过另一端而经过桥（但，这是绝对不可能的）

欧拉证明了这个问题没有解决方案。他所面临的困难是开发出一种合适的分析技术，以及后面的测试，这些测试需要用精确的数学方法证明这一论断。

+

===ER随机网===

第51行：第48行： +

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

−

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

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

第60行：第57行：

===网络科学===

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

+

==表示与分类==

−

===邻接矩阵===

在[https://en.wikipedia.org/wiki/Graph_theory 图论]和[https://en.wikipedia.org/wiki/Computer_science 计算机科学]中，邻接矩阵是用于表示[https://en.wikipedia.org/wiki/Graph_(discrete_mathematics) 有限图]的[https://en.wikipedia.org/wiki/Square_matrix 方阵]。矩阵的元素表明图中顶点对是否相邻。在有限[https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)#Simple_graph 简图]的特殊情况下，邻接矩阵是一个（0，1）对角线[https://en.wikipedia.org/wiki/Logical_matrix 逻辑矩阵]上为0的矩阵。如果图是无向的，则邻接矩阵实对称的[https://en.wikipedia.org/wiki/Symmetric_matrix 对称图像]。[https://en.wikipedia.org/wiki/Spectral_graph_theory 谱图理论]研究了图与其邻接矩阵的[https://en.wikipedia.org/wiki/Eigenvalues_and_eigenvectors 特征值]和[https://en.wikipedia.org/wiki/Eigenvalues_and_eigenvectors 特征向量]之间的关系。邻接矩阵应与图的[https://en.wikipedia.org/wiki/Incidence_matrix 关联矩阵]分开，邻接矩阵是一种不同的矩阵表示，其元素表示顶点——对边是否有关联，[https://en.wikipedia.org/wiki/Degree_matrix 度矩阵]包含了每个[https://en.wikipedia.org/wiki/Vertex_(graph_theory) 顶点（图论）]的[https://en.wikipedia.org/wiki/Degree_(graph_theory) 度（图论）]的信息。

+

=== 链表表示 ===

链表实际上是线性表的链式存储结构，与数组不同的是，它是用一组任意的存储单元来存储线性表中的数据，存储单元不一定是连续的，且链表的长度不是固定的，链表数据的这一特点使其可以非常的方便地实现节点的插入和删除操作

+

链表的每个元素称为一个节点，每个节点都可以存储在内存中的不同的位置，为了表示每个元素与后继元素的逻辑关系，以便构成“一个节点链着一个节点”的链式存储结构，除了存储元素本身的信息外，还要存储其直接后继信息，因此，每个节点都包含两个部分，第一部分称为链表的数据区域，用于存储元素本身的数据信息，它不局限于一个成员数据，也可是多个成员数据，第二部分是一个结构体指针，称为链表的指针域，用于存储其直接后继的节点信息。

+

===网络分类===

−

====有向网====

任一点对（i,j）和（j,i）对应同一条边,则为无向网,反之成为有向网。

第101行：第100行：

最简单的方法涉及到双方的网络投射到一个未加权的网络，但不考虑网络的拓扑结构或共享一个连接的频率对立的元素集。由于在这种情况下，双方的网络很大程度上与不同的结构可以有完全相同的一种模式表示,一个清晰的插图的原始网络拓扑通常需要使用一些加权法。[[https://upload.wikimedia.org/wikipedia/commons/f/f9/Bipartite_network_projection.png]]

[[File:Bipartite_network_projection.png|200px|thumb]]

+

==统计指标==

第107行：第107行：

各项指标通常权重相等，除非有一些理由违反(例如，如果两个项本质上反映了变量的相同方面，那么它们的权重可能为0.5)。

构建项目涉及四个步骤。首先，项目的选择应该基于它们的面部效度、单维性、[https://en.wikipedia.org/wiki/Sensitivity_and_specificity 测量维度]的特异性程度以及它们的方差。项目之间应该有经验上的联系，这引向了检验它们的多元关系的第二步。第三，设计索引得分，这涉及到确定它们的得分范围和项目的权重。最后，需要对指标进行验证，这涉及到是否能够预测与构建中未使用的测量变量相关的指标。

+

===度===

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

[[File:UndirectedDegrees_(Loop).svg.png|200px|thumb]]

+

===平均路径长度===

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

+

===直径===

−

在几何学中，圆的直径是任何穿过圆中心、端点在圆上的直线段。它也可以定义为圆的最长弦。这两个定义对于[https://en.wikipedia.org/wiki/Sphere 球体]的直径也是有效的。

+

在几何学中，圆的直径是任何穿过圆中心、端点在圆上的直线段。它也可以定义为圆的最长弦。这两个定义对于球体的直径也是有效的。在现代化的用法中，直径的长度也被称为直径。从这个意义上说，我们谈论的是直径（指距离）而不是直径(指的是直线本身)，因为一个圆或球体的所有直径都有相同的长度，这是半径r的两倍。

−

~~在现代化的用法中，直径的长度也被称为直径。从这个意义上说，我们谈论的是直径（指距离）而不是直径~~(指的是直线本身)，因为一个圆或球体的所有直径都有相同的长度，这是半径r的两倍。

+

d = 2r⇒r = d / 2。

+

对于平面上的[https://en.wikipedia.org/wiki/Convex_set 凸形]，其直径定义为两条相切于其边界的平行线之间可以形成的最大距离，而宽度通常定义为这种距离的最小值。这两个量都可以用[https://en.wikipedia.org/wiki/Rotating_caliper 旋转卡尺]有效地计算出来。对于一个[https://en.wikipedia.org/wiki/Curve_of_constant_width 等宽的曲线]，例如[https://en.wikipedia.org/wiki/Reuleaux_triangle 鲁洛三角形]，其宽度和直径是相同的，因为所有的平行切线的长度相同。

+

而对于椭圆，标准术语是不同的。椭圆的直径是任何穿过椭圆中心的弦。例如，共轭直径有这样的性质:其中一个端点与椭圆的切线平行于另一个端点。最长的直径称为长轴。

+

“直径”一词来源于希腊διάμετρος(diametros)、“一圈直径”,从διά(dia)”,通过“和μέτρον(密特隆),“衡量”通常缩写DIA,dia,d,或⌀。

第126行：第132行：

在[[图论]]中，聚类系数是图中节点聚类的程度的度量。有证据表明，在大多数真实世界的网络中，特别是在[[社交网络]]中，节点往往以相对高密度的联系为特征，形成紧密的群体;这种可能性往往大于两个节点之间随机建立平局的平均概率(霍兰德和莱因哈特，于1971年; 瓦茨和斯托盖茨，于1998年)。

这种方法有两种版本:全局和局部。全局版本的设计是为了给出网络中集群的总体指示，而局部版本则表示单个节点的嵌入性。

+

===相关性===

第132行：第139行：

===模块性===

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

+

===节点中心性===

第142行：第150行：

实证数据，也被称为感觉经验，是通过[https://en.wikipedia.org/wiki/Sense 感觉]获得的[https://en.wikipedia.org/wiki/Information 信息]，特别是通过[https://en.wikipedia.org/wiki/Observation 观察]和记录通过[https://en.wikipedia.org/wiki/Experiment 实验]的模式和行为。该词来自[https://en.wikipedia.org/wiki/Ancient_Greek 希腊]语的经验,ἐμπειρία(empeiria)。

在[https://en.wikipedia.org/wiki/Immanuel_Kant 康德·伊曼努尔]之后，哲学中通常把获得的知识称为[https://en.wikipedia.org/wiki/A_priori_and_a_posteriori 后验知识](与[https://en.wikipedia.org/wiki/A_priori_and_a_posteriori 先验]知识相反)。

+

==统计特征==

第148行：第157行：

统计量是一种可观察的[https://en.wikipedia.org/wiki/Random_variable 随机变量]，它不同于描述[https://en.wikipedia.org/wiki/Statistical_population 统计总体]特性的一般不可观察量的[https://en.wikipedia.org/wiki/Statistical_parameter 参数]，也不同于不可观察的随机变量，例如观察到的测量值和总体平均值之间的差值。如果整个总体可以观察到没有误差，一个参数只能精确地计算；例如，在一个完美的人口普查或[https://en.wikipedia.org/wiki/Standardized_test 标准化考试]的考生群体中。

统计学家经常考虑一个参数化的概率分[https://en.wikipedia.org/wiki/Probability_distribution 概率分布]布族[https://en.wikipedia.org/wiki/Parametric_family 参数族]，其中的任何成员都可能是人口中每个成员的某种可测量方面的分布，从中随机抽取一个样本。例如，这个参数可能是北美25岁男性的平均身高。测量了100个这样的人的样本的身高;这100个数字的平均值是一个统计数据。人口中所有成员的平均身高不是一个统计数据，除非这个数据也以某种方式被确定(例如通过测量人口中的每一个成员)。所有25岁北美男性的平均身高是一个参数，而不是一个统计数据。

+

===统计特性===

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

+

===信息的统计===

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

+

===无标度===

第164行：第176行：

===小世界===

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

+

===Rich Club系数===

Rich-club系数是[https://en.wikipedia.org/wiki/Graph_(discrete_mathematics) 图形]和[https://en.wikipedia.org/wiki/Complex_network 网络]的度量标准，旨在衡量连接良好的节点之间相互连接的程度。具有较高Rich-club系数的网络具有较强的Rich-club效应，且节点间的连接程度较高。这种效应已经在科学协作网络和航空运输网络中得到了测量和注意。[https://en.wikipedia.org/wiki/Biological_network#Protein-protein_interaction_networks 蛋白质相互作用网络]明显缺乏Rich-club系数。

+

===社团划分===

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

+

==基本模型==

−

===BA模型===

艾伯特-巴拉巴西（BA）模型是一种使用[https://en.wikipedia.org/wiki/Preferential_attachment 优先连接]机制生成随机[https://en.wikipedia.org/wiki/Scale-free_network 无标度网络]的算法。一些自然的和人为的系统，包括[https://en.wikipedia.org/wiki/Internet 因特网]、[https://en.wikipedia.org/wiki/World_Wide_Web 万维网]、[https://en.wikipedia.org/wiki/Citation_analysis 引文网络]和一些[https://en.wikipedia.org/wiki/Social_network 社交网络]，被认为是近似无尺度的，并且肯定包含很少的节点(称为集线器)，与网络的其他节点相比具有异常高的程度。BA模型试图解释真实网络中存在这样的节点。该算法以发明者[https://en.wikipedia.org/wiki/Albert-László_Barabási 艾伯特·拉斯洛·巴拉巴西]和[https://en.wikipedia.org/wiki/Réka_Albert 艾伯特·瑞卡]的名字命名，它是一种更通用的模型的特例，称为[https://en.wikipedia.org/wiki/Price%27s_model 普利斯模型]。

+

===双曲几何模型===

有很多不同的伪球面在很大范围内都有一个恒定的负高斯曲率，其中[https://en.wikipedia.org/wiki/Pseudosphere 伪球面]是最著名的。

第181行：第197行：

[[https://upload.wikimedia.org/wikipedia/commons/thumb/a/ad/Hyperbolic_tiling_omnitruncated_3-7.png/500px-Hyperbolic_tiling_omnitruncated_3-7.png]]

双曲几何常用的[https://en.wikipedia.org/wiki/Mathematical_model 模型]有四种：[https://en.wikipedia.org/wiki/Klein_model 克莱恩模型]、[https://en.wikipedia.org/wiki/Poincaré_disk_model 庞加莱圆盘模型]、[https://en.wikipedia.org/wiki/Poincaré_half-plane_model 庞加莱半平面模型]和洛伦茨或[https://en.wikipedia.org/wiki/Hyperboloid_model 双曲面模型]。这些模型定义了满足双曲几何公理的双曲平面。尽管它们的名字，上面提到的前三个模型是由[https://en.wikipedia.org/wiki/Eugenio_Beltrami 贝尔特拉米]作为双曲空间模型引入的，而不是由[https://en.wikipedia.org/wiki/Henri_Poincaré 庞加莱]或[https://en.wikipedia.org/wiki/Felix_Klein 克莱恩]提出的。所有这些模型都可以扩展到更多的维度。

+

==参考文献==

薄荷

7,129

个编辑