2.2 复杂网络基元方法

2.2.1 模体的概念及功能内涵

自2002年Milo等 [10]在Science上提出模体概念以来，引起了生物信息学、复杂网络研究和社会统计学等领域的广泛关注。Milo等定义模体是在网络中反复出现的相互作用的基本模式，其出现的频率远远高于其在具有相同节点和连线数的随机网络中出现的频率。模体一般理解为反映网络功能模块的拓扑单元子系统；与随机网络相比，模体是真实网络中出现频率较高且有重要意义的局部子图；模体一般由少数几个节点连接而成。大多数网络中3个节点和4个节点构成的模体较为常见。例如，在有向网络中，3个节点之间可以形成13种不同的连通关系，4个节点之间可以形成199种不同的连通关系。无向网络中的模体结构是有向网络中模体结构的特殊情况。对于无向网络，3个节点构成的连通性模体结构有2种，4个节点构成的连通性模体结构有6种，如图2.5所示。

作为网络中大量出现的具有相同结构的小规模子图，模体从局部层次刻画了真实网络相互连接的特定模式，对研究网络组织构型和行为功能具有重要作用。模体在真实网络中出现的频次远高于其在相应随机网络中出现的频次这一事实，目前有两种解释：

（1）一些学者认为模体应具有特定的功能含义。在生命科学领域，模体通常表明生命网络进化所尊崇和偏好的一种设计准则，并被证明可以行使生命网络中的一些特定功能 [152]。例如，基因调控网络中的前馈环模体互相配合完成了基因调控网络中的信息处理功能 [153]。Milo等 [10]在生物网络、神经网络、食物链和技术网络中找到的各种模体，也在各自网络中体现了不同的动力学功能，网络模体对了解代谢网络和信号传导网络中的生物化学过程及信号传递路径具有重要作用，如图2.6所示。

（2）另一批学者认为大量网络模体并非真正的功能单元体，而应作为网络建设过程的伴随品，其出现可以解释为自然选择压力或预先界定 [154]。例如，Conant等 [155]指出模体的涌现不仅是由于简单的基因复制，而且是某种自然选择机制的结果，具有独立的演化特性。

总体而言，网络模体（network motif）是小巧、重复、基本的相互作用模式，是网络分解得到的最小研究单位，是自下而上构成网络全局的“基元”。目前在系统生物学中，已定义的模体类型包括负反馈和正反馈模体、正反馈环、单输入模体、多级输入模体、链式调节子模体、多组分环等 [156]。作为复杂生物网络中的基本元件，网络模体具有信息处理和能量转换等动力学功能 [157]。研究者将注意力转向了对某一具体的有生物功能的网络基元的精确实验和数学模拟，通过控制和预测其行为，优化和重构网络系统 [158-162]。

2.2.2 模体发现的算法及工具

依据Milo等 [10]的开创性研究，网络模体是在网络中反复出现的相互作用的基本模式。这种模式出现的频率远远高于其在具有相同节点和连线数的随机网络中出现的频率。为了判断实际网络中的一个子图f是否为模体，需要产生与实际网络对应的随机化网络，并要求其与实际网络保持规模和度序列的一致，如图2.7所示。依据Milo等人提出的网络模体概念及相应的算法，网络模体发现问题包括随机网络建模、子图搜索和模体评价三个步骤。

1.随机网络建模

模体是与随机网络相比，在真实网络中频繁出现的子图。因此，随机网络建模是模体发现中的一个必要步骤。首先要求随机网络应与真实网络具有相似的统计性质。度分布是复杂网络中最重要的全局统计性质，因此通常建立与真实网络具有相同度分布的随机网络。其次，随机网络模型需保持真实网络的度序列。生成随机网络时，除了度分布或者度序列之外，也可以考虑复杂网络的其他全局统计性质，如介数分布等。根据度序列生成随机网络，有三种常用的算法 [163]。

（1）交换算法。该算法首先根据度序列构造一个网络，接着执行一系列的蒙特卡罗交换步，即随机选择一对边进行交换。若该交换导致了多重边或自回路，则取消该交换。

（2）匹配算法。该算法根据度序列给每个顶点设置入边和出边集合，然后随机地选择一个顶点的入边和另一个顶点的出边，并建立它们之间的连边关系。若该连边导致了多重边或自回路，则抛弃该网络，重新开始上述过程。

（3）赢者通吃算法。该算法同时考虑多个网络，对每一个网络的操作过程与匹配算法相似，过程中将导致多重边或自回路的网络抛弃，因此网络数不断减少。为了弥补网络个数不断减少的情况，过一段时间就把剩余的网络复制一次。重复这个过程直到所有的入边和出边都得到连接，然后随机地选择一个随机网络作为输出。

2.子图搜索

在真实网络和随机网络中搜索特定规模的子图，确定哪些子图是同构的，并将同构的子图归为一类；由于子图的数量随着网络的规模和待搜索子图的规模呈指数级增长，子图搜索是计算复杂度很高的问题，设计出优良的子图搜索发现算法是研究网络模体的重要方面。Milo等 [10]最先采用穷尽递归搜索算法，搜索给定规模的所有子图。该算法用N×N的邻接矩阵表示输入网络，通过枚举其中所有的n×n子矩阵得到对应的导出子图，仅能有效地发现小规模子图，如3和4节点子图。Wernicke等 [164]进一步研究提出用ESU算法寻找所有子图。该算法从输入网络的一个节点v开始，增加具有以下两个性质的节点到集合Ve中：一是它们的下标必须比v的下标大；二是它们不属于Vs中某个节点的邻接点。该算法从规模为1的子图出发逐步增大子图规模，尽管也是枚举子图，但它通过规定约束条件，减少了搜索空间，保证一个子图仅被搜索一次，且不会产生无意义的子图。但由于问题固有的复杂性，ESU能搜索的子图也不能达到较大规模，且计算速度较慢。为提高子图搜索效率，Kashtan等 [165]提出了采样算法，估计子图的相对出现次数。ESA算法随机选择一条边，将其关联顶点加入到子图顶点集合Vsubgraph中，然后不断地将Vsubgraph中顶点的邻接点增加到Vsubgraph中，直到子图达到指定规模，得到一个采样的子图。重复该过程，直到采样的子图数达到预定义的个数。ESA算法独立于网络规模，它解决了搜索子图数量随输入网络规模和子图规模呈指数级增长的问题，理论上可以在网络中搜索较大规模的子图。然而，ESA算法对相同子图可能会多次采样，而另外的子图被采样的概率很低，从而导致最后发现的模体不准确。

3.模体评价

关于模体的统计意义评价尚无统一标准，在网络模体开创性文献 [10]中，通过与随机网络比较计算子图的Z值来评价模体统计意义。

式中，Nreali表示子图gi在真实网络中的出现次数，而〈Nrandi〉和std（σrandi）分别表示子图gi在随机网络集合中的平均出现次数和标准差。关于子图Z值的显著性有三条标准：①该子图在与真实网络对应的随机网络中出现的次数大于其在真实网络中出现次数的概率很小，通常要求这个概率小于某个阈值P，如P=0.01。②该子图在真实网络中作为无节点或边重叠的独立子图出现的次数Nreal不小于某个下限U，如U=3。③该子图在真实网络中出现的次数Nreal明显高于它在随机网络中出现的次数Nrand，一般要求（Nreal-Nrand）＞0.1Nrand。

随着模体研究的发展和算法的成熟，已出现如下典型的网络模体检测和分析的算法工具：

（1）Mfinder：第一个模体分析工具，结合广泛的随机图模型来检测随机图中子图的频率，具有完全列举和抽样方法 [166]两种算法，Mfinder支持检测多达8节点的网络模体；其主要缺点是随着子图大小的增加，子图枚举和采样算法较慢。

（2）Pajek：广泛用于社会网络分析的Pajek，可用于搜寻所有网络中确定的图样，尤其是一些具有3或4个节点的特殊模体，但其在子图枚举和随机网络统计比较方面支持不够。

（3）MAVisto：可发现有向网络中的3~5个节点的模体并可视化，可支持检测多达8节点的网络模体 [167]；其主要缺点是随着子图大小的增加，搜索速度较慢。

（4）Famond：Famond快速模体检测算法工具采用RAND-ESU枚举采样子图的新算法，使检测效率得到极大提升，并能找到具有8个节点的模体 [168]。此外，Famond可以处理不同实体间和不同作用类型的节点着色和边着色网络的模体。