随着社会信息化程度越来越高，计算机处理的数据规模越来越大，而且数据的结构通常也具有很强的随机性。如何为这样的研究对象设计高效的算法，如何研究它们的动态演化方式，已成为新世纪计算机科学最重要的课题之一。上世纪九十年代初提出的概率可检验证明(ProbabilisticCheckableProof)以及随之发展的性质检测(PropertyTest)为这一课题提供了一种有别于传统计算方式的新思路——局部计算，它把传统意义上针对整个输入的确定的计算局部化、随机化。这包含了两层含义。一方面，对于某些大规模输入，我们可以设计不需要读完输入的亚线性时间随机算法，以小概率的错误实现高效率的计算。另一方面，对于规模庞大、结构复杂的对象，如复杂网络，我们可以通过简单的局部随机规则模拟它们的演化过程，并且研究局部规则对全局的影响。本文正是从这两个方面入手分别研究数学性质的局部检测以及网络计算的局部性原理。而局部化思想是我们贯穿全文的主线。　　 本论文的第一部分（二至四章）研究数学性质局部检测，分别讨论代数性质以及组合性质检测问题。在第二章里，我们探讨定义在有限域上的线性和仿射不变函数类的局部可检测性的刻画问题，首先证明了在相差多项式倍的意义下，当函数类定义在素域上时，对于仿射不变函数类，局部约束、局部刻画、局部规则刻画与局部可检测这四个概念等价;对于线性不变函数类，局部刻画、局部规则刻画与局部可检测这三个概念等价。这就说明在素域上，这两个基本的代数不变函数类的局部可检测性都有很好的刻画。进一步地，我们还讨论了线性不变函数类上的局部约束的问题，证明了在二元域上一个强局部约束可以刻画线性不变函数类的局部可检测性，而当域的大小超过2时，即使是强局部约束也不足以刻画它。这里主要的技术性贡献有两点。第一点是我们提出了基于有限域特征的p-进制度数的概念。与传统的多项式度数比较起来，p-进制度具有良好而直观的数学性质，更重要的是，它探到了一个不变函数类的结构的本质。我们第二章的证明主要围绕这一概念来展开。第二点是在证明反面结论时，我们定义了一类新的编码，称为模齐次Reed-Muller码。它是把传统的Reed-Muller码作为基本的仿射不变函数类类比到线性不变函数类上的编码。我们正是以之为反例证明了强局部约束不足以刻画线性不变函数类的局部可检测性。这是一个直观而系统的证明反面结论的方法，比此前所有类似的反例构造型证明都更具一般性和代表性。在第三章里我们进一步研究了这一码字的局部可检测性。我们证明了对于d-阶模齐次Reed-Muller码存在一个查询次数为O（l·q2l+1）的局部检测算法，其中q为有限域的大小，l=「d+(q-1)/q-q/p(」)，p为有限域的特征。它以概率1接受所有的d-阶模齐次Reed-Muller码的合法码字，而以概率Ω(δ)拒绝所有离d-阶模齐次Reed-Muller码δ-远的输入。这已经是一个几乎最优的局部检测算法。该算法利用了模齐次Reed-Muller码的两个刻画，是通过它们的结合而设计的。算法的分析通过代数向量张量积的一个基本性质把这两个刻画巧妙地整合在一起，从而证明其正确性。　　 在第四章里我们转入组合性质局部检测的研究。我们着重介绍了一般图模型下的传导率的局部检测算法。该算法的查询次数和运行时间均为O(m(1+σ)/2·logn·log1/(ε)/ε·(Φ)2)，其中m为图的边数，n为顶点数，ε为距离参数，σ＞0为任意小的常数，它对所有的传导率至少是(Φ)的图以至少2/3的概率接受，而对于任意的离所有传导率至少是α=Ω（(Φ)2）的图ε-远的图，它都以至少2/3的概率拒绝。这一结果已经达到了目前已知最好的在有界度数模型这种特殊情况下的传导率检测算法的效果。这里主要的技术性贡献在于我们定义了关于图的一种新的编码，称为非一致Zig-Zag积。它是经典的Zig-Zag积的推广，后者在构造扩张图以及证明无向图的s-t连通性问题有对数空间算法时发挥了重要的作用。非一致Zig-Zag积通过选择一个恰当的Zig-Zag图序列，把任意的图在保证其大小和传导率变化不大的情况下转化成正则图。这有利于我们运用有界度数模型下的传导率局部检测算法来为一般图模型构造检测算法。我们相信非一致Zig-Zag积在数学性质局部检测之外的领域依然有潜在的应用。　　 本论文的第二部分（第五、六章）转入网络计算局部性原理的研究。我们主要围绕当前网络研究的热点课题——小社区现象展开讨论。小社区是大量实际网络的基本组成单元，比如www-网、蛋白质功能网等，它在网络结构中占有重要的地位。在第五章里，我们重点探讨小社区现象形成的机理。我们遵从生活中“物以类聚，人以群分”这一常识性原理，提出了网络同源性模型，并且证明了由该模型构造的网络G以极大的概率满足如下特点:(1)G中顶点的度数服从幂律分布，(2)G中点与点之间的平均距离很小，即满足小世界现象，(3)G中几乎所有的顶点都从属于某个小社区，即满足小社区现象，(4)G中同一个小社区中的点具有某种相同的属性，即模型中的颜色，(5)每个小社区中的顶点的度数分别都服从幂律分布，(6)每个小社区都有一个与外部联系的代表元，即模型中的种子。由这一结论可以总结出一条网络的同源性定律，网络的同源性保证了网络的小社区现象，而且一些顶点形成小社区的原因是因为它们享有显著共性，即我们模型中的颜色。基于这一原理，我们提出了一个新的网络信息提取与预测算法，并通过论文引用网中的关键词预测实验来验证我们的算法是合理而有效的。　　 在第六章里我们研究一类网络中的影响扩散问题，即带阈值的小瀑布行为(ThresholdCascadingBehavior)。它是一种被广泛用于模拟社会网络中成员具有二元选择且受到来自其邻居影响的行为，比如流言传播、投票、罢工、疾病感染、广告宣传等等。我们主要研究带连续型阈值的小瀑布行为在偏好依附模型(PreferentialAttachmentModel)上的触发条件。我们证明了在所有顶点的阈值ρ都相同的情况下，对于带d条边的偏好依附模型，如果ρ取到稍稍低于1/d一点，那么一定存在着足够大的常数d使得由该模型构造的图G将以1-o(1)的概率满足:若随机地选取一个初始顶点作为被感染点，那么以常数的概率(超过1/2)全图所有的点均被感染。同时还证明了如果ρ取到高于1/d，那么G将以1-o(1)的概率满足:对于任意的常数λ＜1/2，即使随机地选取nλ个初始被感染点，也以1-o(1)的概率不会有任何初始未被感染的顶点被感染。这里的o(1)都是指顶点个数n的高阶无穷小。这就说明1/d是带d条边的偏好依附模型下的小瀑布行为能否形成大规模感染的重要阈值。这里正面结论的证明思路分为两步。首先我们沿用了网络的格局模型下分析脆弱点连通片的思路，证明了在G中以极大的概率存在大量连通的脆弱顶点，即一个邻居便足以将其感染的顶点。那么一个随机的采样将以很高的概率选到它们或者与它们相连的顶点，导致整个连通片被感染。然后以此为基础，我们利用G的传导率很高的特点，证明感染将扩张至全图。反面结论方面，证明的方法是基于组合的观察以及组合数的讨论，其主要思想是证明随机选取少数的顶点，有两个点具有共同邻居的概率很小。事实上，我们的这一思想以及结论适用于所有的不含脆弱顶点的简单图（无重边及自回路）。由于偏好依附模型中的重边和自回路数量很少，所以对它也是适用的。这样正反两面的分析方法也为其他网络模型上的带阈值的小瀑布行为研究提供了技术资源。