Recently, location-based social networks (LBSNs) gave the opportunity to users to share geo-tagged information along with photos, videos, and SMSs. Recommender systems can exploit this geographic information to provide much more accurate and reliable recommendations to users. In this paper, we present and compare 16 real life LBSNs, bringing into surface their advantages/ disadvantages, their special functionalities, and their impact in the mobile social Web. Moreover, we describe and compare extensively 43 state-of-the-art recommendation algorithms for LBSNs. We categorize these algorithms according to: personalization type, recommendation type, data factors/features, problem modeling methodology, and data representation. In addition to the above categorizations which cannot cover all algorithms in an integrated way, we also propose a hybrid k-partite graph taxonomy to categorize them based on the number of the involved k-partite graphs. Finally, we compare the recommendation algorithms with respect to their evaluation methodology (i.e., datasets and metrics) and we highlight new perspectives for future work in LBSNs.