Various measures that characterize graphs exist in literature. Insights into the properties of a graph as a whole and its components are revealed largely through graph measures, also called graph metrics. In seeking to interpret a consequential edge metric from a vertex-centric perspective, the paper advances an original measure – the relative isolation probability of a vertex. Concisely, the probability of relative isolation pertains to the likelihood of a vertex to be disconnected from all designated source vertices in a graph with probability-weighted edges. A two-step algorithm for efficient calculation is presented and evaluated. Contained within the procedure is a Monte Carlo simulation and the use of a compact data structure called the zero-suppressed binary decision diagram, efficiently constructed through the frontier-based search. The novel measure is then computed for a diverse set of graphs, serving as benchmark for the proposed method. In closing, case studies on real-world networks are performed to ensure the consistency of the experimental with the actual.
Tan, R. R. P., See, K. S. S., Kawahara, J., Ikeda, K., de Jesus, R. M., Garciano, L. E. O., & Garciano, A. D. (2022). The relative isolation probability of a vertex in a multiple-source edge-weighted graph. Engineering Letters, 30(1), 117-130. http://www.engineeringletters.com/issues_v30/issue_1/index.html