<p>Graph robustness is a measure of graph’s ability to maintain connectivity and other graph properties with node or edge failures and is widely used in a variety of complex networks. Supercomputing relies on massive parallel architectures to handle complex network simulations, and distributed-memory systems enhance robustness by isolating node failures. Therefore, estimating graph or complex network robustness is quite important in supercomputing. The Kirchhoff index can be used to evaluate graph robustness, but faces the problem of excessive computational complexity when dealing with large-scale graphs. To improve the efficiency and accuracy of robustness estimation based on Kirchhoff index, in this paper, we propose the Semi-Random Degree-Preferred (SRDP) algorithm, which dynamically adjusts its sampling strategy by combining random sampling with degree-prioritized sampling. Verified by a series of experiments, SRDP shows good performance in classical graphs, random graphs and real-world networks. We also explore the estimation of Kirchhoff index through the downtrend and propose the double sampling method for the robustness evaluation of real-world networks. Experimental results show that SRDP has good applicability to different types and sizes of graphs and networks.</p>