Limiting the neighborhood: De-small-world network for outbreak prevention

Ruoming Jin, Yelong Sheng, Lin Liu, Xue Wen Chen, Nhat Hai Phan

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 de-small-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.

Original languageEnglish (US)
Title of host publicationComputational Data and Social Networks - 8th International Conference, CSoNet 2019, Proceedings
EditorsAndrea Tagarelli, Hanghang Tong
Number of pages17
ISBN (Print)9783030349790
StatePublished - 2019
Event8th International Conference on Computational Data and Social Networks, CSoNet 2019 - Ho Chi Minh City, Viet Nam
Duration: Nov 18 2019Nov 20 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11917 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference8th International Conference on Computational Data and Social Networks, CSoNet 2019
Country/TerritoryViet Nam
CityHo Chi Minh City

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Limiting the neighborhood: De-small-world network for outbreak prevention'. Together they form a unique fingerprint.

Cite this