● 摘要
近年来，以渗流模型为代表的复杂网络模型逐渐兴起并广泛应用于各个领域。特别是渗流模型中的相变现象，具有着广泛的实际应用背景和重大的理论研究价值。对相变现象的研究有利于我们分析网络数据动力学行为的演化机制和复杂度，吸引了来自物理学、数学、计算机科学和金融学等多个领域的专家学者。
最近，随着“爆炸性渗流”概念的提出，相变连续性的讨论再次成为热点话题，人们迫切需要搞清楚相变的演化机制和规律。我们主要研究复杂网络模型中相变现象的连续性、复杂性及动力学特性，针对模型特征建立演化方程，结合动力系统、spin-glass和平均场等理论方法，对相变过程进行深入分析。首先针对类BFW这一著名的渗流模型，我们建立微分方程来刻画其动力学行为，并利用动力系统的分支定性理论，结合参数进行稳态分析。从理论上揭示并证明了模型的不连续相变，同时发现系统稳态中存在多个巨大连通分支，经过进一步的分析得出参数与稳态之间的对应关系，所得结论得到了数值实验的支持。本文所建立的这一套理论体系适用于多种不同的网络拓扑结构，不仅帮助我们分析了类BFW模型的演化机制，对于我们研究其他相变的形成机制也有巨大帮助。
相变现象在生物系统中也广泛存在，本文以自催化作用为基础，建立一个具有多种选择规则的演化模型。通过竞争机制的引入，我们发现这一自催化模型同样存在不连续相变，我们通过实验发现最大独立自催化集合规模的单步增幅与系统规模成线性关系，进一步利用之前的理论体系得出系统的演化方程，并通过奇异点分析得出相变的阀值表达式。通过定义两个新的统计量，我们还分析了模型结构的鲁棒性，指出了模型容易导致坍塌的原因。这些结论帮助我们更好的了解相变的演化机制，也为其在相关领域的应用提供更多的支持。
相变理论不仅可以从理论上揭示实际模型的本质属性，更可以帮助我们找出解决问题的关键所在。例如我们在求解最小顶点覆盖这一NP完全问题时，发现随着参数的改变使得求解的时间复杂度发生相变。通过对此相变过程的分析，我们提出一种图形生长式的模型，通过对“交互阻挫”与backbone变量之间演化规律的分析，最终得出启发式算法来帮助求解最小顶点覆盖问题。经证明该算法的复杂度是多项式时间的，并且对于某些范围内的问题是可以精确得出全部解空间结构的。这一算法的灵感来自于对渗流相变现象的深入分析，算法的实现过程体现了模型的演化过程，为求解最小顶点覆盖问题提供了一个全新的视角。