1,592
个编辑
更改
Moved page from wikipedia:en:Network controllability (history)
此词条暂由彩云小译翻译，未经人工整理和审校，带来阅读不便，请见谅。
[[Image:YYL1.png|right|thumb|Controlling a simple network.]]
Controlling a simple network.
控制一个简单的网络。
'''Network Controllability''' is concerned about the structural [[controllability]] of a [[Graph (discrete mathematics)|network]]. Controllability describes our ability to guide a [[dynamical system]] from any initial state to any desired final state in finite time, with a suitable choice of inputs. This definition agrees well with our intuitive notion of control. The controllability of general directed and weighted complex networks has recently been the subject of intense study by a number of groups in wide variety of networks, worldwide. Recent studies by Sharma et al.<ref>{{Cite journal|last=Sharma|first=Ankush|last2=Cinti|first2=Caterina|last3=Capobianco|first3=Enrico|date=2017|title=Multitype Network-Guided Target Controllability in Phenotypically Characterized Osteosarcoma: Role of Tumor Microenvironment|journal=Frontiers in Immunology|language=English|volume=8|pages=918|doi=10.3389/fimmu.2017.00918|pmid=28824643|pmc=5536125|issn=1664-3224}}</ref> on multi-type biological networks (gene- gene, miRNA- gene, Protein-protein interaction networks) identified control targets in phenotypically characterized Osteosarcoma showing important role of genes and proteins responsible for maintaining tumor microenvironment.
Network Controllability is concerned about the structural controllability of a network. Controllability describes our ability to guide a dynamical system from any initial state to any desired final state in finite time, with a suitable choice of inputs. This definition agrees well with our intuitive notion of control. The controllability of general directed and weighted complex networks has recently been the subject of intense study by a number of groups in wide variety of networks, worldwide. Recent studies by Sharma et al. on multi-type biological networks (gene- gene, miRNA- gene, Protein-protein interaction networks) identified control targets in phenotypically characterized Osteosarcoma showing important role of genes and proteins responsible for maintaining tumor microenvironment.
网络可控性研究的是网络的结构可控性。可控性描述了我们在有限时间内，通过合适的输入选择，引导动力系统从任何初始状态到任何期望的最终状态的能力。这个定义与我们直观的控制概念非常吻合。一般有向和加权复杂网络的可控性是近年来世界范围内各种网络的研究热点之一。夏尔马等人最近的研究。多种生物学网络(基因-基因、 miRNA-基因、蛋白质-蛋白质相互作用网络)在表型特征的骨肉瘤中确定了控制靶点，显示了维持肿瘤微环境的基因和蛋白质的重要作用。
==Background==
Consider the canonical linear time-invariant dynamics on a complex network
Consider the canonical linear time-invariant dynamics on a complex network
考虑复杂网络上的正则线性定常动力学
<math>
<math>
数学
\dot{\mathbf{X}}(t) = \mathbf{A} \cdot \mathbf{X}(t) + \mathbf{B}\cdot \mathbf{u}(t)
\dot{\mathbf{X}}(t) = \mathbf{A} \cdot \mathbf{X}(t) + \mathbf{B}\cdot \mathbf{u}(t)
[参考译文][参考译文][参考译文][参考译文][参考译文][参考译文]
</math>
</math>
数学
where the vector <math>\mathbf{X}(t)=(x_1(t),\cdots,x_N(t))^\mathrm{T}</math> captures the state of a system of <math>N</math> nodes at time <math>t</math>. The <math>N \times N</math>
where the vector <math>\mathbf{X}(t)=(x_1(t),\cdots,x_N(t))^\mathrm{T}</math> captures the state of a system of <math>N</math> nodes at time <math>t</math>. The <math>N \times N</math>
其中，向量 math { x }(t)(x1(t) ，cdots，xn (t)) ^ mathrm { t } / math 捕获了时间 math t / math 时数学 n / math 节点系统的状态。数学 n 乘以 n / 数学
matrix <math>\mathbf{A}</math> describes the system's wiring diagram and the interaction strength between the components. The <math>N \times M</math> matrix <math>\mathbf{B}</math> identifies the nodes controlled by an outside controller. The system is controlled through the time dependent input vector <math>\mathbf{u}(t) = (u_1(t),\cdots,u_M(t))^\mathrm{T}</math> that the controller imposes on the system. To identify the ''minimum'' number of driver nodes, denoted by <math>N_\mathrm{D}</math>, whose control is sufficient to fully control the system's dynamics, Liu et al.<ref name="Liu-Nature-11">{{cite journal | last=Liu | first=Yang-Yu | last2=Slotine | first2=Jean-Jacques | last3=Barabási | first3=Albert-László | title=Controllability of complex networks | journal=Nature | publisher=Springer Science and Business Media LLC | volume=473 | issue=7346 | year=2011 | issn=0028-0836 | doi=10.1038/nature10011 | pages=167–173}}</ref> attempted to combine the tools from structural control theory, graph theory and statistical physics. They showed<ref name="Liu-Nature-11"/> that the minimum number of inputs or driver nodes needed to maintain full control of the network is determined by the 'maximum matching’ in the network, that is, the maximum set of links that do not share start or end nodes. From this result, an analytical framework, based on the in-out degree distribution, was developed to predict <math>n_\mathrm{D} =N_\mathrm{D}/N </math> for scale-free and Erdős–Rényi Graphs.<ref name="Liu-Nature-11"/> However, more recently it has been demonstrated that network controllability (and other structure-only methods which use exclusively the connectivity of a graph, <math>\mathbf{A}</math>, to simplify the underlying dynamics), both undershoot and overshoot the number and which sets of driver nodes best control network dynamics, highlighting the importance of redundancy (e.g. canalization) and non-linear dynamics in determining control.<ref name="gates_rocha_scirep">{{cite journal | last=Gates | first=Alexander J. | last2=Rocha | first2=Luis M. | title=Control of complex networks requires both structure and dynamics | journal=Scientific Reports | publisher=Springer Science and Business Media LLC | volume=6 | issue=1 | date=2016-04-18 | issn=2045-2322 | doi=10.1038/srep24456 | page=24456|doi-access=free}}</ref>
matrix <math>\mathbf{A}</math> describes the system's wiring diagram and the interaction strength between the components. The <math>N \times M</math> matrix <math>\mathbf{B}</math> identifies the nodes controlled by an outside controller. The system is controlled through the time dependent input vector <math>\mathbf{u}(t) = (u_1(t),\cdots,u_M(t))^\mathrm{T}</math> that the controller imposes on the system. To identify the minimum number of driver nodes, denoted by <math>N_\mathrm{D}</math>, whose control is sufficient to fully control the system's dynamics, Liu et al. attempted to combine the tools from structural control theory, graph theory and statistical physics. They showed
矩阵数学描述了系统的接线图和元件之间的交互强度。Math n 次 m / math 矩阵 math { b } / math 识别由外部控制器控制的节点。系统通过控制器强加给系统的时变输入向量 math { u }(t)(u 1(t) ，ctdots，u m (t)) ^ mathrm { t } / math 来控制。为了确定驱动节点的最小数目，用数学 n mathrum { d } / math 表示，其控制足以完全控制系统的动力学，Liu 等人。试图结合结构控制理论，图论和统计物理学的工具。他们出现了
It is also notable, that Liu's et al. formulation<ref name="Liu-Nature-11"/> would predict same values of <math>{n_\mathrm{D}}</math> for a chain graph and for a weak densely connected graph. Obviously, both these graphs have very different in and out degree distributions. A recent unpublished work,<ref name = "Arxiv_Close_Betw">{{cite arXiv|first=SJ |last=Banerjee |first2=S |last2=Roy|title=Key to Network Controllability|eprint=1209.3737}}</ref> questions whether [[Degree (graph theory)|degree]], which is a purely local measure in networks, would completely describe controllability and whether even slightly distant nodes would have no role in deciding network controllability. Indeed, for many real-word networks, namely, food webs, neuronal and metabolic networks, the mismatch in values of <math>{n_\mathrm{D}}^{real}</math> and <math>{n_\mathrm{D}}^\mathrm{rand\_degree}</math> calculated by Liu et al.<ref name="Liu-Nature-11"/> is notable. If controllability is decided mainly by degree, why are <math>{n_\mathrm{D}}^{real}</math> and <math>{n_\mathrm{D}}^\mathrm{rand\_degree}</math> so different for many real world networks? They argued <ref name="Liu-Nature-11"/> (arXiv:1203.5161v1), that this might be due to the effect of degree correlations. However, it has been shown<ref name = "Arxiv_Close_Betw"/> that network controllability can be altered only by using [[betweenness centrality]] and [[closeness centrality]], without using [[degree (graph theory)]] or degree correlations at all.
It is also notable, that Liu's et al. formulation questions whether degree, which is a purely local measure in networks, would completely describe controllability and whether even slightly distant nodes would have no role in deciding network controllability. Indeed, for many real-word networks, namely, food webs, neuronal and metabolic networks, the mismatch in values of <math>{n_\mathrm{D}}^{real}</math> and <math>{n_\mathrm{D}}^\mathrm{rand\_degree}</math> calculated by Liu et al. is notable. If controllability is decided mainly by degree, why are <math>{n_\mathrm{D}}^{real}</math> and <math>{n_\mathrm{D}}^\mathrm{rand\_degree}</math> so different for many real world networks? They argued (arXiv:1203.5161v1), that this might be due to the effect of degree correlations. However, it has been shown that network controllability can be altered only by using betweenness centrality and closeness centrality, without using degree (graph theory) or degree correlations at all.
同样值得注意的是，刘的等人。度是网络中一种纯粹的局部度量，它是否能完全描述网络的可控性，即使是稍微远一点的节点在决定网络的可控性方面是否没有作用。事实上，对于许多实词网络，即食物网络、神经元网络和代谢网络，Liu 等人计算的数学数学和数学数学的值不匹配。值得注意的是。如果可控性主要是由程度决定的，那么为什么对于许多现实世界的网络来说，数学、数学和数学如此不同？他们认为(arXiv: 1203.5161 v1) ，这可能是由于度相关性的影响。然而，研究表明，网络的可控性只能通过介于中心性和接近中心性之间来改变，完全不需要度(图论)或度相关性。
[[File:YYL2.pdf|right|thumb|A schematic diagram shows the control of a directed network. For a given directed network (Fig. a), one calculates its maximum matching: a largest set of edges without common heads or tails. The maximum matching will compose of a set of vertex-disjoint directed paths and directed cycles (see red edges in Fig.b). If a node is a head of a matching edge, then this node is matched (green nodes in Fig.b). Otherwise, it is unmatched (white nodes in Fig.b). Those unmatched nodes are the nodes one needs to control, i.e. the driver nodes. By injecting signals to those driver nodes, one gets a set of directed path with starting points being the inputs (see Fig.c). Those paths are called "stems". The resulting digraph is called U-rooted factorial connection. By "grafting" the directed cycles to those "stems", one gets "buds". The resulting digraph is called the cacti (see Fig.d). According to the structural controllability theorem,<ref name="Lin-74"/> since there is a cacti structure spanning the controlled network (see Fig.e), the system is controllable. The cacti structure (Fig.d) underlying the controlled network (Fig.e) is the "skeleton" for maintaining controllability.]]
A schematic diagram shows the control of a directed network. For a given directed network (Fig. a), one calculates its maximum matching: a largest set of edges without common heads or tails. The maximum matching will compose of a set of vertex-disjoint directed paths and directed cycles (see red edges in Fig.b). If a node is a head of a matching edge, then this node is matched (green nodes in Fig.b). Otherwise, it is unmatched (white nodes in Fig.b). Those unmatched nodes are the nodes one needs to control, i.e. the driver nodes. By injecting signals to those driver nodes, one gets a set of directed path with starting points being the inputs (see Fig.c). Those paths are called "stems". The resulting digraph is called U-rooted factorial connection. By "grafting" the directed cycles to those "stems", one gets "buds". The resulting digraph is called the cacti (see Fig.d). According to the structural controllability theorem, since there is a cacti structure spanning the controlled network (see Fig.e), the system is controllable. The cacti structure (Fig.d) underlying the controlled network (Fig.e) is the "skeleton" for maintaining controllability.
示意图显示了一个有向网络的控制。对于给定的有向网络(图)。A) ，计算它的最大匹配: 没有共同的正面或反面的最大边集。最大匹配将由一组顶点不相交的有向路径和有向循环组成(见图 b 中的红边)。如果一个节点是匹配边的头部，则匹配该节点(图 b 中的绿色节点)。否则，它是不匹配的(图 b 中的白色节点)。那些不匹配的节点是需要控制的节点，即。驱动节点。通过向这些驱动节点注入信号，可以获得一组有向路径，起始点作为输入(参见图 c)。这些路径被称为“茎”。由此产生的有向图称为根 u 阶乘连接。通过“嫁接”那些“茎”的定向循环，一个人得到“芽”。得到的有向图称为 cacti (见图 d)。根据结构能控性定理，由于存在跨越受控网络的 cacti 结构(见图 e) ，系统是可控的。控制网络(Fig.e)底层的 cacti 结构(Fig.d)是维持可控性的“骨架”。
===Structural Controllability===
The concept of the structural properties was first introduced by Lin (1974)<ref name="Lin-74">C.-T. Lin, ''IEEE Trans. Auto. Contr.'' '''19'''
The concept of the structural properties was first introduced by Lin (1974)<ref name="Lin-74">C.-T. Lin, IEEE Trans. Auto. Contr. 19
结构性质的概念最早是由 Lin (1974) ref name"Lin-74"c. t. Lin，IEEE Trans。自动。女名女子名。19
(1974).</ref> and then extended by Shields and Pearson (1976)<ref name="Shields-76">R. W. Shields and J. B. Pearson, ''IEEE Trans. Auto. Contr.'' '''21'''
(1974).</ref> and then extended by Shields and Pearson (1976)<ref name="Shields-76">R. W. Shields and J. B. Pearson, IEEE Trans. Auto. Contr. 21
(1974) . / ref and then extended by Shields and Pearson (1976) ref name"Shields-76"r.希尔兹和 j。培生，IEEE Trans。自动。女名女子名。21
(1976).</ref> and alternatively derived by Glover and Silverman (1976).<ref name="Glover-76">K. Glover and L. M. Silverman, ''IEEE Trans. Auto. Contr.'' '''21'''
(1976).</ref> and alternatively derived by Glover and Silverman (1976).<ref name="Glover-76">K. Glover and L. M. Silverman, IEEE Trans. Auto. Contr. 21
(1976) . / ref 和另外由 Glover 和 Silverman (1976)派生。 ref name"Glover-76"k。格洛弗和 l. m. Silverman，IEEE Trans。自动。女名女子名。21
(1976).</ref> The main question is whether the lack of controllability or observability are generic with respect to the variable system parameters. In the framework of structural control the system parameters are either independent free variables or fixed zeros. This is consistent for models of physical systems since parameter values are never known exactly, with the exception of zero values which express the absence of interactions or connections.
(1976).</ref> The main question is whether the lack of controllability or observability are generic with respect to the variable system parameters. In the framework of structural control the system parameters are either independent free variables or fixed zeros. This is consistent for models of physical systems since parameter values are never known exactly, with the exception of zero values which express the absence of interactions or connections.
(1976年)。 / ref 主要的问题是，对于可变系统参数来说，缺乏可控性或可观测性是否是一般性的。在结构控制的框架下，系统参数可以是独立自由变量，也可以是固定零点。这对于物理系统的模型是一致的，因为参数值永远不会准确地知道，零值除外，零值表示交互或连接的缺失。
===Maximum Matching===
In graph theory, a [[matching (graph theory)|matching]] is a set of edges without common vertices. Liu et al.<ref name="Liu-Nature-11"/> extended this definition to directed graph, where a matching is a set of directed edges that do not share start or end vertices. It is easy to check that a matching of a directed graph composes of a set of vertex-disjoint simple paths and cycles. The maximum matching of a directed network can be efficiently calculated by working in the bipartite representation using the classical [[Hopcroft–Karp algorithm]], which runs in O(''E''{{radic|''N''}}) time in the worst case. For undirected graph, analytical solutions of the size and number of maximum matchings have been studied using the [[cavity method]] developed in statistical physics.<ref name="Zdeborova-06">[[Lenka Zdeborová|L. Zdeborová]] and M. Mezard, ''J. Stat. Mech.'' '''05''' (2006).</ref> Liu et al.<ref name="Liu-Nature-11"/> extended the calculations for directed graph.
In graph theory, a matching is a set of edges without common vertices. Liu et al. Liu et al. extended the calculations for directed graph.
在图论中，匹配是一组没有共同顶点的边。刘等人。刘等人。扩展了有向图的计算。
By calculating the maximum matchings of a wide range of real networks, Liu et al.<ref name="Liu-Nature-11"/> asserted that the number of driver nodes is determined mainly by the networks degree distribution <math>P(k_\mathrm{in}, k_\mathrm{out})</math>. They also calculated the average number of driver nodes for a network ensemble with arbitrary degree distribution using the [[cavity method]]. It is interesting that for a chain graph and a weak densely connected graph, both of which have very different in and out degree distributions; the formulation of Liu et al.<ref name="Liu-Nature-11"/> would predict same values of <math>{n_\mathrm{D}}</math>. Also, for many real-word networks, namely, food webs, neuronal and metabolic networks, the mismatch in values of <math>{n_\mathrm{D}}^{real}</math> and <math>{n_\mathrm{D}}^\mathrm{rand\_degree}</math> calculated by Liu et al.<ref name="Liu-Nature-11"/> is notable. If controllability is decided purely by degree, why are <math>{n_\mathrm{D}}^{real}</math> and <math>{n_\mathrm{D}}^\mathrm{rand\_degree}</math> so different for many real world networks? It remains open to scrutiny whether ''control robustness" in networks is influenced more by using [[betweenness centrality]] and [[closeness centrality]]<ref name = "Arxiv_Close_Betw"/> over [[degree (graph theory)]] based metrics.
By calculating the maximum matchings of a wide range of real networks, Liu et al. asserted that the number of driver nodes is determined mainly by the networks degree distribution <math>P(k_\mathrm{in}, k_\mathrm{out})</math>. They also calculated the average number of driver nodes for a network ensemble with arbitrary degree distribution using the cavity method. It is interesting that for a chain graph and a weak densely connected graph, both of which have very different in and out degree distributions; the formulation of Liu et al. would predict same values of <math>{n_\mathrm{D}}</math>. Also, for many real-word networks, namely, food webs, neuronal and metabolic networks, the mismatch in values of <math>{n_\mathrm{D}}^{real}</math> and <math>{n_\mathrm{D}}^\mathrm{rand\_degree}</math> calculated by Liu et al. is notable. If controllability is decided purely by degree, why are <math>{n_\mathrm{D}}^{real}</math> and <math>{n_\mathrm{D}}^\mathrm{rand\_degree}</math> so different for many real world networks? It remains open to scrutiny whether control robustness" in networks is influenced more by using betweenness centrality and closeness centrality over degree (graph theory) based metrics.
通过计算各种实际网络的最大匹配，刘等人提出了一种新的网络匹配算法。断言驱动节点数主要由网络度分布数学 p (k，k，k) / 数学决定。他们还利用空腔法计算了任意度分布的网络集成的平均驱动节点数。有趣的是，对于链图和弱紧连通图，它们的内外度分布都有很大的不同。可以预测相同的数学数值。此外，对于许多实词网络，即食物网络、神经元网络和代谢网络，Liu 等人计算出的数学函数 d ^ 实数 / 数学和数学函数 d ^ 实数 / 数学的值不匹配。值得注意的是。如果可控性纯粹是由程度决定的，那么为什么对于许多现实世界的网络来说，数学、数学和数学如此不同？网络中的控制鲁棒性是否受基于度的度量中介中心性和贴近中心性的影响仍有待进一步研究。
While sparser graphs are more difficult to control,<ref name="Liu-Nature-11"/><ref name = "Arxiv_Close_Betw"/> it would obviously be interesting to find whether [[betweenness centrality]] and [[closeness centrality]]<ref name = "Arxiv_Close_Betw"/> or degree heterogeneity<ref name="Liu-Nature-11"/> plays a more important role in deciding controllability of sparse graphs with almost similar degree distributions.
While sparser graphs are more difficult to control, it would obviously be interesting to find whether betweenness centrality and closeness centrality or degree heterogeneity plays a more important role in deciding controllability of sparse graphs with almost similar degree distributions.
尽管稀疏图的可控性难以控制，但是研究具有几乎相似度分布的稀疏图的可控性中，是否存在介于介于中间中心性和封闭中心性或度异质性起着更重要的作用显然是很有意义的。
==Control of composite quantum systems and algebraic graph theory==
A control theory of networks has also been developed in the context of universal control for composite quantum systems, where subsystems and their interactions are associated to nodes and links, respectively.<ref name="BG-07">{{cite journal | last=Burgarth | first=Daniel | last2=Giovannetti | first2=Vittorio | title=Full Control by Locally Induced Relaxation | journal=Physical Review Letters | publisher=American Physical Society (APS) | volume=99 | issue=10 | date=2007-09-05 | issn=0031-9007 | doi=10.1103/physrevlett.99.100501 | page=100501| arxiv=0704.3027 }}</ref> This framework permits to formulate Kalman's criterion with tools from [[algebraic graph theory]] via the [[minimum rank of a graph]] and related notions.<ref name="BDHSY-13">{{cite journal|last1=Burgarth|first1=Daniel|last2=D'Alessandro|first2=Domenico|last3=Hogben|first3=Leslie|author3-link=Leslie Hogben|last4=Severini|first4=Simone|last5=Young|first5=Michael|doi=10.1109/TAC.2013.2250075|issue=9|journal=IEEE Transactions on Automatic Control|mr=3101617|pages=2349–2354|title=Zero forcing, linear and quantum controllability for systems evolving on networks|volume=58|year=2013}}</ref><ref name="OT-15">S. O'Rourke, B. Touri, https://arxiv.org/abs/1511.05080.</ref>
A control theory of networks has also been developed in the context of universal control for composite quantum systems, where subsystems and their interactions are associated to nodes and links, respectively. This framework permits to formulate Kalman's criterion with tools from algebraic graph theory via the minimum rank of a graph and related notions.
在复合量子系统的通用控制的背景下，也发展了网络控制理论，其中子系统及其相互作用分别与节点和链路相关联。这个框架允许用代数图论的工具通过图的最小秩和相关概念来建立卡尔曼准则。
== See also ==
* [[Controllability Gramian]]
==References==
<references/>
== External links ==
* [http://barabasilab.neu.edu/projects/controllability/ The network controllability project website]
* [https://www.youtube.com/watch?v=9-q2qpOJfkg The video showing network controllability]
<!--- Categories --->
<!--- Categories --->
!-类别-
[[Category:Network theory]]
Category:Network theory
范畴: 网络理论
<noinclude>
<small>This page was moved from [[wikipedia:en:Network controllability]]. Its edit history can be viewed at [[网络可控性/edithistory]]</small></noinclude>
[[Category:待整理页面]]
[[Image:YYL1.png|right|thumb|Controlling a simple network.]]
Controlling a simple network.
控制一个简单的网络。
'''Network Controllability''' is concerned about the structural [[controllability]] of a [[Graph (discrete mathematics)|network]]. Controllability describes our ability to guide a [[dynamical system]] from any initial state to any desired final state in finite time, with a suitable choice of inputs. This definition agrees well with our intuitive notion of control. The controllability of general directed and weighted complex networks has recently been the subject of intense study by a number of groups in wide variety of networks, worldwide. Recent studies by Sharma et al.<ref>{{Cite journal|last=Sharma|first=Ankush|last2=Cinti|first2=Caterina|last3=Capobianco|first3=Enrico|date=2017|title=Multitype Network-Guided Target Controllability in Phenotypically Characterized Osteosarcoma: Role of Tumor Microenvironment|journal=Frontiers in Immunology|language=English|volume=8|pages=918|doi=10.3389/fimmu.2017.00918|pmid=28824643|pmc=5536125|issn=1664-3224}}</ref> on multi-type biological networks (gene- gene, miRNA- gene, Protein-protein interaction networks) identified control targets in phenotypically characterized Osteosarcoma showing important role of genes and proteins responsible for maintaining tumor microenvironment.
Network Controllability is concerned about the structural controllability of a network. Controllability describes our ability to guide a dynamical system from any initial state to any desired final state in finite time, with a suitable choice of inputs. This definition agrees well with our intuitive notion of control. The controllability of general directed and weighted complex networks has recently been the subject of intense study by a number of groups in wide variety of networks, worldwide. Recent studies by Sharma et al. on multi-type biological networks (gene- gene, miRNA- gene, Protein-protein interaction networks) identified control targets in phenotypically characterized Osteosarcoma showing important role of genes and proteins responsible for maintaining tumor microenvironment.
网络可控性研究的是网络的结构可控性。可控性描述了我们在有限时间内，通过合适的输入选择，引导动力系统从任何初始状态到任何期望的最终状态的能力。这个定义与我们直观的控制概念非常吻合。一般有向和加权复杂网络的可控性是近年来世界范围内各种网络的研究热点之一。夏尔马等人最近的研究。多种生物学网络(基因-基因、 miRNA-基因、蛋白质-蛋白质相互作用网络)在表型特征的骨肉瘤中确定了控制靶点，显示了维持肿瘤微环境的基因和蛋白质的重要作用。
==Background==
Consider the canonical linear time-invariant dynamics on a complex network
Consider the canonical linear time-invariant dynamics on a complex network
考虑复杂网络上的正则线性定常动力学
<math>
<math>
数学
\dot{\mathbf{X}}(t) = \mathbf{A} \cdot \mathbf{X}(t) + \mathbf{B}\cdot \mathbf{u}(t)
\dot{\mathbf{X}}(t) = \mathbf{A} \cdot \mathbf{X}(t) + \mathbf{B}\cdot \mathbf{u}(t)
[参考译文][参考译文][参考译文][参考译文][参考译文][参考译文]
</math>
</math>
数学
where the vector <math>\mathbf{X}(t)=(x_1(t),\cdots,x_N(t))^\mathrm{T}</math> captures the state of a system of <math>N</math> nodes at time <math>t</math>. The <math>N \times N</math>
where the vector <math>\mathbf{X}(t)=(x_1(t),\cdots,x_N(t))^\mathrm{T}</math> captures the state of a system of <math>N</math> nodes at time <math>t</math>. The <math>N \times N</math>
其中，向量 math { x }(t)(x1(t) ，cdots，xn (t)) ^ mathrm { t } / math 捕获了时间 math t / math 时数学 n / math 节点系统的状态。数学 n 乘以 n / 数学
matrix <math>\mathbf{A}</math> describes the system's wiring diagram and the interaction strength between the components. The <math>N \times M</math> matrix <math>\mathbf{B}</math> identifies the nodes controlled by an outside controller. The system is controlled through the time dependent input vector <math>\mathbf{u}(t) = (u_1(t),\cdots,u_M(t))^\mathrm{T}</math> that the controller imposes on the system. To identify the ''minimum'' number of driver nodes, denoted by <math>N_\mathrm{D}</math>, whose control is sufficient to fully control the system's dynamics, Liu et al.<ref name="Liu-Nature-11">{{cite journal | last=Liu | first=Yang-Yu | last2=Slotine | first2=Jean-Jacques | last3=Barabási | first3=Albert-László | title=Controllability of complex networks | journal=Nature | publisher=Springer Science and Business Media LLC | volume=473 | issue=7346 | year=2011 | issn=0028-0836 | doi=10.1038/nature10011 | pages=167–173}}</ref> attempted to combine the tools from structural control theory, graph theory and statistical physics. They showed<ref name="Liu-Nature-11"/> that the minimum number of inputs or driver nodes needed to maintain full control of the network is determined by the 'maximum matching’ in the network, that is, the maximum set of links that do not share start or end nodes. From this result, an analytical framework, based on the in-out degree distribution, was developed to predict <math>n_\mathrm{D} =N_\mathrm{D}/N </math> for scale-free and Erdős–Rényi Graphs.<ref name="Liu-Nature-11"/> However, more recently it has been demonstrated that network controllability (and other structure-only methods which use exclusively the connectivity of a graph, <math>\mathbf{A}</math>, to simplify the underlying dynamics), both undershoot and overshoot the number and which sets of driver nodes best control network dynamics, highlighting the importance of redundancy (e.g. canalization) and non-linear dynamics in determining control.<ref name="gates_rocha_scirep">{{cite journal | last=Gates | first=Alexander J. | last2=Rocha | first2=Luis M. | title=Control of complex networks requires both structure and dynamics | journal=Scientific Reports | publisher=Springer Science and Business Media LLC | volume=6 | issue=1 | date=2016-04-18 | issn=2045-2322 | doi=10.1038/srep24456 | page=24456|doi-access=free}}</ref>
matrix <math>\mathbf{A}</math> describes the system's wiring diagram and the interaction strength between the components. The <math>N \times M</math> matrix <math>\mathbf{B}</math> identifies the nodes controlled by an outside controller. The system is controlled through the time dependent input vector <math>\mathbf{u}(t) = (u_1(t),\cdots,u_M(t))^\mathrm{T}</math> that the controller imposes on the system. To identify the minimum number of driver nodes, denoted by <math>N_\mathrm{D}</math>, whose control is sufficient to fully control the system's dynamics, Liu et al. attempted to combine the tools from structural control theory, graph theory and statistical physics. They showed
矩阵数学描述了系统的接线图和元件之间的交互强度。Math n 次 m / math 矩阵 math { b } / math 识别由外部控制器控制的节点。系统通过控制器强加给系统的时变输入向量 math { u }(t)(u 1(t) ，ctdots，u m (t)) ^ mathrm { t } / math 来控制。为了确定驱动节点的最小数目，用数学 n mathrum { d } / math 表示，其控制足以完全控制系统的动力学，Liu 等人。试图结合结构控制理论，图论和统计物理学的工具。他们出现了
It is also notable, that Liu's et al. formulation<ref name="Liu-Nature-11"/> would predict same values of <math>{n_\mathrm{D}}</math> for a chain graph and for a weak densely connected graph. Obviously, both these graphs have very different in and out degree distributions. A recent unpublished work,<ref name = "Arxiv_Close_Betw">{{cite arXiv|first=SJ |last=Banerjee |first2=S |last2=Roy|title=Key to Network Controllability|eprint=1209.3737}}</ref> questions whether [[Degree (graph theory)|degree]], which is a purely local measure in networks, would completely describe controllability and whether even slightly distant nodes would have no role in deciding network controllability. Indeed, for many real-word networks, namely, food webs, neuronal and metabolic networks, the mismatch in values of <math>{n_\mathrm{D}}^{real}</math> and <math>{n_\mathrm{D}}^\mathrm{rand\_degree}</math> calculated by Liu et al.<ref name="Liu-Nature-11"/> is notable. If controllability is decided mainly by degree, why are <math>{n_\mathrm{D}}^{real}</math> and <math>{n_\mathrm{D}}^\mathrm{rand\_degree}</math> so different for many real world networks? They argued <ref name="Liu-Nature-11"/> (arXiv:1203.5161v1), that this might be due to the effect of degree correlations. However, it has been shown<ref name = "Arxiv_Close_Betw"/> that network controllability can be altered only by using [[betweenness centrality]] and [[closeness centrality]], without using [[degree (graph theory)]] or degree correlations at all.
It is also notable, that Liu's et al. formulation questions whether degree, which is a purely local measure in networks, would completely describe controllability and whether even slightly distant nodes would have no role in deciding network controllability. Indeed, for many real-word networks, namely, food webs, neuronal and metabolic networks, the mismatch in values of <math>{n_\mathrm{D}}^{real}</math> and <math>{n_\mathrm{D}}^\mathrm{rand\_degree}</math> calculated by Liu et al. is notable. If controllability is decided mainly by degree, why are <math>{n_\mathrm{D}}^{real}</math> and <math>{n_\mathrm{D}}^\mathrm{rand\_degree}</math> so different for many real world networks? They argued (arXiv:1203.5161v1), that this might be due to the effect of degree correlations. However, it has been shown that network controllability can be altered only by using betweenness centrality and closeness centrality, without using degree (graph theory) or degree correlations at all.
同样值得注意的是，刘的等人。度是网络中一种纯粹的局部度量，它是否能完全描述网络的可控性，即使是稍微远一点的节点在决定网络的可控性方面是否没有作用。事实上，对于许多实词网络，即食物网络、神经元网络和代谢网络，Liu 等人计算的数学数学和数学数学的值不匹配。值得注意的是。如果可控性主要是由程度决定的，那么为什么对于许多现实世界的网络来说，数学、数学和数学如此不同？他们认为(arXiv: 1203.5161 v1) ，这可能是由于度相关性的影响。然而，研究表明，网络的可控性只能通过介于中心性和接近中心性之间来改变，完全不需要度(图论)或度相关性。
[[File:YYL2.pdf|right|thumb|A schematic diagram shows the control of a directed network. For a given directed network (Fig. a), one calculates its maximum matching: a largest set of edges without common heads or tails. The maximum matching will compose of a set of vertex-disjoint directed paths and directed cycles (see red edges in Fig.b). If a node is a head of a matching edge, then this node is matched (green nodes in Fig.b). Otherwise, it is unmatched (white nodes in Fig.b). Those unmatched nodes are the nodes one needs to control, i.e. the driver nodes. By injecting signals to those driver nodes, one gets a set of directed path with starting points being the inputs (see Fig.c). Those paths are called "stems". The resulting digraph is called U-rooted factorial connection. By "grafting" the directed cycles to those "stems", one gets "buds". The resulting digraph is called the cacti (see Fig.d). According to the structural controllability theorem,<ref name="Lin-74"/> since there is a cacti structure spanning the controlled network (see Fig.e), the system is controllable. The cacti structure (Fig.d) underlying the controlled network (Fig.e) is the "skeleton" for maintaining controllability.]]
A schematic diagram shows the control of a directed network. For a given directed network (Fig. a), one calculates its maximum matching: a largest set of edges without common heads or tails. The maximum matching will compose of a set of vertex-disjoint directed paths and directed cycles (see red edges in Fig.b). If a node is a head of a matching edge, then this node is matched (green nodes in Fig.b). Otherwise, it is unmatched (white nodes in Fig.b). Those unmatched nodes are the nodes one needs to control, i.e. the driver nodes. By injecting signals to those driver nodes, one gets a set of directed path with starting points being the inputs (see Fig.c). Those paths are called "stems". The resulting digraph is called U-rooted factorial connection. By "grafting" the directed cycles to those "stems", one gets "buds". The resulting digraph is called the cacti (see Fig.d). According to the structural controllability theorem, since there is a cacti structure spanning the controlled network (see Fig.e), the system is controllable. The cacti structure (Fig.d) underlying the controlled network (Fig.e) is the "skeleton" for maintaining controllability.
示意图显示了一个有向网络的控制。对于给定的有向网络(图)。A) ，计算它的最大匹配: 没有共同的正面或反面的最大边集。最大匹配将由一组顶点不相交的有向路径和有向循环组成(见图 b 中的红边)。如果一个节点是匹配边的头部，则匹配该节点(图 b 中的绿色节点)。否则，它是不匹配的(图 b 中的白色节点)。那些不匹配的节点是需要控制的节点，即。驱动节点。通过向这些驱动节点注入信号，可以获得一组有向路径，起始点作为输入(参见图 c)。这些路径被称为“茎”。由此产生的有向图称为根 u 阶乘连接。通过“嫁接”那些“茎”的定向循环，一个人得到“芽”。得到的有向图称为 cacti (见图 d)。根据结构能控性定理，由于存在跨越受控网络的 cacti 结构(见图 e) ，系统是可控的。控制网络(Fig.e)底层的 cacti 结构(Fig.d)是维持可控性的“骨架”。
===Structural Controllability===
The concept of the structural properties was first introduced by Lin (1974)<ref name="Lin-74">C.-T. Lin, ''IEEE Trans. Auto. Contr.'' '''19'''
The concept of the structural properties was first introduced by Lin (1974)<ref name="Lin-74">C.-T. Lin, IEEE Trans. Auto. Contr. 19
结构性质的概念最早是由 Lin (1974) ref name"Lin-74"c. t. Lin，IEEE Trans。自动。女名女子名。19
(1974).</ref> and then extended by Shields and Pearson (1976)<ref name="Shields-76">R. W. Shields and J. B. Pearson, ''IEEE Trans. Auto. Contr.'' '''21'''
(1974).</ref> and then extended by Shields and Pearson (1976)<ref name="Shields-76">R. W. Shields and J. B. Pearson, IEEE Trans. Auto. Contr. 21
(1974) . / ref and then extended by Shields and Pearson (1976) ref name"Shields-76"r.希尔兹和 j。培生，IEEE Trans。自动。女名女子名。21
(1976).</ref> and alternatively derived by Glover and Silverman (1976).<ref name="Glover-76">K. Glover and L. M. Silverman, ''IEEE Trans. Auto. Contr.'' '''21'''
(1976).</ref> and alternatively derived by Glover and Silverman (1976).<ref name="Glover-76">K. Glover and L. M. Silverman, IEEE Trans. Auto. Contr. 21
(1976) . / ref 和另外由 Glover 和 Silverman (1976)派生。 ref name"Glover-76"k。格洛弗和 l. m. Silverman，IEEE Trans。自动。女名女子名。21
(1976).</ref> The main question is whether the lack of controllability or observability are generic with respect to the variable system parameters. In the framework of structural control the system parameters are either independent free variables or fixed zeros. This is consistent for models of physical systems since parameter values are never known exactly, with the exception of zero values which express the absence of interactions or connections.
(1976).</ref> The main question is whether the lack of controllability or observability are generic with respect to the variable system parameters. In the framework of structural control the system parameters are either independent free variables or fixed zeros. This is consistent for models of physical systems since parameter values are never known exactly, with the exception of zero values which express the absence of interactions or connections.
(1976年)。 / ref 主要的问题是，对于可变系统参数来说，缺乏可控性或可观测性是否是一般性的。在结构控制的框架下，系统参数可以是独立自由变量，也可以是固定零点。这对于物理系统的模型是一致的，因为参数值永远不会准确地知道，零值除外，零值表示交互或连接的缺失。
===Maximum Matching===
In graph theory, a [[matching (graph theory)|matching]] is a set of edges without common vertices. Liu et al.<ref name="Liu-Nature-11"/> extended this definition to directed graph, where a matching is a set of directed edges that do not share start or end vertices. It is easy to check that a matching of a directed graph composes of a set of vertex-disjoint simple paths and cycles. The maximum matching of a directed network can be efficiently calculated by working in the bipartite representation using the classical [[Hopcroft–Karp algorithm]], which runs in O(''E''{{radic|''N''}}) time in the worst case. For undirected graph, analytical solutions of the size and number of maximum matchings have been studied using the [[cavity method]] developed in statistical physics.<ref name="Zdeborova-06">[[Lenka Zdeborová|L. Zdeborová]] and M. Mezard, ''J. Stat. Mech.'' '''05''' (2006).</ref> Liu et al.<ref name="Liu-Nature-11"/> extended the calculations for directed graph.
In graph theory, a matching is a set of edges without common vertices. Liu et al. Liu et al. extended the calculations for directed graph.
在图论中，匹配是一组没有共同顶点的边。刘等人。刘等人。扩展了有向图的计算。
By calculating the maximum matchings of a wide range of real networks, Liu et al.<ref name="Liu-Nature-11"/> asserted that the number of driver nodes is determined mainly by the networks degree distribution <math>P(k_\mathrm{in}, k_\mathrm{out})</math>. They also calculated the average number of driver nodes for a network ensemble with arbitrary degree distribution using the [[cavity method]]. It is interesting that for a chain graph and a weak densely connected graph, both of which have very different in and out degree distributions; the formulation of Liu et al.<ref name="Liu-Nature-11"/> would predict same values of <math>{n_\mathrm{D}}</math>. Also, for many real-word networks, namely, food webs, neuronal and metabolic networks, the mismatch in values of <math>{n_\mathrm{D}}^{real}</math> and <math>{n_\mathrm{D}}^\mathrm{rand\_degree}</math> calculated by Liu et al.<ref name="Liu-Nature-11"/> is notable. If controllability is decided purely by degree, why are <math>{n_\mathrm{D}}^{real}</math> and <math>{n_\mathrm{D}}^\mathrm{rand\_degree}</math> so different for many real world networks? It remains open to scrutiny whether ''control robustness" in networks is influenced more by using [[betweenness centrality]] and [[closeness centrality]]<ref name = "Arxiv_Close_Betw"/> over [[degree (graph theory)]] based metrics.
By calculating the maximum matchings of a wide range of real networks, Liu et al. asserted that the number of driver nodes is determined mainly by the networks degree distribution <math>P(k_\mathrm{in}, k_\mathrm{out})</math>. They also calculated the average number of driver nodes for a network ensemble with arbitrary degree distribution using the cavity method. It is interesting that for a chain graph and a weak densely connected graph, both of which have very different in and out degree distributions; the formulation of Liu et al. would predict same values of <math>{n_\mathrm{D}}</math>. Also, for many real-word networks, namely, food webs, neuronal and metabolic networks, the mismatch in values of <math>{n_\mathrm{D}}^{real}</math> and <math>{n_\mathrm{D}}^\mathrm{rand\_degree}</math> calculated by Liu et al. is notable. If controllability is decided purely by degree, why are <math>{n_\mathrm{D}}^{real}</math> and <math>{n_\mathrm{D}}^\mathrm{rand\_degree}</math> so different for many real world networks? It remains open to scrutiny whether control robustness" in networks is influenced more by using betweenness centrality and closeness centrality over degree (graph theory) based metrics.
通过计算各种实际网络的最大匹配，刘等人提出了一种新的网络匹配算法。断言驱动节点数主要由网络度分布数学 p (k，k，k) / 数学决定。他们还利用空腔法计算了任意度分布的网络集成的平均驱动节点数。有趣的是，对于链图和弱紧连通图，它们的内外度分布都有很大的不同。可以预测相同的数学数值。此外，对于许多实词网络，即食物网络、神经元网络和代谢网络，Liu 等人计算出的数学函数 d ^ 实数 / 数学和数学函数 d ^ 实数 / 数学的值不匹配。值得注意的是。如果可控性纯粹是由程度决定的，那么为什么对于许多现实世界的网络来说，数学、数学和数学如此不同？网络中的控制鲁棒性是否受基于度的度量中介中心性和贴近中心性的影响仍有待进一步研究。
While sparser graphs are more difficult to control,<ref name="Liu-Nature-11"/><ref name = "Arxiv_Close_Betw"/> it would obviously be interesting to find whether [[betweenness centrality]] and [[closeness centrality]]<ref name = "Arxiv_Close_Betw"/> or degree heterogeneity<ref name="Liu-Nature-11"/> plays a more important role in deciding controllability of sparse graphs with almost similar degree distributions.
While sparser graphs are more difficult to control, it would obviously be interesting to find whether betweenness centrality and closeness centrality or degree heterogeneity plays a more important role in deciding controllability of sparse graphs with almost similar degree distributions.
尽管稀疏图的可控性难以控制，但是研究具有几乎相似度分布的稀疏图的可控性中，是否存在介于介于中间中心性和封闭中心性或度异质性起着更重要的作用显然是很有意义的。
==Control of composite quantum systems and algebraic graph theory==
A control theory of networks has also been developed in the context of universal control for composite quantum systems, where subsystems and their interactions are associated to nodes and links, respectively.<ref name="BG-07">{{cite journal | last=Burgarth | first=Daniel | last2=Giovannetti | first2=Vittorio | title=Full Control by Locally Induced Relaxation | journal=Physical Review Letters | publisher=American Physical Society (APS) | volume=99 | issue=10 | date=2007-09-05 | issn=0031-9007 | doi=10.1103/physrevlett.99.100501 | page=100501| arxiv=0704.3027 }}</ref> This framework permits to formulate Kalman's criterion with tools from [[algebraic graph theory]] via the [[minimum rank of a graph]] and related notions.<ref name="BDHSY-13">{{cite journal|last1=Burgarth|first1=Daniel|last2=D'Alessandro|first2=Domenico|last3=Hogben|first3=Leslie|author3-link=Leslie Hogben|last4=Severini|first4=Simone|last5=Young|first5=Michael|doi=10.1109/TAC.2013.2250075|issue=9|journal=IEEE Transactions on Automatic Control|mr=3101617|pages=2349–2354|title=Zero forcing, linear and quantum controllability for systems evolving on networks|volume=58|year=2013}}</ref><ref name="OT-15">S. O'Rourke, B. Touri, https://arxiv.org/abs/1511.05080.</ref>
A control theory of networks has also been developed in the context of universal control for composite quantum systems, where subsystems and their interactions are associated to nodes and links, respectively. This framework permits to formulate Kalman's criterion with tools from algebraic graph theory via the minimum rank of a graph and related notions.
在复合量子系统的通用控制的背景下，也发展了网络控制理论，其中子系统及其相互作用分别与节点和链路相关联。这个框架允许用代数图论的工具通过图的最小秩和相关概念来建立卡尔曼准则。
== See also ==
* [[Controllability Gramian]]
==References==
<references/>
== External links ==
* [http://barabasilab.neu.edu/projects/controllability/ The network controllability project website]
* [https://www.youtube.com/watch?v=9-q2qpOJfkg The video showing network controllability]
<!--- Categories --->
<!--- Categories --->
!-类别-
[[Category:Network theory]]
Category:Network theory
范畴: 网络理论
<noinclude>
<small>This page was moved from [[wikipedia:en:Network controllability]]. Its edit history can be viewed at [[网络可控性/edithistory]]</small></noinclude>
[[Category:待整理页面]]