Critical node detection involves identifying key nodes whose removal significantly disrupts network connectivity or performance. The evaluation of vulnerability in networks is crucial because many real-world problems are represented as graphs with uncertainty, including social networks, communication infrastructures, epidemiological models, and transportation systems. In this paper, we consider a stochastic Critical Node Detection Problem (SCNDP) with edge uncertainty, aiming to minimize the expected pairwise connectivity (EPC) in the resulting residual network. We propose a heuristic method for the SCNDP and compare it with the existing algorithm. Experimental results performed on random graphs with different edge-probability configurations demonstrate the effectiveness of the heuristics.