文章基本信息

标题：The Relative Isolation Probability of a Vertex in a Multiple-Source Edge-Weighted Graph
本地全文：下载
作者：Renzo Roel P.Tan ; Kyle Stephen S.See ; Jun Kawahara 等
期刊名称：Engineering Letters
印刷版ISSN：1816-093X
电子版ISSN：1816-0948
出版年度：2022
卷号：30
期号：1
页码：117-130
语种：English
出版社：Newswood Ltd
摘要：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 probabilityweighted 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.
关键词：frontier-based search;graph measure;Monte Carlo method;probability of relative isolation;zero-suppressed binary decision diagram