哪些看似与图论无关的问题可用图论模型解决？ 第1页

简介：20世纪90年代中期开始使用功能磁共振成像（functional magnetic resonance imaging, fMRI）对人脑连接体进行分析，并且在发现人类认知和神经系统疾病的神经基础方面引起了越来越多的关注。基于图论的计算方法在理解大脑连通性结构中发挥了重要作用。 由于图论分析的出现，基于图论的复杂网络定量分析的最新进展已迅速转化为大脑网络组织的研究。大脑的结构和功能系统具有复杂的网络功能，例如小世界拓扑，高度连接的中心和模块性，无论是在人类神经成像的全脑范围内，还是在非人类动物的细胞范围内。本文回顾了研究复杂的大脑网络的各种实验方法，包括人类的结构和功能MRI，扩散张量成像的研究，并对图论的基本原理进行了介绍。最后，对图论在神经和精神疾病中的大脑网络中的应用做一个简单的介绍。

1引言

人脑由860亿个神经元组成、通过150万亿突触连接，允许神经元向其他神经元传输电信号或化学信号。随着神经科学家寻求理解认知、行为和感知背后的综合信息，将人脑建模为复杂系统的研究显著增长。自19世纪以来，我们就知道大脑的神经元构成了一个非常复杂的结构网络。自20世纪以来，人们还广泛地认识到，这种解剖学基质支持相干生理活动的动态出现，例如锁相高频电磁振荡，它可以跨越构成功能网络的多个空间不同的大脑区域。 这样的网络被认为为信息处理和心理表征提供了生理基础。 在本文中，我们将重点放在图理论方法上，以分析复杂网络，这些方法可以提供一种量化大脑的结构和功能系统的强大新方法。

基于图的网络分析揭示了关于人脑网络拓扑结构的有意义的信息，例如小世界、模块化组织和高度连接或集中的中枢。小世界是一些网络的特性，在这些网络中，大多数节点不是彼此的邻居，但是可以通过少数步骤从每个其他节点到达。这一特性非常适合研究复杂的大脑动力学，它证实了在低能量和低布线成本的人脑网络中有效的信息分离和整合。最近的研究表明，大脑网络的小世界性质在不同的认知负荷和发展过程中经历拓扑变化，就像在神经和精神障碍中那样。这些变化可能为人类认知的生物学机制以及健康和疾病提供新的见解。

神经影像学的最新进展使得人类连接体在不同应用中的定位成为可能。基于影像的脑网络构主要分为结构脑网络和功能脑网络。结构脑网络通常以脑区作为节点，以纤维数量、纤维长度、连接概率、各项分数异性等作为边。连接强度可以使用扩散张量成像(diffusion tensor imaging, DTI)进行白质纤维素追踪。脑白质的纤维追踪技术主要有确定性追踪和概率性追踪两种：确定性追踪是将每个体素中的纤维段按照一定的规则连起来形成连接不同脑区的通路。概率性追踪假设每一个体素的纤维方向并不唯一确定，而是满足一定的概率密度分布。 脑功能网络以脑区为节点，以活动中时间相关性的大小作为边。大脑功能可以通过神经成像技术进行定位，该技术通过正电子发射断层扫描(positron emission tomography, PET)评估新陈代谢的变化，或者通过功能磁共振成像评估血氧水平依赖(blood oxygenation level-dependent, BOLD)反应的变化。在过去的二十年里，激增的fMRI研究在静息态或任务执行期间将神经功能映射到大脑的不同部分，然而更多的注意力集中在静息态功能磁共振成像(resting-state fMRI, rs-fMRI)数据上。图论在fMRI中的具体研究问题主要有：

1.使用功能磁共振成像模拟大脑连接模式的计算方法是如何演变的？

2.如何对使用功能磁共振成像绘制人类连接体的研究进行分类？

3.在已确定的大脑连通性分析工具包中，基于图的方法有什么意义？

4.随着认知领域图论的出现神经科学，在模拟人类认知和精神疾病方面研究了哪些应用？

5.从当前基于图的人类连接体研究中可以学到什么，这将导致进一步研究的主题？

2 图论:将大脑作为一个大型复杂网络的分析

图论和网络分析的第一次应用可以追溯到1736年，当时Leonhard Euler解决了Königsberg Bridge问题。就这一点而言，一个图由一组有限的顶点(或节点)组成，这些顶点通过称为边(或弧)连接在一起。随着电路和化学结构在其早期应用中出现有希望的结果，图论现在在解决其他学科中的大量实际问题方面变得有影响力，例如运输系统、社交网络、大数据环境、物联网、电力基础设施和生物神经网络。

2.1 大脑网络的构建

使用图论的复杂脑网络研究的转折点可以追溯到“人类连接体”的引入。在图论中，元素为零或非零的N×N邻接矩阵(也称为连接矩阵)表示具有N个节点的网络的顶点之间不存在或存在关系。通过从该矩阵中提取不同的指标，可以获得所需图(例如，人脑网络)的拓扑分析。基于顶点之间的链接是否携带方向信息(例如，因果交互)，脑图可以被分类为有向或无向。到目前为止，由于定向网络推理的技术限制，大多数人脑研究都致力于无向网络。根据顶点之间的链接是否可以取不同的值，脑图也可以分为加权的或二进制的。大尺度大脑网络中的节点通常代表大脑区域，而连接则代表解剖，功能或有效连接。解剖连接通常对应于成对的大脑区域之间的白质束。功能连接对应于活动中时间相关性的大小。根据测量，功能连接性可能反映线性或非线性相互作用，以及不同时间尺度的相互作用。有效连接表示一个区域在另一个区域直接或间接因果关系，可以通过观察到的扰动来估计。

可以使用图论通过以下四个步骤来探索结构和功能的大脑网络：

（1）定义网络节点。这些可以定义为脑电图或多电极阵列电极，或组织学，MRI或扩散张量成像数据的解剖学定义区域。

（2）估计节点之间关联的连续度量。这可能是两个脑磁图传感器之间的频谱相干性或Granger因果关系度量，或者是单个扩散张量成像数据集的两个区域之间的连接概率，或者是在受试者组中估计的皮质厚度或体积MRI测量中的区域间相关性。

（3）通过编译节点之间的所有成对关联来生成关联矩阵，并且（通常）将阈值应用于此矩阵的每个元素，以生成二进制邻接矩阵或无向图。

（4）在此大脑网络图形模型中计算感兴趣的网络参数，并将其与随机网络总体的等效参数进行比较。

图论分析中从fMRI中提取复杂网络的主要步骤。最初，对采集的功能磁共振成像数据进行许多预处理步骤，包括切片之间的时间校正、重新对准、图像配准、基于分割的归一化和空间平滑。需要注意的是预处理步骤的选择和顺序可能会影响最终图指标测量的范围。然后，为了探索大规模的大脑网络，应用了适当的分割方案，例如解剖学自动标记图谱，将整个大脑划分为几个皮质和皮质下的解剖单元。然后通过平均该特定区域内的所有体素的时间进程平均作为该脑区的时间序列。接下来，执行在前面部分中回顾的连通性方法之一，诸如相关分析，以确定大脑不同脑区间的时间序列的成对关联。然后通过对相关矩阵的值进行阈值处理来获得二进制连通性矩阵(即邻接矩阵)。最后，可以使用大脑连接工具箱获得表征大脑网络连接的局部和整体架构的关键拓扑属性。

2.2 节点的性质

各个大脑网络中节点和链接的性质是由大脑映射方法，解剖分割方案和连通性度量的组合确定的。许多组合发生在各种实验设置中。给定组合的选择必须谨慎地进行，因为节点和链接的性质在很大程度上决定了网络拓扑的神经生物学解释。

理想情况下，节点应该代表具有外部解剖或功能连接的连贯模式的大脑区域。将不同连接的大脑区域合并成单个节点的划分方案可能意义不大。此外，分割方案应完全覆盖皮层或整个大脑的表面，并且各个节点在空间上不应重叠。考虑到传感器可能检测到空间上重叠的信号并且通常不与相干区域的边界对齐，因此在这方面使用MEG和EEG传感器可能会出现问题。 使用不同的分割方案构建的网络的性质可能存在显着差异，并且通常无法进行定量比较。具体而言，只有结构和功能网络共享相同的分割方案，才可以对它们进行有意义的比较。

2.3 连接的性质

除了连通性的类型（解剖学，功能或有效连接）和特定于度量的（例如时间标度）连通性特征外，连接还根据其权重和方向性进行区分。二进制链接表示存在或不存在连接，而加权链接还包含有关连接强度的信息。解剖网络中的权重可以代表解剖区域的大小，密度或连贯性，而功能网络和有效网络中的权重代表各自的相关或因果交互的大小。最近的许多研究都放弃了连接权重，因为二值网络在大多数情况下更易于表征，并且具有更容易定义的用于统计比较的空模型。另一方面，加权表征通常侧重于网络组织的某些不同和互补的方面，并且在过滤弱的和潜在不重要的链接的影响方面可能特别有用。弱链接和非重要链接可能表示虚假连接，尤其是在功能或有效的网络中。这些联系往往掩盖了强连接和重要连接的拓扑，因此经常通过施加绝对或比例权重阈值而将其丢弃。阈值通常是任意确定的，理想情况下应该通过广泛的阈值来描述网络。独立地，所有自连接或负连接(如功能性反连接)必须在分析之前从网络中移除。未来的网络方法可能能够量化负权重在全球网络组织中的作用。

连接也可以通过方向性的存在与否来区分。因此，解剖学和有效的连接可以在概念上用有向连接表示。不幸的是，当前的神经成像方法不能直接检测解剖学或因果的方向性。另一方面，由目标追踪研究构建的定向解剖网络表明，皮质中存在大量的交互连接，这为非定向解剖网络的使用提供了一定的有效性。有效连接的定向模式可以从伴随局部扰动的功能活动变化中推断出来。

图论在神经科学研究中的主要能力通常是在构建了一个功能性的大脑网络之后才显现出来的。可以使用几个指标来评估不同网络的拓扑模式，例如：聚类系数、模块化、平均路径、小世界性、分类性和节点中心性。一般来说，人们不能说哪些测量方法更适合研究大脑网络，但鉴于人脑的复杂结构，能够代表大脑网络小世界特性的测量方法非常重要。这一关键特性是在中枢(即网络中高度连接的节点)的帮助下产生的，导致了局部聚类方法的出现。

2.4图指标的计算

最常用的表征功能性脑网络的图指标分为两大类：整体属性和局部属性。这些标准大多适用于任何类型的二进制、加权和定向网络。

Ø 节点度，度分布和分类性

节点度是将其链接到网络其余部分的连接数，这是最基本的网络度量，大多数其他度量最终都与节点度相关联。网络所有节点度形成度分布。在随机网络中，所有连接都是同等可能的，从而导致高斯分布和对称中心分布。复杂的网络通常具有非高斯度分布，通常具有高度具有长尾。无标度网络的度分布遵循幂律。分类性是连接节点的度之间的相关性。正的分类性表示高度节点倾向于相互连接。

Ø 聚类系数和模体

如果节点的最近邻居也直接相互连接，则它们会形成一个类。聚类系数将一个节点的最近邻居之间存在的连接数量除以最大可能连接数量。随机网络的平均聚类较低，而复杂的网络则具有较高的聚类（与较高的本地信息传递效率和鲁棒性相关）。相邻节点之间的相互作用 也可以通过计算互连节点小模体的出现来量化。网络中不同模体类别的分布提供了有关网络可以支持的本地交互类型的信息。

Ø 路径长度和效率

路径长度是从一个节点到另一个节点必须经过的最小边数。随机和复杂的网络平均路径长度较短（并行信息传输的整体效率很高），而规则网格的平均路径长度较长。效率与路径长度成反比，但在数值上更容易用于估计不连续图的元素之间的拓扑距离。

Ø 连接密度或成本

连接密度是图形中实际的边数占可能边总数的比例，并且是对网络物理成本（例如，能源或其他资源需求）的最简单估算。

Ø 中心性和鲁棒性

中心性是具有高度或高度集中性的节点。节点的中心性衡量网络中所有其他节点对之间的最短路径中有多少条经过该路径。因此，具有高度中心性的节点对于有效通信至关重要。可以通过删除单个节点并评估“受损”网络的效率来评估单个节点对网络效率的重要性。鲁棒性是指删除节点或边缘后网络的结构完整性，或者是指扰动对局部或全局网络状态的影响。

Ø 模块化

许多复杂的网络由许多模块组成。有多种算法可以估算网络的模块性，其中许多算法都是基于层次聚类。每个模块包含几个节点，节点之间的连接比较密集，不同模块节点之间的连接相对较少。因此，中心可以按照它们在这个社区结构中的角色来描述。次级中心主要连接到它们自己模块中的节点，而连接器中心连接到其他模块中的节点。

Ø 小世界属性

“小世界”属性最初是在社交网络中描述的，它结合了网络节点之间高水平的局部聚类(形成家庭或派系)和全局连接网络所有节点的短路径。这意味着大型系统的所有节点都通过相对较少的中间步骤进行链接，尽管事实上大多数节点仅维护少数几个直接连接-多数情况下是在邻居群体中。小世界组织介于随机网络和规则网络之间，随机网络的总路径长度较短，其局部聚类水平较低;规则网络的高聚类水平，其局部聚类水平较长。因此，通过将这两个指标的值与等效随机网络中的值进行比较，标准化后的聚类系数与路径长度之比是对小世界的一个方便的单数总结。小世界属性已经在遗传、信号、通信、计算和神经网络的广泛研究中报告。这些研究表明，在自然和技术系统中发现的几乎所有网络都具有非随机/非规则或小世界架构，这些网络偏离随机性的方式反映了它们的特定功能。

2.4.1全局属性

全局指标主要旨在揭示:(a)功能分离；(b)大脑网络内信息流的功能整合；(c)小世界属性和(d)网络抗故障能力。功能分离指的是网络元素形成专门社区的程度，而整合提供了对整体信息通信效率的洞察或组合分布式信息的能力。聚类系数和模块性是量化脑网络中拓扑隔离特性的最常见的指标(图2A)。在脑网络中，解剖上相邻或功能上相连的区域通常被认为是模块。各种研究表明，基于模块化结构的网络通常反映了小世界的属性。 另一方面，功能整合通常由量化全局信息整合能力的特征路径长度来衡量(图2B)。小世界属性显示了网络分离和整合之间的最佳平衡(图2C)。网络的同配性指数衡量了当网络中主要成分受到破坏时的网络弹性，这是网络科学中最重要的问题之一，它反映出网络抗干扰的能力(图2D)。

(A)聚类系数，量化给定节点的多少邻居是互连的，并测量局部群集(即，节点的邻居可以构建完整图的程度)；模块性，其与称为模块的节点集群相关，表示在群集内具有密集的互连性，但是在不同群集中的节点之间具有稀疏连接。一方面，某一模块内的密集通信增加了局部分块的能力，从而提高了该模块的信息传输效率。另一方面，不同模块之间的一些连接整合了全脑的信息流，这与图中的平均路径长度的减少相关联；

(B)整合指标包括特征路径长度，该指标测量信息传输的潜力，被确定为跨越所有节点对的平均最短路径长度。

(C)规则网络(左)表现出高的聚类系数和长的平均路径长度，而随机网络(右)表现出低的聚类系数和短的平均路径长度。小世界网络(中间)显示出了规则网络和随机网络之间的中间平衡(即，它们由许多短距离链路和几个长距离链路组成)，反映了高聚类系数和短路径长度。

(D)同配性指数衡量网络在其主要成分(即，其顶点和边)中能够抵抗故障的程度。值得注意的是，当特定中枢崩溃时，分类网络中的中枢之间的通信会覆盖彼此的活动，但是由于易受攻击的中枢的存在，非分类网络中的性能也将急剧下降。

2.4.2局部属性

在网络科学中，中枢是指具有高节点中心性的节点，因此会深刻影响网络拓扑。网络的枢纽节点根据各自定义的参与系数的高低分为两类:枢纽节点和局部中枢（provincial）节点。枢纽节点倾向于互连不同模块之间的节点，而局部中枢节点负责链接同一模块中的节点(图3A)。

检测网络中的中枢节点最简单的方法是计算节点度，即计算连接到每个节点的边。此外，绘制某个网络的度（degree）分布P(K)提供了关于该网络中是否存在枢纽的有价值的信息，例如，无标度网络中多个高度节点的存在伴随着幂律分布。此外，用于衡量节点中心性的其他常用指标包括：节点中介性、接近中心性、特征向量中心性、参与系数和PageRank（网络的一个算法）(图3B)。

(A)中枢是指具有高度节点中心性的节点，可以使用不同的衡量标准进行识别。

(B)度中心性定义为节点的邻居数。中介数中心性通过计算网络中包含给定节点的所有最短路径的比率来衡量节点在独立群集之间充当桥梁的角色。接近中心性量化了连通图中的给定节点访问所有其他节点的速度，因此节点越中心，它与所有其他节点的距离就越近。特征向量中心性是考虑节点连接的中心性的自参考度量，因此连接到中心节点会依次增加一个节点的中心性；红色节点比灰色节点更中心，尽管它们的度数相等。节点的参与系数表示其连接在不同模块之间的分布。

3 图论在神经和精神疾病中大脑网络的应用

由局部但相互联系的特殊区域组成的大脑连接的断开会导致功能障碍，与非典型的脑分布区域整合有关。Catani和Ffytche(2005)提出了大脑网络失连接带来的症状，并指出许多神经障碍可以通过这些综合征来解释，这与神经病学和精神病学先驱Meynert、Wernicke和Dejerine的研究一致。复杂大脑网络领域的研究已经证明，使用rs-fMRI分析网络属性和从大脑拓扑中获得的指标可以帮助神经学家区分精神障碍患者组和对照组。下面将讨论一些使用图论研究常见神经系统疾病的研究，包括：癫痫、阿尔茨海默病(AD)、自闭症谱系障碍(ASD)。然而，在近期的图论文献中也发现了其他精神障碍的特征，包括精神分裂症、帕金森病、失眠、重度抑郁症、强迫症(OCD)、边缘性人格障碍(BPD)和双相情感障碍等，但是这些疾病方面的图论研究贡献还较小。

3.1图论在癫痫中的应用

癫痫是一种慢性神经系统疾病，伴有大脑活动异常，导致反复发作和偶尔失去意识。颞叶癫痫(Temporal lobe epilepsy, TLE)是一种最常见的癫痫形式，伴有部分癫痫发作。在两项使用网络分析的有趣的rs-fMRI研究中，Vytvarova等人(2017)和Dong等人(2016)描述了基底神经节丘脑皮层回路对TLE中全脑功能连接的贡献。虽然检测和清除致痫性病变区域对于消除癫痫发作是必要的，但许多研究表明，癫痫发作源于致痫网络的异常，而不是病变;因此，40%的癫痫手术患者在5年内癫痫复发(Spencer, 2002)。因此，应用图论，结合临床放射学发现，有助于更好地理解局灶性癫痫(尤其是TLE)认知下降背后的网络机制，并提供有前景的诊断生物标志物。

Vlooswijk等人使用rs-fMRI检查了TLE患者的小世界属性。与健康受试者相比，他们发现癫痫患者的局部网络连接和全局连接都出现了中断。他们证实了癫痫患者的认知能力分数和脑网络信息处理表现之间的联系。其他实验也表明了平均路径长度和认知能力之间的相关性。综上所述，这些结果支持了局域性癫痫不是由于脑网络的局部中断造成，而是由于脑网络的整体变化导致了认知障碍产生这一假设。除了TLE之外，其他类型的癫痫如儿童缺位癫痫(CAE)和睡眠相关超运动癫痫(SHE)最近也被进行了研究。CAE是一种常见的全身性癫痫综合征，其特征是突然发生的意识严重损害，但不丧失身体张力，出现在其他健康的学龄儿童中。Wang et al.(2017)比较了CAE患者与健康对照组的中心性指标，并假设CAE患者DMN和丘脑内的枢纽节点明显受损。在其他工作中，Evangelisti等人(2018)也发现了患者主要在基底神经节和边缘系统发生的拓扑改变。

4 总结

总的来说，采用图论方法的实验在不同疾病的神经基础上较为一致的结论表明，这一方法很有希望在未来的fMRI研究中建立一个全面和可持续的模型。图论度量，如节点度、聚类系数、平均路径长度、中心节点、中心性、模块化、鲁棒性和协调性，可以被用来检测大脑网络的拓扑模式，反映认知和行为表现。但是，图论研究中的另一个挑战是，如何在定义网络节点和构建大脑网络时达成共识。不同的分割方法会导致人脑网络的拓扑性质不同，其结果取决于网络的分辨率。然而，为了更好地洞察，人们可以通过在不同空间尺度上应用多个分割方案，特别是那些高分辨率的方案，来评估主要发现的再现性。此外，节点脑区的规范性在发展研究中是极其重要的，因为在一个样本中可能存在节点不同的情况，这可能会扭曲大脑网络。因此，保证脑连通性研究中图分析可靠性的一个基本条件是网络节点的精确定义，这需要采用适当的分割策略。

除此以外，尽管结构通路被认为是功能连接模式的基础，但目前的发现表明功能和结构组织中的拓扑特性之间不存在一一对应的关系。例如，在一些神经系统疾病如精神分裂症中，小世界网络异常甚至可能在功能和结构组织上显示出相反的方向。因此，需要对结构功能关系的深入研究来帮助阐明这些研究中发现的功能和结构图论指标的偏差，为以后的工作提供帮助。

参考文献

[1] Achard, S. (2006). A resilient, low-frequency, small-world human brain functional network with highly connected association cortical hubs. J. Neurosci. 26, 63–72.

[2] Armstrong, C. C., Moody, T. D., Feusner, J. D., McCracken, J. T., Chang, S., Levitt, J. G., et al. (2016). Graph-theoretical analysis of resting-state fMRI in pediatric obsessive-compulsive disorder. J. Affect. Disord. 193, 175–184.

[3] Avena-Koenigsberger, A., Misic, B., and Sporns, O. (2018). Communication dynamics in complex brain networks. Nat. Rev. Neurosci. 19, 17–33.

[4] Barabási, A.-L., and Albert, R. (1999). Emergence of scaling in random networks. Science 286, 509–512.

[5] Barnett, L., and Seth, A. K. (2009). Granger causality and transfer entropy are equivalent for gaussian variables. Phys. Rev. Lett. 103, 238701–238704.

[6] Bassett, D. S., and Bullmore, E. (2006). Small-world brain networks. Neuroscientist 12, 512–523.

[7] Bastos, A. M., and Schoffelen, J. (2016). A tutorial review of functional connectivity analysis methods and their interpretational pitfalls. Front. Syst. Neurosci. 9:175.

[8] Betzel, R. F., Byrge, L., He, Y., Goñi, J., Zuo, X. N., and Sporns, O. (2014). Changes in structural and functional connectivity among resting-state networks across the human lifespan. Neuroimage 102, 345–357.

[9] Boccaletti, S., Latora, V., Moreno, Y., Chavez, M., and Hwang, D. U. (2006). Complex networks: structure and dynamics. Phys. Rep. 424, 175–308.

[10] Bullmore, E., and Sporns, O. (2009). Complex brain networks: graph theoretical analysis of structural and functional systems. Nat. Rev. Neurosci. 10, 186–198.

[11] Bullmore, E., and Sporns, O. (2012). The economy of brain network organization. Nat. Rev. Neurosci. 13, 336–349.

[12] Bullmore, E. T., and Bassett, D. S. (2011). Brain graphs: graphical models of the human brain connectome. Annu. Rev. Clin. Psychol. 7, 113–140.

[13] Cohen, J. D., Daw, N., Engelhardt, B., Hasson, U., Li, K., Niv, Y., et al. (2017). Computational approaches to fMRI analysis. Nat. Neurosci. 20, 304–313.

[14] Craddock, R. C., Jbabdi, S., Yan, C. G., Vogelstein, J. T., Castellanos, F. X., Di Martino, A., et al. (2013). Imaging human connectomes at the macroscale. Nat. Methods 10, 524–539.

[15] Daunizeau, J., David, O., and Stephan, K. E. (2011). Dynamic causal modelling: a critical review of the biophysical and statistical foundations. Neuroimage 58, 312–322.

[16] Harrisona, B. J., Zaleskya, A., and Simonsd, J. S. (2012). Competitive and cooperative dynamics of large-scale brain functional networks supporting recollection. Proc. Natl. Acad. Sci. U.S.A. 109, 12788–12793.

[17] Watts, D. J., and Strogatz, S. H. (1998). Collective dynamics of “small-world” networks. Nature 393, 440–442.

[18] Farahani, F. V., Karwowski, W., & Lighthall, N. R. (2019). Application of graph theory for identifying connectivity patterns in human brain networks: a systematic review. frontiers in Neuroscience, 13, 585.

[19] Yu, Q., Du, Y., Chen, J., Sui, J., Adalē, T., Pearlson, G. D., & Calhoun, V. D. (2018). Application of graph theory to assess static and dynamic brain connectivity: Approaches for building brain graphs. Proceedings of the IEEE, 106(5), 886-906.

[20] Rubinov, M., & Sporns, O. (2010). Complex network measures of brain connectivity: uses and interpretations. Neuroimage, 52(3), 1059-1069.

[21] Bassett, D. S., & Sporns, O. (2017). Network neuroscience. Nature neuroscience, 20(3), 353-364.

[22] Bassett, D. S., Zurn, P., & Gold, J. I. (2018). On the nature and use of models in network neuroscience. Nature Reviews Neuroscience, 19(9), 566-578.

[23] Stam, C. J. (2014). Modern network science of neurological disorders. Nature Reviews Neuroscience, 15(10), 683-695.

[24] Park, H. J., & Friston, K. (2013). Structural and functional brain networks: from connections to cognition. Science, 342(6158).

[25] Fornito A, Zalesky A, Breakspear M. The connectomics of brain disorders[J]. Nature Reviews Neuroscience, 2015, 16(3): 159-172.

大家都知道陶哲轩得了菲尔兹奖，可能也知道他得奖得结果是证明了存在任意长的素数等差数列，即Green-Tao Theorem。不过可能很少有人了解具体的做法。

素数等差数列，比如3，5，7 。更长一点的，比如7，37，67，97，127，157 。如果没记错，目前人们知道的最长的素数等差数列也只有26项，所以G-T定理还是很不平凡的结果。

这个证明基本上就是用图论和组合数学做的，基于Szemeredi regularity lemma和Szemeredi theorem。Szemeredi本人通过这个定理拿了Abel奖，Gowers用调和分析构造了regularity lemma中常数的界拿了菲尔兹奖，Tao推广了这个定理也拿了菲尔兹。难怪我老板说，10年之内regularity lemma将是人人都会用的工具。（特别的，Frieze和Kannan给出了regularity lemma的弱化版本，利用graph limit的理论在理论计算机中应用非常多。）

关于graph limit的最最基本的理论可以参考有哪些指标可以描述两个图（graph）的相似度？ - 知乎

G-T定理具体的证明过程大家估计不感兴趣，我说一下大概的思路。

Erdos有一个很有名的猜想，是说我有一个自然数的子集A，里面的元素是 ，如果 ，那么A中有任意长的等差数列。这个猜想至今还open，人们甚至不能证明A中有长度为3的等差数列。。G-T定理是这个猜想的特殊情况，因为所有素数倒数和也是无穷的。至于一般情况，谁能证出来这个，估计Fields没跑了。

Szemeredi证明了弱化版本，所谓Szemeredi Theorem是说，如果A是自然数的稠密子集，那么A中有任意长的等差数列。所谓稠密是指 ，其中[N]指的是前N个自然数的集合。注意到素数不满足这个性质（由素数定理），所以这个定理比G-T定理弱。

他用到的工具就是regularity lemma。

Szemeredi Regularity Lemma描述的是完全混乱是不可能的。随便给一个large graph，我都可以把他分成M份使得每两份之间非常reguler。Gowers证明了M至少是Tower Function。

通过regularity lemma可以得到graph counting lemma。我这里以三角形为例，triangle removal lemma说的是如果一个图中有不是很多的三角形（ ），我可以通过移除相当相当少的边（ ），让图中没有三角形。三部图中的三角形可以对应长度为3的等差数列，基本上用counting lemma加上一些精细的分析，可以得到Szemeredi Theorem。

G-T定理的核心是证明了relative Szemeredi theorem。因为素数集P在N中sparse，这个定理内容是说如果N的子集S满足某种性质（初始论文要满足两个条件，最新的结果简化成了一个），A在S中稠密，那么A中有任意长的等差数列。我们可以取S为一些素因子很少的数的集合，让素数在里面稠密。具体的思路就是在sparse的情况下证明图中的counting lemma。

不过可以看到这个最新的结果仍然far away from Erdos的猜想。。期待大神的突破。

正在外边吃饭，就不放reference paper了。另外有没有人知道为啥Tao凭借 Green-Tao Theorm拿了菲尔兹但是Green没有？他18年应该41了，彻底没希望了。

----------------------------

补充一下个人理解的regularity lemma在算法上的应用部分（根据问题标签，回答里还是涉及一下算法比较好）

1. regularity lemma侧重于理论上的应用（证明某些存在性），因为他给出的界是一个Tower Function（就是2的2的2的..的2次方）。这样即使我们得出的算法是linear的，其实里面的常数是一个大到无法想象的数字。

2. regularity lemma中将图分成几部分，其中有 的irregular误差，如果消去误差将会得到一个界是Tower的Tower。FK-regularity lemma应用价值更高（界是exp的），但是损失了很多regular的性质。

3. 只对dense graph有意义，因为sparse上的regularity是平凡的。sparse上最近也有一些不平凡的结果，详情看大神Yufei Zhao的paper。

4. 用regularity lemma的证明大都可以找到一个不用lemma的证明可以得到更好的界（但是很难），比如最近很热的Hypergraph container。