The critical node problem in stochastic networks with discrete-time Markov chain

Abstract

The length of the stochastic shortest path is defined as the arrival probability from a source node to a destination node. The uncertainty of the network topology causes unstable connections between nodes. A discrete-time Markov chain is devised according to the uniform distribution of existing arcs where the arrival probability is computed as a finite transition probability from the initial state to the absorbing state.Two situations are assumed, departing from the current state to a new state, or waiting in the current state while expecting better conditions. Our goal is to contribute to determining the critical node in a stochastic network, where its absence results in the greatest decrease of the arrival probability. The proposed method is a simply application for analyzing the resistance of networks against congestion and provides some crucial information of the individual nodes. Finally, this is illustrated using networks of various topologies.