1,068
个编辑
更改
跳到导航
跳到搜索
第7行：
第7行： − + + − Controlling a simple network. − − 图1：控制一个简单的网络。 − − − − '''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. − − '''<font color="#FF8000">网络可控性 Network Controllability </font>'''研究的是网络的结构可控性。可控性描述了我们在有限时间内，通过合适的输入选择，引导动力系统从任何初始状态到任何期望的最终状态的能力。这个定义与我们直观的控制概念非常吻合。一般的有向加权复杂网络的可控性是近年来世界范围内许多研究小组的重点研究课题。夏尔马<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> 等人最近在多种生物学网络(基因-基因、 miRNA-基因、蛋白质-蛋白质相互作用网络)上的研究，确定了骨肉瘤表现型特征的控制目标，显示了基因和蛋白质在维持肿瘤微环境中的重要作用。 − − − − ==背景 Background== − − Consider the canonical linear time-invariant dynamics on a complex network − − Consider the canonical linear time-invariant dynamics on a complex network + 第34行：
第17行： − − − 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>. − − 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>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>+ − The <math>N \times N</math>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 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. 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. − <math>N \times N</math> 的矩阵 <math>\mathbf{A}</math> 描述了系统的连接图以及各组分之间的交互强度。<math>N \times M</math> 矩阵 <math>\mathbf{B}</math> 列出了由外部控制器控制的节点。控制器通过施加给系统的时间相关向量 <math>\mathbf{u}(t) = (u_1(t),\cdots,u_M(t))^\mathrm{T}</math> 来实现对系统的控制。为了确定驱动节点的最小数目，<math>N_\mathrm{D}</math>，亦即确定对最少几个节点施加控制便足以完全控制系统的动力学进程，在这方面，Liu等人尝试了'''<font color="#FF8000">将结构控制理论 Structural Control Theory </font>'''、'''<font color="#FF8000">图论 Graph Theory </font>'''和'''<font color="#FF8000">统计物理 Statistical Physics </font>'''的工具的结合。<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> 他们发现，完全控制一个网络所需要的最少输入或驱动节点，取决于网络的'''<font color="#FF8000">最大匹配 maximum matching</font>'''，也就是不共享起始顶点和终止顶点的最大边集。从这个结论出发，一个基于''入-出度分布''的分析框架被开发出来，用于预测'''<font color="#FF8000">无标度网络 scale-free network</font>'''和'''<font color="#FF8000">ER随即图 Erdős–Rényi Graph</font>'''的<math>n_\mathrm{D} =N_\mathrm{D}/N </math>值。 − --[[用户:Qige96|Ricky]]：“ 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.”这句读不懂，怀疑有语法错误。+ − − − 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. − − 同样值得关注的是，刘等人的工作<ref name="Liu-Nature-11"/>提出了这么一个问题：'''<font color="#FF8000">度 Degree </font>''',作为网络中一种纯粹的局部度量，能否完全描述网络的可控性？是不是即便稍微远一点的节点，就对网络的可控性没有影响？事实上，对于许多'''<font color="#FF8000">现实世界里的网络 Real-World Networks </font>'''，像'''<font color="#FF8000">食物网络 Food Webs </font>'''、'''<font color="#FF8000">神经元网络 Neuronal Network </font>''' 和'''<font color="#FF8000">代谢网络 Metabolic Network </font>'''，Liu等人计算的<math>{n_\mathrm{D}}^{real}</math><math> 和 {n_\mathrm{D}}^\mathrm{rand\_degree}</math> 的值并不匹配。值得注意的是。如果可控性主要是由度决定，那么为什么对于许多现实世界的网络来说，<math>{n_\mathrm{D}}^{real}</math> 和 <math>{n_\mathrm{D}}^\mathrm{rand\_degree}</math> 如此不同？他们认为，这可能是由于度相关性的影响。然而，已有的研究表明，网络的可控性只能通过中间性和封闭性来改变，而完全不需要使用度（图论）或'''<font color="#FF8000">度相关性 Degree Correlations </font>'''。(arXiv:1203.5161v1) − − − − [[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），可以计算其最大匹配：没有共同头部或尾部的最大边集。最大匹配将由一组顶点不相交的有向路径和有向环组成（请参见图b中的红色边缘）。如果一个节点是匹配边的头部，则该节点是匹配的（图b中的绿色节点）。否则，它是不匹配的（图b中的白色节点）。那些不匹配的节点是需要施加控制的节点，即驱动节点。通过向这些驱动节点注入信号，可以得到一组以起点为输入的有向路径（见图c）。这些路径被称为“茎”。得到的有向图称为U根因子连接。通过将定向周期“嫁接”到那些“茎”，人们就会得到“芽”。得到的有向图称为'''仙人掌 cacti'''（见图d）。根据结构可控性定理，由于存在跨越受控网络的cacti结构（参见图e），因此该系统是可控的。受控网络（图e）下的cacti结构（图d）是维持可控性的“骨架”。]] − − − − − 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. Auto. Contr.'' '''19'''(1974).</ref> 提出的，然后由 Glover 和 Silverman (1976)扩展。 <ref name="Shields-76">R. W. Shields and J. B. Pearson, ''IEEE Trans. Auto. Contr.'' '''21'''(1976).</ref>主要的问题是，对于可变系统参数来说，缺乏可控性或可观测性是否是普遍存在的现象。在结构控制的框架里，系统参数要么是独立自由变量，要么是固定的0。这对于物理系统的模型是一致的，因为参数值永远不会准确地获得，零值除外，零值代表没有交互和连接。 − + − − 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.<br> − + − 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. − − − − − − 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== − 复合量子系统的控制与代数图论<br> − − 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== + − + − − − − − − <!--- 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> − − − 此词条暂由彩云小译翻译，未经人工整理和审校，带来阅读不便，请见谅。 − − 本词条由信白初步翻译 − − 本词条由[[用户:Qige96|Ricky]]审校。 − − [[Category:待整理页面]] 第158行：
第65行： − + − 本课程中，以 Koch Curve 和 Box Counting 为例，讲解分形与分形维数。 − ====[https://campus.swarma.org/course/760 分形的世界]==== − 本课程中，主要介绍了分形现象、分形维数、利用分形规律的计算方法以及混沌。 第167行：
第71行： − 本中文词条由Jie参与编译，AvecSally审校，糖糖、[[用户:薄荷|薄荷]]编辑，如有问题，欢迎在讨论页面留言。+ +
无编辑摘要
[[Image:YYL1.png|right|thumb|Controlling a simple network.]]
[[Image:YYL1.png|right|thumb|图1：控制一个简单的网络。]]
'''<font color="#FF8000">网络可控性 Network Controllability </font>'''研究的是网络的结构可控性。可控性描述了我们在有限时间内，通过合适的输入选择，引导动力系统从任何初始状态到任何期望的最终状态的能力。这个定义与我们直观的控制概念非常吻合。一般的有向加权复杂网络的可控性是近年来世界范围内许多研究小组的重点研究课题。夏尔马<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>等人最近在多种生物学网络(基因-基因、 miRNA-基因、蛋白质-蛋白质相互作用网络)上的研究，确定了骨肉瘤表现型特征的控制目标，显示了基因和蛋白质在维持肿瘤微环境中的重要作用。
== 背景 ==
考虑'''<font color="#FF8000">复杂网络 Complex Network </font>'''上的经典线性时不变动力学
考虑'''<font color="#FF8000">复杂网络 Complex Network </font>'''上的经典线性时不变动力学
\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>
其中，向量 <math>\mathbf{X}(t)=(x_1(t),\cdots,x_N(t))^\mathrm{T}</math> 表示在 <math>N</math> 个节点的系统时间 <math>t</math>时的状态。
其中，向量 <math>\mathbf{X}(t)=(x_1(t),\cdots,x_N(t))^\mathrm{T}</math> 表示在 <math>N</math> 个节点的系统时间 <math>t</math>时的状态。
<math>N \times N</math> 的矩阵 <math>\mathbf{A}</math> 描述了系统的连接图以及各组分之间的交互强度。<math>N \times M</math> 矩阵 <math>\mathbf{B}</math> 列出了由外部控制器控制的节点。控制器通过施加给系统的时间相关向量 <math>\mathbf{u}(t) = (u_1(t),\cdots,u_M(t))^\mathrm{T}</math> 来实现对系统的控制。为了确定驱动节点的最小数目，<math>N_\mathrm{D}</math>，亦即确定对最少几个节点施加控制便足以完全控制系统的动力学进程，在这方面，Liu等人尝试了'''<font color="#FF8000">将结构控制理论 Structural Control Theory </font>'''、'''<font color="#FF8000">图论 Graph Theory </font>'''和'''<font color="#FF8000">统计物理 Statistical Physics </font>'''的工具的结合。<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> 他们发现<ref name="Liu-Nature-11"/>，完全控制一个网络所需要的最少输入或驱动节点，取决于网络的'''<font color="#FF8000">最大匹配 maximum matching</font>'''，也就是不共享起始顶点和终止顶点的最大边集。从这个结论出发，一个基于''入-出度分布''的分析框架被开发出来，用于预测'''<font color="#FF8000">无标度网络 scale-free network</font>'''和'''<font color="#FF8000">ER随即图 Erdős–Rényi Graph<ref name="Liu-Nature-11"/> </font>'''的<math>n_\mathrm{D} =N_\mathrm{D}/N </math>值。<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>
同样值得关注的是，刘等人的工作<ref name="Liu-Nature-11"/>提出了这么一个问题<ref name = "Arxiv_Close_Betw">{{cite arXiv|first=SJ |last=Banerjee |first2=S |last2=Roy|title=Key to Network Controllability|eprint=1209.3737}}</ref> ：'''<font color="#FF8000">度 Degree </font>''',作为网络中一种纯粹的局部度量，能否完全描述网络的可控性？是不是即便稍微远一点的节点，就对网络的可控性没有影响？事实上，对于许多'''<font color="#FF8000">现实世界里的网络 Real-World Networks </font>'''，像'''<font color="#FF8000">食物网络 Food Webs </font>'''、'''<font color="#FF8000">神经元网络 Neuronal Network </font>''' 和'''<font color="#FF8000">代谢网络 Metabolic Network </font>'''，Liu等人计算的<math>{n_\mathrm{D}}^{real}</math><math> 和 {n_\mathrm{D}}^\mathrm{rand\_degree}</math> 的值并不匹配<ref name="Liu-Nature-11"/>。值得注意的是。如果可控性主要是由度决定，那么为什么对于许多现实世界的网络来说，<math>{n_\mathrm{D}}^{real}</math> 和 <math>{n_\mathrm{D}}^\mathrm{rand\_degree}</math> 如此不同？他们认为<ref name="Liu-Nature-11"/>，这可能是由于度相关性的影响。然而，已有的研究表明<ref name = "Arxiv_Close_Betw"/>，网络的可控性只能通过中间性和封闭性来改变，而完全不需要使用度（图论）或'''<font color="#FF8000">度相关性 Degree Correlations </font>'''。(arXiv:1203.5161v1)
[[File:YYL2.pdf|right|thumb|示意图显示了一个有向向网络的控制。对于给定的有向网络（图a），可以计算其最大匹配：没有共同头部或尾部的最大边集。最大匹配将由一组顶点不相交的有向路径和有向环组成（请参见图b中的红色边缘）。如果一个节点是匹配边的头部，则该节点是匹配的（图b中的绿色节点）。否则，它是不匹配的（图b中的白色节点）。那些不匹配的节点是需要施加控制的节点，即驱动节点。通过向这些驱动节点注入信号，可以得到一组以起点为输入的有向路径（见图c）。这些路径被称为“茎”。得到的有向图称为U根因子连接。通过将定向周期“嫁接”到那些“茎”，人们就会得到“芽”。得到的有向图称为'''仙人掌 cacti'''（见图d）。根据结构可控性定理，由于存在跨越受控网络的cacti结构（参见图e），因此该系统是可控的。受控网络（图e）下的cacti结构（图d）是维持可控性的“骨架”。]]
=== 结构可控性 ===
===结构可控性 Structural Controllability===
'''<font color="#FF8000">结构可控性 Structural Controllability </font><br>
'''<font color="#FF8000">结构可控性 Structural Controllability </font><br>
结构性质的概念最早是由 Lin (1974) <ref name="Lin-74">C.-T. Lin, ''IEEE Trans. Auto. Contr.'' '''19'''(1974).</ref> 提出的，然后由 Glover 和 Silverman (1976)扩展。 <ref name="Shields-76">R. W. Shields and J. B. Pearson, ''IEEE Trans. Auto. Contr.'' '''21'''(1976).</ref><ref name="Glover-76">K. Glover and L. M. Silverman, ''IEEE Trans. Auto. Contr.'' '''21'''(1976).</ref> 主要的问题是，对于可变系统参数来说，缺乏可控性或可观测性是否是普遍存在的现象。在结构控制的框架里，系统参数要么是独立自由变量，要么是固定的0。这对于物理系统的模型是一致的，因为参数值永远不会准确地获得，零值除外，零值代表没有交互和连接。
(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'''
(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> 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.
===最大匹配 Maximum Matching===
=== 最大匹配 ===
'''<font color="#FF8000">最大匹配 Maximum Matching </font>'''<br>
'''<font color="#FF8000">最大匹配 Maximum Matching </font>'''<br>
在图论中，匹配（图论）是一组没有共同顶点的边。Liu等人<ref name="Liu-Nature-11"/>将此定义扩展到有向图，其中匹配是一组不共享起始或终止顶点的有向边。很容易知道，有向图的匹配由一组顶点不相交的简单路径和周期组成。定向网络的最大匹配可以通过在'''<font color="#FF8000">二部图表示 Bipartite Representation </font>'''中使用经典的'''<font color="#FF8000">Hopcroft-Karp算法 </font>'''来高效地计算，该算法在最坏情况下的时间复杂度是O(''E''{{radic|''N''}})。对于无向图，统计物理中开发的'''<font color="#FF8000">空腔法 Cavity Method </font>'''研究了最大匹配的大小和数量的解析解。<ref name="Zdeborova-06">[[Lenka Zdeborová|L. Zdeborová]] and M. Mezard, ''J. Stat. Mech.'' '''05''' (2006).</ref>Liu等人<ref name="Liu-Nature-11"/>扩展了有向图的计算范围。
在图论中，匹配（图论）是一组没有共同顶点的边。Liu等人<ref name="Liu-Nature-11"/>将此定义扩展到有向图，其中匹配是一组不共享起始或终止顶点的有向边。很容易知道，有向图的匹配由一组顶点不相交的简单路径和周期组成。定向网络的最大匹配可以通过在'''<font color="#FF8000">二部图表示 Bipartite Representation </font>'''中使用经典的'''<font color="#FF8000">Hopcroft-Karp算法 </font>'''来高效地计算，该算法在最坏情况下的时间复杂度是O(''E''{{radic|''N''}})。对于无向图，统计物理中开发的'''<font color="#FF8000">空腔法 Cavity Method </font>'''研究了最大匹配的大小和数量的解析解。<ref name="Zdeborova-06">[[Lenka Zdeborová|L. Zdeborová]] and M. Mezard, ''J. Stat. Mech.'' '''05''' (2006).</ref>Liu等人<ref name="Liu-Nature-11"/>扩展了有向图的计算范围。
通过计算各种真实网络的最大匹配，Liu等人<ref name="Liu-Nature-11"/>断言驱动节点的数量主要由网络度分布<math>P(k_\mathrm{in}，k_\mathrm{out})</math>决定。他们还使用空腔方法计算了具有任意度分布的网络集合的驱动节点的平均数量。有趣的是，对于'''<font color="#FF8000">链图 Chain Graph </font>'''和'''<font color="#FF8000">弱密集连通图 Weak Densely Connected Graph </font>'''，两者都具有非常不同的进出度分布；Liu等人的公式<ref name="Liu-Nature-11"/>将会计算得出出<math>{n_\mathrm{D}}</math>的相同值。此外，对于许多真实世界地网络，即食物网、神经元和代谢网络，Liu等人计算的<math>{n_\mathrm{D}}^{real}</math> 和 <math>{n_\mathrm{D}}^\mathrm{rand\_degree}</math> 值的不匹配<ref name="Liu-Nature-11"/> 。值得注意的是，如果可控性纯粹由度决定，那为什么<math>{n_\mathrm{D}}^{real}</math>和<math>{n_\mathrm{D}}^\mathrm{rand\_degree}</math>对于许多现实世界的网络来说是如此不同？对于网络中的控制健壮性是否更多地受到基于度的'''<font color="#FF8000">中介中心性 Betweenness Centrality </font>'''和'''<font color="#FF8000">紧密度中心性 Closeness Centrality </font>'''<ref name = "Arxiv_Close_Betw"/>的影响，仍然是开放的。
通过计算各种真实网络的最大匹配，Liu等人<ref name="Liu-Nature-11"/>断言驱动节点的数量主要由网络度分布<math>P(k_\mathrm{in}，k_\mathrm{out})</math>决定。他们还使用空腔方法计算了具有任意度分布的网络集合的驱动节点的平均数量。有趣的是，对于'''<font color="#FF8000">链图 Chain Graph </font>'''和'''<font color="#FF8000">弱密集连通图 Weak Densely Connected Graph </font>'''，两者都具有非常不同的进出度分布；Liu等人的公式<ref name="Liu-Nature-11"/> 将会计算得出出<math>{n_\mathrm{D}}</math>的相同值。此外，对于许多真实世界地网络，即食物网、神经元和代谢网络，Liu等人计算的<math>{n_\mathrm{D}}^{real}</math> 和 <math>{n_\mathrm{D}}^\mathrm{rand\_degree}</math> 值的不匹配。值得注意的是。如果可控性纯粹由度决定，那为什么<math>{n_\mathrm{D}}^{real}</math>和<math>{n_\mathrm{D}}^\mathrm{rand\_degree}</math>对于许多现实世界的网络来说是如此不同？对于网络中的控制健壮性是否更多地受到基于度的'''<font color="#FF8000">中介中心性 Betweenness Centrality </font>'''和'''<font color="#FF8000">紧密度中心性 Closeness Centrality </font>'''的影响，仍然是开放的。
虽然'''<font color="#FF8000">稀疏图 Sparser Graph </font>'''更难以控制<ref name="Liu-Nature-11"/><ref name = "Arxiv_Close_Betw"/> ，但是，中介中心性和紧密度中心性<ref name = "Arxiv_Close_Betw"/>，或'''<font color="#FF8000">度异质性 Degree Heterogeneity </font>'''<ref name="Liu-Nature-11"/>在决定具有几乎相似的度分布的稀疏图的可控性中是否起更重要的作用？这是个有趣的问题。
虽然'''<font color="#FF8000">稀疏图 Sparser Graph </font>'''更难以控制<ref name="Liu-Nature-11"/><ref name = "Arxiv_Close_Betw"/> ，但是，中介中心性和紧密度中心性<ref name = "Arxiv_Close_Betw"/>，或'''<font color="#FF8000">度异质性 Degree Heterogeneity </font>'''<ref name="Liu-Nature-11"/>在决定具有几乎相似的度分布的稀疏图的可控性中是否起更重要的作用？这是个有趣的问题。
== 复合量子系统的控制与代数图论 ==
人们还开发了在复合量子系统的通用控制背景下的网络控制理论，其中子系统及其相互作用分别与节点和链路相关联<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>。该框架允许使用代数图论中的工具通过图的最小等级和相关概念来制定'''<font color="#FF8000">卡尔曼准则 Kalman's Criterion </font>'''。<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>
人们还开发了在复合量子系统的通用控制背景下的网络控制理论，其中子系统及其相互作用分别与节点和链路相关联<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>。该框架允许使用代数图论中的工具通过图的最小等级和相关概念来制定'''<font color="#FF8000">卡尔曼准则 Kalman's Criterion </font>'''。<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>
== 其他参考资料 ==
* 可控性格拉姆矩阵
== 参考文献 ==
<references/>
<references/>
== 相关链接 ==
== External links ==
* [http://barabasilab.neu.edu/projects/controllability/ 美国东北大学网络可控性项目网站]
* [http://barabasilab.neu.edu/projects/controllability/ 美国东北大学网络可控性项目网站]
* [https://www.youtube.com/watch?v=9-q2qpOJfkg 网络可控性演示视频]
* [https://www.youtube.com/watch?v=9-q2qpOJfkg 网络可控性演示视频]
===集智视频===
===集智视频===
====[https://campus.swarma.org/course/1341 Fractals]====
====[ht]====
----
----
本中文词条由信白初步参与编译，[[用户:Qige96|Ricky]]审校，糖糖编辑，如有问题，欢迎在讨论页面留言。
'''本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。'''
'''本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。'''
[[Category:经济计量学会研究员]]
[[Category:经济计量学会研究员]]