复杂网络瓦解问题研究进展与展望

Status and Prospects on Disintegration of Complex Networks

一般情况下,我们面对的网络都是有益的,但是有时候我们面对的网络也可能是有害的,例如恐怖组织网络、疾病传播网络等。如何通过阻断、干扰、免疫、封锁、隔离等手段有效瓦解这些有害网络成为一个亟待解决的挑战性问题,其核心是找到网络系统的关键节点(边)。首先给出了网络瓦解问题的数学描述,在此基础上从基于数学规划、基于中心性指标、基于启发式算法、基于进化计算、基于机器学习等几个方面系统总结了运筹学、网络科学、计算机科学等领域关于复杂网络瓦解问题的研究进展,最后分别从目标网络维度、瓦解模型维度、瓦解算法维度对复杂网络瓦解问题未来发展进行了展望。

In the majority of cases, networks are beneficial. However, many times it may also be harmful, such as terrorist networks and disease spreading networks. It has become an urgent challenging problem to disintegrate these harmful networks by various methods such as immunization, block, isolation, disturbance, and attack. The core task of network disintegration is to identify the “critical nodes(edges)”. This survey firstly gives the mathematical description of network disintegration. On this basis, this survey then reviews the status of network disintegration study in the fields of operations research, network science, and computer science based on mathematical programming, the centrality metrics, the heuristic algorithms, evolutionary computation, and machine learning, respectively. Lastly, this survey presents the prospects of network disintegration study from the aspects of the target network, disintegration model, and algorithm.