Personal privacy is facing severe threats as social networks are sharing user data with advertisers, application developers, and data mining researchers. Although these data are anonymized by removing personal information, such as user identity, nickname, or address information, personal information still could not be protected effectively. In order to arouse the attention of people from academia and industry for privacy protection, we propose a random forest method to de-anonymize social networks. First, we convert the social network de-anonymization problem into a binary classification problem between node pairs. In order to partition large sparse social networks, we use the spectral partition method to partition large graphs into a number of small subgraphs. Then, we use the features of the network structure to train the random forest classifier. As a result, candidate node pairs from anonymous network and auxiliary network can be classified as matched pair by the random forest classifier. Furthermore, we improve the efficiency of our solution through parallelizing proposed method. The experiments conducted on the real data sets show that our solution's area under the curve is 19% higher than baseline methods on average. Besides that we test the robustness of the proposed algorithm by adding some noisy data, and the result demonstrates that our solution has good robustness. © 2013 IEEE.