网络化系统中的回路分布与系统复杂性

赵千川
(清华大学自动化系智能与网络化系统研究中心)

　　现今的网络化系统研究，引起了学术界的广泛兴趣。

　　一个有趣的现象是系统当中圈（有向回路）的个数与系统复杂性之间的关联。很容易理解，无环网络，节点间可以进行拓扑排序，分析起来可以采用串行的方式。以求解不动点为例，可以从排得靠前的节点到靠后的节点依次进行。当出现有向回路时，节点之间存在相互影响。为了简化问题的分析，人们引入了顶点子集中的一类子集“回路割集”的概念。回路割集又称为反馈顶点集合。当我们去除了回路割集中的节点时，网络化系统就变成为一个无环图。因此，整个网络化系统的研究，可以归结为回路割集上的网络化子系统（可以看作某种形式的内核）和由该子系统驱动的系统剩余节点构成的输出子系统来分别研究。

　　遗憾的是，早在1972年Karp就证明了寻找最小回路割集是NP难题。这暗示着含一般大规模网络化系统的回路及动态分析是一个非常复杂的问题。

　　当前人们在网络科学中对现实世界复杂网络的研究，大多集中在以度分布为基础的问题方面，已经取得了很多深刻的结果，发现了无尺度、幂律分布等特征。但对度分布以外的图属性，特别是涉及回路割集的统计特征，研究较少。但由于回路的存在，对动态系统长期行为，特别是吸引子和不动点有决定性的影响，了解回路分布及相关统计特性对揭示复杂网络的动态行为有重要意义。

　　我们针对节点动态行为以逻辑关系描述的网络化动态系统—布尔网络，运用回路割集的分析思路，提出了一种简化不动点分析的算法。运用该算法，可以证明系统不动点的个数是受到回路割集中的节点个数控制的，这就推广了此前学者关于调控布尔网络的相应结论。利用向3-SAT问题的多项式规约，我们还证明了当系统中的基本回路个数达到节点总数的一半以上时，布尔网络的不动点计数问题将是NP难的。这些工作表明，即使对于即使节点只有两个状态的网络化动态系统，回路的数量分布都对系统行为分析乃至控制综合有重要的影响。

　　按照Kauffman在Origins of Order一书中关于实际网络化系统运行在无序和有序边缘的说法，统计实际系统中回路的分布情况，似乎满足如下猜想：基本回路的量级应足够大，以至于随节点数增长，应当趋于无穷，但又应当足够小，在节点数的线性量级以下。或许是节点总数的对数函数？这值得深入研究。

获奖者简介：

　　赵千川，清华大学自动化系教授、博士生导师，中国自动化学会控制理论专业委员会副主任。

　　主要研究方向为网络化动态系统的性能优化、安全控制和稳定性分析，主持多项国家自然科学基金面上项目和国际合作课题，发表高水平SCI国际期刊论文47篇（近5年来21篇），其中IEEE期刊论文22篇（近5年来8篇），论著的SCI他引超过300篇次，他引期刊包括《自然×生物技术杂志》和14种IEEE汇刊在内的超过70种期刊，他引作者中的IEEE Fellow超过40位。

　　先后作为惟一获奖人获得第九届关肇直优秀论文奖（2003），作为第二完成人获得2009年国家自然科学二等奖（获奖项目“离散事件动态系统的优化理论与方法”），作为第一完成人获得2013年教育部自然科学二等奖（获奖项目“事件驱动的网络化动态系统的建模与控制”）等学术奖励，并入选2004年教育部新世纪优秀人才支持计划。担任《控制理论与应用》期刊副主编，担任IEEE网络系统控制汇刊和《自动化学报》等国内外学术期刊编委。