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 prob