基于非回溯矩阵的有向网络拆解方法

Directed Network Dismantling Method Based on Non-backtracking Matrix

网络拆解是指通过移除最少的节点集将网络拆分为相互不连通的子部分从而达到对网络进行有效控制的效果。但是现有的绝大多数工作只聚焦于无向网络的拆解问题,对有向网络的研究很少,因为当网络中的连边为有向时应用现有方法会使拆解产生较多的耗费。针对此问题本文提出了一种有效的基于非回溯矩阵的边模块拆解方法,将边模块谱划分和有向网络拆解问题相结合,找到连接不同边模块的最少关键点集进行移除。为验证本方法的有效性,将其应用于大规模人工网络和真实网络,多重实验结果表明本文所提方法在拆解精度和计算效率上都具有很大优势。

Network dismantling is to break a network into several unconnected subcomponents by removing a minimal set of vertices so as to effectively control the network.However,most of existing works only focus on network dismantling problem in undirected network,there is little research on directed networks,the reason is,when the connected edges in the network are directed edges,the application of existing dismantling methods will lead to much dismantling cost.Concentrating on network dismantling in directed network,this paper proposes the link modules dismantling method based on non-backtracking matrix,which combines link modules spectral partition with network dismantling in directed network,find and remove the minimal critical vertices set which connects different link modules.In order to verify the effectiveness of this method,it has been applied in large-scale artificial networks and real networks.Multiple experimental results show that the proposed method has great advantages in dismantling accuracy and computational efficiency.