In this paper, we propose new methods for generating playlists with a single graph, which represents multiple types of relations in a playlist. Although current users are familiar with online music services, they have difficulty in deciding which tracks to listen to because there are millions of tracks available on such services. Automated playlist generation is one of the best solutions to solving this costly task of finding interesting tracks from the enormous tracks. Accordingly, one playlist-generation task, namely, hit rate, in which several tracks are given as a user query, is focused on in this study. There are four types of context objects (playlists, tracks, artists, and users) in the basic information on playlists, and three types of relations (playlists contain tracks and artists, users create playlists and artists play and/or sing tracks) in playlists. First, different types of relations in playlists are combined, and a single graph linking different context objects is generated. Next, a random walk is applied to the graph, and the expected values of track nodes are calculated on the basis of the transition probabilities of nodes in the graph. Finally, tracks are recommended in order of the expected values. The results of an experimental evaluation of the proposed methods in comparison with conventional methods revealed that one of the proposed methods (RW-hybrid) improved effectiveness by up to 21%. Moreover, this method reduces execution time as much as the fastest existing methods.