本文以网络鲁棒性最小化为图分割目标,进行关键节点挖掘,寻找对于维持网络结构有重要意义的节点。此问题在实际应用中有重要意义,识别网络中的重要节点,能让我们在传染病网络中更好地控制疾病传播,在电力网中更高效地维护基础设施等。由于关键节点挖掘在实际中的重要价值,其成为了复杂网络研究中的热点问题。本文深入分析了网络鲁棒性的性质,并提出了规划反向目标算法。之后改进了鲁棒性指标的定义,并基于新定义提出了一种新的关键节点挖掘算法。本文的主要研究内容和创新点如下:(1)本文深入分析了网络鲁棒性的定义和性质。证明了网络鲁棒性的取值范围,证明了其最优序列特性和结合律。最优序列特性表明最优序列每次选取的节点必定在网络当前的最大连通分支中。结合律表明了在符合最优序列特征的条件下,可以用网络各部分的结果直接计算合成网络的结果。(2)基于网络鲁棒性的分析,提出了规划反向目标算法。规划反向目标算法中引入了社团发现方法,先探测网络的结构,将网络中的节点分为社团内部节点和社团边缘节点。根据节点类型的不同,然后进行关键节点挖掘。最后使用移除节点序列优化方法对已获得结果进行优化,得到最终结果。此方法和其他常见方法相比,取得了较好的结果。(3)本文指出传统鲁棒性指标的不足,提出了新鲁棒性指标的定义,并证明了新鲁棒性指标的各种性质。网络鲁棒性标准主要关注网络的最大连通分支,没有考虑到节点之间的差异,其不能很好地应用于有节点权重的网络。新网络鲁棒性考虑了节点权重。本文深入分析了新网络鲁棒性的取值范围特点、最优序列特征、结合律等特性,并比较了其与原有网络鲁棒性在这些特性上异同。证明了两种定义的兼容性。(4)基于新网络鲁棒性指标,本文提出了新反向目标算法,从而能更好地挖掘出网络中的关键节点。新反向目标算法将最小化关键连通分支重要性作为贪心目标。在多个实际网络和模型网络中,新反向目标算法都获得了较好的结果。本文分析了实验结果差异产生的原因。从概率论的角度,证明了在网络趋于无穷大时,在任意的网络结构下,在任意的节点权重随机分布下,对于任意的节点移除序列,其新网络鲁棒性值收敛到原有网络鲁棒性值。