Analytical Approximation for ATTR with Respect to Node Removals

Abstract

We propose an analytical approach to approximate the average two-Terminal reliability (ATT R) for graphs where a fraction of the nodes is removed. The approximation is based on the generating function of the network's degree distribution under random node removals and stochastic degree-based node removals. Through validation on synthetic graphs, including Erdos Renyi random graphs and Barabasi-Albert graphs, as well as four real-world networks from the Internet Topology Zoo, we observe that the analytical method effectively approximates the average two-Terminal reliability under random node removals for synthetic graphs. In the case of real-world graphs under random and stochastic degree-based node removals or synthetic graphs under stochastic degree-based node removals, the analytical ap-proximation yields reasonably accurate results when the fraction of removed nodes is small, specifically less than 10%, provided that the initial analytical approximation closely aligns with the real ATT R values.