Protein phosphorylation is a kind of important post-translational modification of protein, which plays a critical role in many biological processes of eukaryote. Identifying kinase-substrate interactions is helpful to understand the mechanism of many diseases. Many computational algorithms for kinase-substrate interactions identification have been proposed. However, most of those methods are mainly focused on utilizing protein local sequence information. In this article, we propose a new computational method to predict kinase-substrate interactions based on protein-protein interaction (PPI) network. Different from existing methods, the PPI network is utilized to measure the similarities of kinase-kinase and substrate-substrate, respectively. Then, the pairwise similarities of kinase-kinase and substrate-substrate are adjusted based on the assumption that the similarities of kinase-kinase and substrate-substrate are more reliable if they are in the same cluster. Finally, the bi-random walk is used to predict potential kinase-substrate interactions. The experimental results show that our method outperforms other state-of-the-art algorithms in performance. Furthermore, the case study demonstrates that it is effective in predicting potential kinase-substrate interactions.