基于最少边的最短路径扰动

摘要

提出一种最少边扰动算法，以解决如何在扰动最少边的前提下，以最小代价来使得一条特定的目标路径成为最短路径的问题。该算法基于最少边的最短路径扰动模型，通过引入每条边的权重扰动上限约束，提出了最少扰动边数-最小扰动成本的双目标混合整数规划问题，从而实现操纵网络节点间的最短路径。与以往的最小代价扰动算法相比，该方法降低了扰动的复杂性和扰动网络被察觉的风险。实验表明，最优解使扰动边数减少了约27%，具有更好的性能。

关键词

扰动边数 / 扰动代价 / 路径扰动 / 最短路径

基金资助

国家自然科学基金(120050019); 安徽省自然科学基金(2008085QF299,2108085QA35); 安徽省教育厅重点项目(KJ2021A0896)