The growing popularity of social networks has generated interesting data analysis problems. At the same time, it has raised important privacy concerns, because social networks contain personal and sensitive information. Consequently, social graphs, which express the relations between the actors in a social network, ought to be sanitized or anonymized before being published. Most work on privacy-preserving publication of social graphs has focused on dealing with passive attackers while active attackers have been largely ignored. Active attackers can affect the structure of the social network graphs actively and use structural information, as a passive attacker does, to re-identify a user in a social graph. In this article we propose, to the best of our knowledge, the first anonymization method that resists to active attacks.