不完全信息条件下基于链路预测的复杂网络瓦解问题研究

In the majority of cases, networks are beneficial, however, many times it may also be harmful, such as terrorist network and disease spreading network. 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". Aiming at the problem of incomplete information in network disintegration, this project creatively introduces the new idea of link prediction and try to recover partial missing information based on link prediction, which may improve the effect of network disintegration. Based on the formal descriptions of network information, disintegration strategy, disintegration cost, disintegration effect and link prediction, this project firstly establishes the disintegration model of complex networks with incomplete information and investigates the impact of missing information on the effect of network disintegration. Then this project studies the methods of algorithm selection of link prediction and the optimal faction of prediction. Lastly, this project proposes the optimization model of disintegration strategy based on link prediction and presents the solution algorithm. This project will provide a new approach to solve the problem of network disintegration with incomplete information, such as the counterterrorism, disease immunity, military confrontation and so on. Moreover, it will provide an important reference for the application of link prediction in other fields.

大多数情况下，我们面对的网络都是“有益的”，但是很多时候我们面对的网络也可能是“有害的”，例如恐怖组织网络、疾病传播网络等。如何通过免疫、封锁、隔离、干扰、袭击等手段有效瓦解这些有害网络成为一个亟待解决的挑战性问题，其核心是找到网络系统的“关键节点”。本项目针对复杂网络瓦解面临的信息缺失问题，创新提出基于链路预测的新思路，探索通过链路预测还原部分缺失的网络结构信息，从而提高网络瓦解效果。本项目首先通过对网络信息、瓦解策略、瓦解成本、瓦解效果、链路预测进行形式化描述，构建不完全信息条件下的复杂网络瓦解模型，在此基础上研究信息缺失对网络瓦解效果的影响，进而研究解决链路预测算法遴选、链路预测比例确定等关键问题，最后建立瓦解策略优化模型并给出求解算法。项目成果将为解决反恐维稳、疾病免疫、军事对抗等不完全信息条件下的复杂网络瓦解问题提供新思路、新技术，同时也为链路预测在其他领域的应用提供重要借鉴。

大多数情况下，我们面对的网络都是“有益的”，但是很多时候我们面对的网络也可能是“有害的”，例如恐怖组织网络、疾病传播网络等。如何通过免疫、封锁、隔离、干扰、袭击等手段有效瓦解这些有害网络成为一个亟待解决的挑战性问题，其核心任务是找到网络系统的“关键节点”。本项目针对复杂网络瓦解面临的信息缺失问题，创新提出基于链路预测的新思路，探索通过链路预测还原部分缺失的网络结构信息，从而提高网络瓦解效果。主要开展了四个方面的研究工作：1）不完全信息条件下的复杂网络瓦解模型研究；2）信息缺失对复杂网络瓦解效果的影响研究；3）基于链路预测的复杂网络最优瓦解策略研究；4）链路预测算法选择以及最优预测比例研究。主要研究成果包括：1）提出了一种基于特征谱的网络可预测性指标；2）将链路预测引入到不完全信息条件下瓦解策略的研究；3）揭示了链路预测的漫画效应；4）提出了基于边重要性的链路预测算法评价与遴选方法；5）提出了链路预测最优预测比例确定方法；6）设计了复杂网络链路预测及网络瓦解应用的仿真系统；7）开发了面向大众的复杂网络瓦解与攻防博弈游戏。本项目成果将为解决反恐维稳、疾病免疫、军事对抗等不完全信息条件下的复杂网络瓦解问题提供新思路、新技术，同时也为链路预测在其他领域的应用提供重要借鉴，具有重要的理论和应用价值。本项目严格按照研究计划执行， 共发表高水平学术论文15篇，其中SCI检索论文13篇（中科院一区Top论文3篇），获得教育部科技进步二等奖1项（排名第4）、软件著作权3项。