Owners of online social networks are increasingly sharing potentially sensitive information about users and their relationships with advertisers, application developers, and data-mining researchers. This information is of significance importance in various applications domains such as marketing, psychology, epidemiology and homeland security. In the area of marketing, it is an accepted fact that the analysis of social networks has made commerce more profitable. Privacy on social networks is typically protected by anonymization. It is now accepted that current approaches to anonymization are not sufficient for ensuring privacy when dealing with social networks. Smarter anonymization techniques are based on the modification of the original network by adding fake links. While it is true that this makes the identification of the individuals harder, it is also true that the information of the social network is deteriorated. We introduced the NetDegree global constraint whose purpose is to eliminate non-viable alternatives in the process of finding a good trade-off between protection of data and quality of the information represented by the network.