更改

[[Image:YYL1.png|right|thumb|图1：控制一个简单的网络。]]

[[Image:330px-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">网络可控性 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-基因、蛋白质-蛋白质相互作用网络)上的研究，确定了骨肉瘤表现型特征的控制目标，显示了基因和蛋白质在维持肿瘤微环境中的重要作用。

同样值得关注的是，刘等人的工作<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)

同样值得关注的是，刘等人的工作<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）是维持可控性的“骨架”。]]

[[File:page1-330px-YYL2.pdf.jpg|right|thumb|示意图显示了一个有向向网络的控制。对于给定的有向网络（图a），可以计算其最大匹配：没有共同头部或尾部的最大边集。最大匹配将由一组顶点不相交的有向路径和有向环组成（请参见图b中的红色边缘）。如果一个节点是匹配边的头部，则该节点是匹配的（图b中的绿色节点）。否则，它是不匹配的（图b中的白色节点）。那些不匹配的节点是需要施加控制的节点，即驱动节点。通过向这些驱动节点注入信号，可以得到一组以起点为输入的有向路径（见图c）。这些路径被称为“茎”。得到的有向图称为U根因子连接。通过将定向周期“嫁接”到那些“茎”，人们就会得到“芽”。得到的有向图称为'''仙人掌 cacti'''（见图d）。根据结构可控性定理，由于存在跨越受控网络的cacti结构（参见图e），因此该系统是可控的。受控网络（图e）下的cacti结构（图d）是维持可控性的“骨架”。]]

=== 结构可控性 ===

=== 结构可控性 ===

结构性质的概念最早是由 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。这对于物理系统的模型是一致的，因为参数值永远不会准确地获得，零值除外，零值代表没有交互和连接。

结构性质的概念最早是由 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。这对于物理系统的模型是一致的，因为参数值永远不会准确地获得，零值除外，零值代表没有交互和连接。

=== 最大匹配 ===

=== 最大匹配 ===

在图论中，匹配（图论）是一组没有共同顶点的边。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"/>扩展了有向图的计算范围。