{'fraction_non_alphanumeric': 0.02580140734949179, 'fraction_numerical': 0.001563721657544957, 'mean_word_length': 5.3681592039801, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Scaling-Up Urban Network Security Games with Graph Contraction

Urban network security games, which model attackers and defenders on road networks, provide a promising framework for planning effective strategies of patrolling and inspection. This paper focuses on improving scalability of the algorithm to solve them, which is one of the important challenges in security game problems. State-of-the-art solvers have been scaled up to handle real-world networks with tens of thousands of edges; however, it can take days or more to solve them when we vary problem settings of sources, targets, and security resources. This paper provides a novel method “MiCANS” to improve the scalability drastically, which includes two features: (1) the strategy spaces of both players are reduced dramatically through edge contraction by identifying the edges that are not essential for defender’s optimal strategy, based on the technique that we call “min-cut arrangement”; and (2) the reduced problem is solved efficiently with a mixed-integer quadratic programming oracle. Although theoretical analysis have not been made yet enough, experimental results show that it finds optimal solutions in most cases and achieves several orders of magnitude speedup compared to the existing algorithms.