Minimizing Spectral Radius of Non-Backtracking Matrix by Edge Removal

The spectral radius of the non-backtracking matrix for an undirected graph plays an important role in various dynamic processes running on the graph. For example, its reciprocal provides an excellent approximation of epidemic and edge percolation thresholds. In this paper, we study the problem of minimizing the spectral radius of the non-backtracking matrix of a graph with n nodes and m edges, by deleting k selected edges. We show that the objective function of this combinatorial optimization problem is not submodular, although it is monotone. Since any straightforward approach to solving the optimization problem is computationally infeasible, we present an effective, scalable approximation algorithm with complexity O (n+km). Extensive experiment results for a large set of real-world networks verify the effectiveness and efficiency of our algorithm, and demonstrate that our algorithm outperforms several baseline schemes.