Finding Minimum Node Separators: A Markov Chain Monte Carlo Method

Abstract:
In networked systems such as the power grid or communication networks, graph separation from node failures can damage the overall operation severely. Thus, one of the most important goals of network attackers is to separate nodes such that the sizes of the connected components become small. In this work, we consider the problem of finding a minimum α-separator, that partitions the graph into connected components of sizes smaller than alphan, where n is the number of nodes in the graph. To solve the α-separator problem, we develop a random walk algorithm based on a Metropolis chain. We analyze the first passage time of our random walk algorithm and investigate the conditions for polynomial first passage time. Through simulations over real topologies and generated topologies, we show that the first passage time is less than O(n³), where the number of nodes is n, and validate our analysis for the first passage time. We then show that our random walk algorithm performs better than other heuristic algorithms, highest-degree-first and greedy. The solution from our algorithm allows us to characterize the weakest points in the network that need to be strengthened. In real topologies, we find that attacking a dense area is often not an efficient solution for partitioning a network graph into small components.