To preserve the privacy of social networks

most existing methods are applied to satisfy different anonymity models

but some serious problems are involved such as often incurring large information losses and great structural modifications of original social network after being anonymized.Therefore

an improved privacy protection model called SimilarGraph is proposed

which is based on

k

-degree anonymous graph derived from

k

-anonymity to keep the network structure stable.Where the main idea of this model is firstly to partition network nodes into optimal number of clusters according to degree sequences based on dynamic programming

and then to reconstruct the network by means of moving edges to ac

hieve

k

-degree anonymity with internal relations of nodes considered.To differentiate from traditional data disturbing or graph modifying method used by adding and deleting nodes or edges randomly

the superiority of our proposed scheme lies in which neither increases the number of nodes and edges in network

nor breaks the connectivity and relational structures of original network.Experimental results show that our SimilarGraph model can not only effectively improve the defense capability against malicious attacks based on node degrees

but also maintain stability of network structure.In addition

the cost of information losses due to anonymity is minimized ideally.