面向复杂网络可控性的最小驱动点集枚举及优化选取算法研究

摘要

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

目录

声明

摘要

第1章 绪论

1．1 研究背景及意义

1．2 国内外研究现状

1．3 主要研究内容

1．4 论文组织结构

第2章 相关技术

2．1 复杂网络概述

2．1．1 复杂网络分析指标

2．2 复杂网络可控性

2．2．1 线性时不变系统可控性

2．2．2 卡尔曼能控性

2．2．3 Lin结构可控性理论

2．2．4 最小输入原理

2．3 匹配

2．3．1 匹配的基本概念

2．3．2 匹配的基本定理

2．3．3 二分图最大匹配算法

2．4 本章小结

第3章 网络所有最小驱动节点集枚举算法

3．1 问题描述

3．2 相关定义

3．3 网络所有最小驱动节点集定理及证明

3．4 网络所有最小驱动节点集枚举算法

3．5 实验环境、数据集及参数设置

3．6 网络所有最小驱动节点集拓扑分析

3．6．1 网络所有最小驱动节点集生成网算法描述

3．6．2 实验结果与分析

3．7 网络节点分类及拓扑特性分析

3．7．1 算法描述

3．7．2 实验结果与分析

3．8 本章小结

第4章 复杂网络驱动节点集优化选取算法

4．1 问题描述

4．2 相关定义

4．3 复杂网络最佳驱动节点集算法

4．4 实验结果及分析

4．5 本章小结

第5章 总结与展望

5．1 工作总结

5．2 进一步研究工作

参考文献

致谢

攻读硕士学位期间的论文项目情况