复杂网络的可控性

复杂网络的可控性已有2783次阅读2011-6-1322:34|个人分类:复杂网络|系统分类:科研笔记|关键词:复杂网络前不久，nature上发表了一篇关于研究复杂网络的可控性的文章。这篇文章结合了工程控制论的思想和复杂网络的研究，开辟了一种帮助我们进一步理解复杂系统的新方法（这是文章自己的说法，但是关于有向网络的可控性研究，据我所知，在2010年就已经有人研究过了）。复杂系统涉及多个组分（如基因调控过程中的基因、蛋白质等分子，或者社交网络中的人物账号等）和这些组分之间的关系。一般的建模方法，如常微分方程等，由于受限于计算能力或者是建模对象本身的模糊性，已经不能对这种大规模的复杂系统进行建模。而复杂网络是对复杂系统建模的一种有效的方法。复杂网络的节点表示的是复杂系统中的多个组分的某种量化性质，如基因调控网络中基因的激活/抑制状态、社交网络中账号的状态等；复杂网络的变表示节点之间的某种联系或者是共享某种信息，如基因网络中A——〉B表示基因A的产物会促进基因B的表达、社交网络中C——〉D表示账号D的动态会和账号C共享。我们研究复杂系统的最终目标是希望能对它们进行控制。如基因药物的靶标选取问题，选择哪个基因（基因调控网络中的节点）作为药物的靶标，能使得整个生物系统达到一个我们期望的状态呢？还有社交网络中,我们选取那个节点作为信息的发布点对整个社交网络产生我们想要的宣传效果呢？这些都可以抽象为如何对一个表示状态的复杂网络进行有效地控制，从而使得整个网络进入我们期望的状态。这篇文章最开始的出发点是研究复杂有向网络的可控性。众所周知，我们若是能对整个网络中的每一个节点输入一个控制信号，那么整个网络是可控的。但是对于一个大规模的复杂系统，这是很难实现的。作者希望能找到最少的控制节点（文章中称为驱动节点‘drivernodes）来有效地控制整个网络。作者采用的是比较古老的“最大匹配”方法（这是基于将整个网络看成一个线性系统的）寻找最小的驱动节点数Nd。并将这种方法用于几个基于对象建模的真实网络和一群ER随机网络以及一群度分布和真实网络相同的随机网络，通过比较得到的最小驱动节点数，作者发现最新驱动节点数主要是由于网络的度分布性质确定的。接着作者根据这一发现以及cavitymethod推导出了一组自稳定的方程组，度分布为自变量，最小驱动节点数为所求的结果。这篇文章有两个研究成果都是与我们预想的结果是相反的，一是复杂网络中的驱动节点一般不是网络的hub；二是稀疏的异质网络是最难控制的而致密的同质网络是比较容易控制的。这篇文章的研究还发现我们本以为难以控制的具有个体独立性的社交网络相比于其他的网络模型，如基因调控网络等，却是相对比较容易控制的。这篇文章的成果是显著的，但是如何将文中的理论用于实际，如何将研究框架扩展到非线性系统。这仍是有待我们的研究的。/nature/journal/v473/n7346/full/naturelOOll.html#/comments前不久，我写过一篇关于我研读nature上发表的“ControllabilityofComplexNetwork”的文章(/home.php?mod=space&uid=545746&do=blog&id=454884)。当时只是自己感性上觉得这篇文章很有用，会对将来各种复杂网络的研究产生较大的影响。但由于暂时我还没有看到相关的重要的后续研究出现，对于其是否将产生比较重大的影响，我还有些怀疑。今天在Science上看到了一篇关于这篇文章的一篇评论/content/332/6031/777.full我不禁感觉这条路前面的灯亮了。有一些专家学者都认为Yang-YuLiu等人的工作是非常重要的：香港城市大学的GuanrongChen认为：实际中大部分网络都是有向网络，相比以前人们对无向网络的研究，这项工作比以往的网络控制研究都更具有通用型和实际价值，寻找drivernodes的算法是非常重要的，因为它很有用。丹麦科技大学的生物学家RuneLinding认为这篇文章的算法可用于解读细胞内生化相互作用网络，如可以作为研究控制激酶磷酸化网络的框架。另外此项研究还可用于控制生物机器人，如控制虫新杆状线虫的297个神经细胞中的49个来对这个生物机器人实现必要的控制。另外这篇文章将泰斗级控制论专家Jean-JacquesSlotine和网络领军人物之一Barabas联合在一起，十分给力这条路的后续发展。复杂网络的严格可控性一一强悍的特征值又回来了已有1139次阅读2013-9-2714:16|系统分类:论文交流|关键词:网络，可控性控制一个系统是非线性研究中的一个重要问题。如何控制一个系统呢？首要问题是需要多少外界信号的输入，也就是满足可控性条件的控制器个数问题。然而这是一个很难事先根据Kalman条件得到的问题,2011年Liu等在Nature上发表论文Controllabilityofcomplexnetworks，利用最大匹配理论解决了复杂网络的结构可控性问题。他们提出一个系统结构可

控需要的独立控制器（Driver）为系统非匹配节点数（完美匹配时为系统任意一个节点），并且Driver数与网络度分布存在密切关联。最近我们在NatureCommunications上发表论文Exactcontrollabilityofcomplexnetworks，给出了网络严格可控性的相关结论。我们从可控性的PBH条件（与Kalman条件等价）入手，得到网络严格可控性所需要的Driver数为系统特征值的最大几何重数；当系统矩阵可对角化（比如对称）时，退化为系统特征值的最大代数重数。进一步在分析稀疏和致密网络时发现，稀疏网络最大几何重数出现在零特征值上，从而对稀疏网络就可直接由系统矩阵的秩来决定Driver数；而对于同权致密网络，最大几何重数出现在负权值上，同样可直接对同权网络简单计算Driver数。仿真实验说明了对稀疏和致密网络简单计算的正确性，同时发现同权网络越致密越难控制（Driver数越大）。0.01.0000.60.000riy安冲0.0040.9961.00.S0.00.0000.004WEW=担P0.0000.0040.9961.000Figure0.01.0000.60.000riy安冲0.0040.9961.00.S0.00.0000.004WEW=担P0.0000.0040.9961.000Figure2\Exactcontrollabilityofundirectednetwork乩Exs匚tcontrollabilityrnc?asurenDasafunctionofLRrandomnetworksEirid(b)ERrundomnetworkswithrandomweightsassignedtolinks(WER)t(c)r?匚：vforNewman-Wattssmall-worldnetworks,(d)nDversushalfoftheaveragedegreeforBarab^si-jundirectedandtheircouplingmatricesaresyrnmetri匚.ThedatapointsareobtainedfromtheMMlLequalfrom20independentrealtzations.Thecurves(SoD)arethetheormti匸戒predictionsofequations(5)and(TherepresentativenetworksizesusedareW=1,000,2,000zind5,000.di.oo.s0.0BA曙肚肚1234另外，我们还可以通过线性代数中初等变换的方法求的网络需要Driver的节点。该方法简单易行，复杂度约为0(N人2(logNH2)。EigenvaluesTransformation曲)=3FigureEigenvaluesTransformation曲)=3Figure1|lllustratianofttwexactcontrollabilityframeworktoidentifynminimumsetofdrivers(a)Asimpleundire匚t色dnetworkwithself-ioops,(b)日simpledirectednetworkand(c)anundirectednetworkwithdenseconnectio门乩ThematrixA―thecolumn匚anoni匚曲formofmatrixA—bytheelementarycolumntransformation,theeigenvalues2andtheeigenvalue匚oir^HporicIin呂tothemaximumgeometricmultiplicityp(zM)ofAaregivenforeachsimplenetwork.Therowsthatarelinearlydependentonothersinthe匚olumncanonicalformaremarkedbyred.Thenodescorrespondingtothemarethedriversthataremarkedbyredaswellinthenetworks.Fortheundire匚t&dnetworksin□andc,isequaltothemaximumalgebraicmultipli亡it卅that曲themultiplicityof丿叫Theconfigurationofdriversisnotuniqueasitreliesontheelementarycolumntransformatio