复杂网络可控性分析与驱动节点集拓扑性质研究

摘要

现实世界中的诸多系统都以有向复杂网络形式存在，要保证这些系统的正常运作，就必须对整个系统进行控制。如果系统能在规定的时间内从任意一个初始状态驱动到任意理想的最终状态，则称其为可控的。若是能单独控制网络中的每个节点，那么整个网络是可控的，但这对于一个大规模的复杂系统来说是很难实现的，希望能寻找最少的节点来控制整个网络。把复杂网络映射到线性系统上，利用二分图的最大匹配算法，非匹配节点作为驱动节点。通过对驱动节点输入外部信号来实现对复杂网络的控制。
　　本文基于二分图的最大匹配算法对复杂网络可控性进行了研究，主要分析驱动节点集和核心驱动节点的性质。首先利用度大的节点优先匹配算法和度小的节点优先匹配算法，研究实际网络和模型网络中驱动节点集合平均度的变化规律，考察不同驱动点集合的拓扑特征。其次对网络的节点随机排序，通过随机抽样的方法多次计算驱动节点集合，研究不同驱动节点集合的个数及其性质，并与网络的度分布曲线进行对比，并研究驱动节点集合交集节点的性质以及对网络控制性的影响，总结了网络控制的原理。然后把网络的节点和边依据其在网络控制性的作用分为三类，分析不同类型的节点对网络控制的影响。最后计算网络中各节点在驱动节点集中出现的次数，并给出核心驱动节点的定义及求解方法，分析其性质以及在网络控制中的作用。
　　通过对驱动节点集性质的分析研究，本文发现网络驱动节点集的平均度变化范围较大，某些网络驱动节点集的平均度明显高于网络的平均度。所以认为驱动点避开高度节点的结论是不精确的。通过分析网络中各节点在驱动节点出现的次数，发现复杂网络的控制是通过控制低度节点来影响高度节点从而控制整个网络。

目录

声明

摘要

第1章 绪论

1．1 研究背景及意义

1．2 国内外研究现状

1．3 主要研究内容

1．4 论文组织结构

第2章 相关技术

2．1 复杂网络概述

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

2．1．2 常见复杂网络模型

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 Hopcroft-Karp算法

2．4 本章小结

第3章 复杂网络驱动节点拓扑分析

3．1 问题描述

3．2 相关定义

3．3 优先匹配算法驱动节点集平均度分析

3．3．1 最大匹配算法

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

3．3．3 复杂网络的驱动节点分布

3．3．4 驱动节点集合平均度

3．4 节点随机排序算法驱动节点集平均度分析

3．4．1 算法描述

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

3．5 本章小结

第4章 复杂网络核心驱动节点集分析

4．1 问题描述

4．2 网络节点分类及边分类

4．2．1 节点分类及边分类

4．2．2 实验结果与分析

4．3 核心驱动节点集特征

4．3．1 算法描述

4．3．2 核心驱动节点与分类后节点的交集情况

4．4 节点在驱动节点集中的出现分布特征

4．5 本章小结

第5章 总结与展望

5．1 工作总结

5．2 进一步研究工作

参考文献

致谢

攻读硕士期间参加的科研项目