Analysis of Critical and Redundant Vertices in Controlling Directed Complex Networks Using Feedback Vertex Sets
Analysis of Critical and Redundant Vertices in Controlling Directed Complex Networks Using Feedback Vertex Sets
复制标题
DOI：
10.1089/cmb.2018.0019
复制
发表时间：
2018-10-01
影响因子：
1.7
通讯作者：
Akutsu, Tatsuya
中科院分区：
文献类型：
--
作者：
Bao, Yu;Hayashida, Morihiro;Akutsu, Tatsuya
通过少量控制顶点控制复杂网络在广泛的研究领域中具有重要意义。最近，一种基于最小反馈顶点集（MFVS）的新方法被提出，用于在有向网络中寻找此类顶点，其中目标状态限于稳态。然而，可能存在多种MFVS配置，因此顶点的选择可能取决于算法和输入数据表示。我们为解决这种模糊性所做的尝试使我们采用了一种现有的方法，该方法将顶点分为三类。这种方法已成功应用于基于最大匹配和基于最小支配集的可控性分析框架。在本文中，我们提出了一种算法及其实现，用于在基于MFVS的框架下计算和评估关键、间歇和冗余顶点，其中这三类分别包括属于所有MFVS的顶点、属于某些（但不是所有）MFVS的顶点以及不属于任何MFVS的顶点。使用人工生成的网络和现实世界的生物网络进行的计算实验结果表明，所提出的算法对于识别相对大规模网络的这三种顶点是有用的，并且关键和间歇顶点的比例相当小。此外，对信号通路的分析表明，关键和间歇的MFVS往往富含必需基因。
Controlling complex networks through a small number of controller vertices is of great importance in wide-ranging research fields. Recently, a new approach based on the minimum feedback vertex set (MFVS) has been proposed to find such vertices in directed networks in which the target states are restricted to steady states. However, multiple MFVS configurations may exist and thus the selection of vertices may depend on algorithms and input data representations. Our attempts to address this ambiguity led us to adopt an existing approach that classifies vertices into three categories. This approach has been successfully applied to maximum matching-based and minimum dominating set-based controllability analysis frameworks. In this article, we present an algorithm as well as its implementation to compute and evaluate the critical, intermittent, and redundant vertices under the MFVS-based framework, where these three categories include vertices belonging to all MFVSs, some (but not all) MFVSs, and none of the MFVSs, respectively. The results of computational experiments using artificially generated networks and real-world biological networks suggest that the proposed algorithm is useful for identifying these three kinds of vertices for relatively large-scale networks, and that the fraction of critical and intermittent vertices is considerably small. Moreover, an analysis of the signal pathways indicates that critical and intermittent MFVSs tend to be enriched by essential genes.