2013/05/02 by Ruoming Jin, Jin, Ruoming, Yelong Shen +5
Computer Science · Engineering · Physics and Astronomy · #Complex Network Analysis Techniques #FOS: Computer and information sciences #FOS: Physical sciences #Infrastructure Resilience and Vulnerability Analysis #Network Security and Intrusion Detection #Physics and Society (physics.soc-ph) #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.1305.0513
openalex publication_date 2013/05/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this work, we 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, we introduce the average neighborhood size as a new measure for the degree of being small-world and utilize it to formally define the desmall- world network problem. We 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 our problem. Furthermore, we transform the de-small-world network problem as an OR-AND Boolean function maximization problem, which is also an NP-hardness problem. In addition, we develop a numerical relaxation approach to solve the Boolean function maximization and the de-small-world problem. Also, we introduce the short-betweenness, which measures the edge importance in terms of all short paths with distance no greater than a certain threshold, and utilize it to speed up our numerical relaxation approach. The experimental evaluation demonstrates the effectiveness and efficiency of our approaches.