论文摘要
现实世界中的诸多系统都以有向复杂网络形式存在,要保证这些系统的正常运作,就必须对整个系统进行控制。把复杂网络映射到线性系统上,利用二分图的最大匹配算法,非匹配节点作为驱动节点,求得网络的最小驱动节点集,通过对最小驱动节点集中的驱动节点输入外部信号来实现对复杂网络的控制。但网络的最大匹配集并不唯一,由此得出的最小驱动节点集也并不唯一,如何找到网络的所有最小驱动节点集对于分析网络的可控性具有重要的意义。本文的主要工作内容包括两部分：1.提出了枚举复杂网络所有最小驱动节点集的算法。目前通过求网络的全部最大匹配集进而来求网络的所有最小驱动节点集的方法存在重复度大,效率低的弊端,提出并证明了最小驱动节点集反转定理和枚举定理；由此设计了网络中所有最小驱动节点集的枚举算法,并在实际网络上进行实验；结果表明,算法效率较最大匹配方法有较大提高。构建网络所有最小驱动节点集关系网,分析该生成网络的拓扑结构及对网络控制的影响。然后根据网络中的节点在所有最小驱动节点集中出现的情况将节点分为覆盖驱动节点、覆盖匹配节点和混合节点,分析了这三种节点的拓扑性质。2.提出了最小驱动节点集优化选取算法。通过将控制节点的代价赋为节点的权值,边的权值定义为其目的节点的权值,利用网络的最大权匹配算法求出网络的最大权匹配集,因为网络的总权值固定,从而得出了网络中控制代价最小的驱动节点集——最佳驱动节点集,并对最佳驱动节点集的性质进行分析。