TY - GEN
T1 - Limiting the neighborhood
T2 - 8th International Conference on Computational Data and Social Networks, CSoNet 2019
AU - Jin, Ruoming
AU - Sheng, Yelong
AU - Liu, Lin
AU - Chen, Xue Wen
AU - Phan, Nhat Hai
N1 - Publisher Copyright:
© Springer Nature Switzerland AG 2019.
PY - 2019
Y1 - 2019
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85077769032&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85077769032&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-34980-6_27
DO - 10.1007/978-3-030-34980-6_27
M3 - Conference contribution
AN - SCOPUS:85077769032
SN - 9783030349790
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 229
EP - 245
BT - Computational Data and Social Networks - 8th International Conference, CSoNet 2019, Proceedings
A2 - Tagarelli, Andrea
A2 - Tong, Hanghang
PB - Springer
Y2 - 18 November 2019 through 20 November 2019
ER -