Limiting the Neighborhood: De-Small-World Network for Outbreak Prevention
In this paper, the authors study a basic and practically important strategy to help prevent and/or delay an outbreak in the context of network: limiting the contact between individuals. In this paper, they introduce the average neighborhood size as a new measure for the degree of being small-world and utilize it to formally define the de-small-world network problem. They also prove the NP-hardness of the general reachable pair cut problem and propose a greedy edge betweenness based approach as the benchmark in selecting the candidate edges for solving their problem. Furthermore, they transform the de-small-world network problem as an OR-AND Boolean function maximization problem, which is also an NP-hardness problem.