论文部分内容阅读
复杂网络在自然界中普遍存在如社会网络、生物网络、电力网络等，复杂网络中对网络连通性有重要影响的那些节点通常被称为关键节点。关键节点识别问题(critical node detection problem, CNDP)是寻找特定条件下对网络连通性影响最大的节点子集的一类优化问题。识别网络中的关键节点是分析与理解网络特性、结构以及功能的重要方式，本文基于网络局部特征对关键节点识别问题进行研究，主要工作有：
(1)提出了一种基于节点中心性的关键节点识别算法框架(greedy algorithm for critical node problem, GCNP)，根据某种中心性指标选择网络的初始点覆盖集；从网络中删除该点覆盖集，迭代选择点覆盖集中使原网络连通节点对增加最小的节点向原网络回添,直至点覆盖集中节点满足用户给定的待删除关键节点数。为了更好地选择初始的节点覆盖集，提出了一种基于局部拓扑信息的节点中心性度量指标(local neighbor centrality, LNC)。在16个人工网络和9个真实网络数据集上的实验结果表明，与单独使用各中心性指标相比，采用GCNP算法框架可以提高算法性能；所提的节点中心性度量指标LNC较其他常见的中心性更能准确地评估节点的重要性；GCNP下的LNC性能优于其他指标。
(2)提出了一种基于迭代局部搜索框架的关键节点优化方法(critial nodes optimization method, CNOA)。该方法通过迭代优化过程和随机扰动过程来提升解的质量。在迭代优化过程中，选择剩余网络大连通分量中的节点与可行解中的节点进行交换来减少计算量；为避免点交换过程中的部分节点频繁换入换出，定义了节点权重，每次迭代选择相应大连通分量中权重最高的节点进行交换。为了避免算法陷入局部极值，随机扰动过程从剩余网络中的大连通分支的节点并集中随机选择多个节点对当前解进行扰动，扰动后的解经过再次优化后通常可以得到质量更高的关键节点集。在16个人工网络和14个真实网络上进行有效性验证，实验结果表明CNOA中的迭代优化过程和随机扰动策略可以有效提高可行解的质量；与常见的4种启发式算法相比，CNOA在大多数网络上更能准确识别关键节点。
(1)提出了一种基于节点中心性的关键节点识别算法框架(greedy algorithm for critical node problem, GCNP)，根据某种中心性指标选择网络的初始点覆盖集；从网络中删除该点覆盖集，迭代选择点覆盖集中使原网络连通节点对增加最小的节点向原网络回添,直至点覆盖集中节点满足用户给定的待删除关键节点数。为了更好地选择初始的节点覆盖集，提出了一种基于局部拓扑信息的节点中心性度量指标(local neighbor centrality, LNC)。在16个人工网络和9个真实网络数据集上的实验结果表明，与单独使用各中心性指标相比，采用GCNP算法框架可以提高算法性能；所提的节点中心性度量指标LNC较其他常见的中心性更能准确地评估节点的重要性；GCNP下的LNC性能优于其他指标。
(2)提出了一种基于迭代局部搜索框架的关键节点优化方法(critial nodes optimization method, CNOA)。该方法通过迭代优化过程和随机扰动过程来提升解的质量。在迭代优化过程中，选择剩余网络大连通分量中的节点与可行解中的节点进行交换来减少计算量；为避免点交换过程中的部分节点频繁换入换出，定义了节点权重，每次迭代选择相应大连通分量中权重最高的节点进行交换。为了避免算法陷入局部极值，随机扰动过程从剩余网络中的大连通分支的节点并集中随机选择多个节点对当前解进行扰动，扰动后的解经过再次优化后通常可以得到质量更高的关键节点集。在16个人工网络和14个真实网络上进行有效性验证，实验结果表明CNOA中的迭代优化过程和随机扰动策略可以有效提高可行解的质量；与常见的4种启发式算法相比，CNOA在大多数网络上更能准确识别关键节点。