Abstract: In basic random walk similarity index, the transition probability is determined just by the degree of current node. This way can influence link prediction precision. In view of this, an improved link prediction algorithm is proposed, which is based on the Metropolis-Hasting (MH) algorithm. The degree information of neighbor nodes is fully utilized and the transition probability matrix is reconstructed by assigning the self-loop rate of current node to its neighbors, and then the Random Walk with Restart (RWR) similarity index is fused in the proposed method. Firstly, the transition probability between nodes is redefined according to the degree information of the current node and the neighbor node.Then the new transition probability is reconstructed into a probability matrix. Finally the RWR similarity index is fused to carry out the link prediction experiment. The experimental results show that our method's consequence is better than other seven benchmark algorithms (e.g. RWR and CN) , the AUC index of proposed algorithm also is improved, as well as the ranking score index.The AUC index can be raised at most 3.98% and the Ranking score index can be decreased 1.92%. Thus, it's an effective method for improving the accuracy of link prediction.