Abstract: Personalized recommender systems are confronting great challenges of accuracy, diversification and novelty, especially when the data set is sparse and lacks of accessorial information, such as user profiles, item attributes and explicit ratings. Collaborative tags contain abundant information about personalized preferences and item contents, and are therefore potential to help providing better recommendations. In this paper, we analyze the information on the famous music social network, Last.fm. Bipartite graph is established between users, items and tags while random walk with restart is used to analyze the relationship between the nodes discussed before and get the neighboring relations between songs or tags. After that, musicrecommended list and indirect related music collection, thus, can be obtained. At last, personalized music recommendation algorithm can be implemented by fusing and reranking the recommended list using the algorithm proposed in this paper. Experiments show that, in the same corpus, the music recommendation algorithmin this paper performs better than the ordinary method such as collaborative filtering and bipartite based algorithm. Our method built on Last.fm, therefore, satisfies the personalized requirement for users to music. Furthermore, with the development of Web2.0, our method will show its advantage as the amount of tags become more and more enormous.