A Connected-Component Improvement Procedure for Relative Isolation Probability Calculation

• Main Authors: Tan, Renzo Roel P, Ikeda, Kazushi
• Format: text
• Published: Archīum Ateneo 2024
• Subjects: breadth-first search; graph measure; Monte Carlo method; probability of relative isolation; Engineering; Environmental Sciences; Life Sciences
• Online Access: https://archium.ateneo.edu/qmit-faculty-pubs/22; https://archium.ateneo.edu/context/qmit-faculty-pubs/article/1021/viewcontent/EL_32_4_07.pdf
• Institution: Ateneo De Manila University

Due to the prevalence of natural disasters, the resilience of networks that provide essential services to the population has been studied. A recent contribution is the probability of relative isolation, which measures the likelihood of a demand node to be unreachable by supply nodes. The existing procedure for calculation is an enumerative decision-diagram-based approach that may be resource-intensive especially on occasions when time and memory constraints are imposed. In response, the study reverse-engineers the current method towards increased efficiency. The proposed solution hinges on the breadth-first search, producing connected components based on the sources. The algorithm is then benchmarked on foundational networks from literature, presenting a 99.77% decrease in computation time on average.