Although the problem of spam detection in email is well understood and has been extensively researched, a significant portion of emails today are spam. A most widely used method to detect spam involves content filtering, where the spam detector scans the received email for keywords. However, the same approach cannot be applied to detect Voice over IP (VoIP) spam, since a call has to be categorized as a legitimate or a spam (each to a degree with a certain reliability) before the connection is established. Also, spammers over IP can potentially generate orders of magnitude more spam volume, at far less cost, and with greater anonymity than telemarketers using the Public Switch Telephone Network (PSTN). The spam problem in VoIP is further compounded by the absence of a do-not-call-list, which has been the main reason for the reduction of spam calls in PSTN. Thus, the spam issue for VoIP is as important as those pertaining to quality-of-service (QoS) of the voice traffic itself. To this end, we propose two different anti-spam frameworks for large scale VoIP systems. The first one is a centralized SIP-based spam detection framework that relies on SIP messages during the call establishment phase to identify spam calls, and the second one is a distributed referral social network model, where a user is assigned a reputation score by its neighbors. Based on the reputation, a callee can decide either to accept or decline a call. Our simulation results indicate that the referral model can provide better anti-spam capabilities by isolating a spammer faster than the SIP based approach, and can also correctly identify spam calls over 98% of time.