Social networks have made considerable development in recent years and are spreading quickly in different ways. The most common model for representation and study of social networks is based on graph theory that it is widely used in the analysis of social networks. A social network can be represented with a simple and undirected graph G = ( V,E ) where V is the set of vertices and E is the set of edges so that each vertex corresponds to a user and edge between two vertices represents relationship between corresponding users of the network such as friendship, cooperation and so on. The information of social networks are valuable sources of information that their publication is necessary and useful in order to analyze the data. On the other hand these information includes sensitive, private information of many people. Thus, the users’ privacy concerns have become one of the major concerns in the use of social networks. So in order to privacy preserving, we should release the anonymous version of the network that is different from the original version. On the other hand, to utility of analysis results of the anonymous version of network, the anonymous network must be similar as much as possible to the main network. Therefore, the significant problem is provide ways to balance between the security of the network and the loss information in the released network. Now there is growing various methods for preserving privacy on a social network, considering the amount of available information for the attacker and data utility after the publication of the network. In this thesis, we study a variety of privacy preserving methods on social networks, based on graph theory