This paper presents a set of algorithms used for music recommendations and personalization in a general purpose social network www.ok.ru, the second largest social network in the CIS visited by more then 40 millions users per day. In addition to classical recommendation features like "recommend a sequence" and "find similar items" the paper describes novel algorithms for construction of context aware recommendations, personalization of the service, handling of the cold-start problem, and more. All algorithms described in the paper are working on-line and are able to detect and address changes in the user's behavior and needs in the real time. The core component of the algorithms is a taste graph containing information about different entities (users, tracks, artists, etc.) and relations between them (for example, user A likes song B with certainty X, track B created by artist C, artist C is similar to artist D with certainty Y and so on). Using the graph it is possible to select tracks a user would most probably like, to arrange them in a way that they match each other well, to estimate which items from a fixed list are most relevant for the user, and more. In addition, the paper describes the approach used to estimate algorithms efficiency and analyze the impact of different recommendation related features on the users' behavior and overall activity at the service.