Social networks contain important information about the society. Publishing them tends to have various advantages to data analyzers. However, privacy preservation in social networks has always been of primary concern. If these networks are published raw or with an ineffective anonymization technique, an adversary, even with limited background knowledge has the potential to extract the sensitive information present in the network. The Lossy-Join approach was used by Wong et al (2007) to develop an algorithm in order to achieve (α, k) - anonymity [14] in relational data. We extend this approach and develop an algorithm by using the same concept so that (α, k) - anonymity can be achieved in social networks. First, we run the proposed algorithm on a small network for illustration of its effect. Further, we test our approach on a real dataset from the United State Power grid and another large synthetic input in Erdős-Rényi graph generated by using R. Through experimental analysis, we establish that the efficiency of our algorithm is better than a general (α, k) - anonymity algorithm developed by Chakraborty et al [6] in 2016. We also propose a technique to add noisy sensitive labels into the model in case an anonymizer wishes a higher level of anonymization. The noise nodes required for anonymization are added so that they have minimal social importance. © 2018, University of Skovde. All Rights Reserved.