Un modelo de grafo aleatorio jerárquico (HRG) combinado con un enfoque de máxima verosimilitud y un algoritmo de Monte Carlo de Cadena de Markov no solo se puede utilizar para describir cuantitativamente la organización jerárquica de muchas redes reales, sino que también puede predecir conexiones faltantes en redes parcialmente conocidas con alta precisión. Sin embargo, el costo computacional es muy alto cuando se muestrean grafos aleatorios jerárquicos mediante el algoritmo de Monte Carlo de Cadena de Markov (MCMC), de modo que los grafos aleatorios jerárquicos, que pueden describir las características de la estructura de la red, no se pueden encontrar en un rango de tiempo razonable. Esto limita seriamente la practicidad del modelo. Para superar este defecto, en este artículo se propone un algoritmo MCMC mejorado llamado MCMC de transiciones de dos estados (TST-MCMC) para muestrear eficientemente grafos aleatorios jerárquicos. En la cadena de Markov compuesta por todos los posibles grafos aleatorios jerárquicos, TST-MCMC puede generar dos variables de estado candidatas durante la transición de estado e introducir un mecanismo de competencia para filtrar la peor de las dos variables de estado candidatas. Además, el equilibrio detallado de la cadena de Markov puede ser garantizado mediante el uso de la regla de Metropolis-Hastings. Al utilizar este método, no solo se puede mejorar la velocidad de convergencia de la cadena de Markov, sino que también se puede estrechar el intervalo de convergencia de la cadena de Markov. Se emplean tres redes de ejemplo para verificar el rendimiento del algoritmo propuesto. Los resultados experimentales muestran que nuestro algoritmo es más factible y más efectivo que los esquemas comparados.