In recent years, we have witnessed a great success of social community websites. Large-scale social images with rich metadata are increasingly available on the Web. In this paper, we focus on efficiently tagging social images by partitioning the large-scale tag graph in parallel. Vertices of the tag graph are constructed by the candidate tags which are extended from initial tags. Initial tags are extracted from the rich metadata of social images, including user supplied tags, notes data and group information. Edge weight of the tag graph is calculated by combining two parameters, which are related to image visual features and tag co-occurrence. Both global and local features are considered in parameter 1. For each candidate tag, a neighbor images voting algorithm is performed to calculated parameter 2. As the tag graph may be large-scale, we utilize a parallel graph partitioning algorithm to accelerate the graph partitioning process. After the tag graph is partitioned, we rank all the sub-graphs according to the edge weight within one sub-graph. Afterwards, final tags are selected from the top ranked sub-graphs. Experimental results on Flickr image collection well demonstrate the effectiveness and efficiency of the proposed algorithm. Furthermore, we apply our social image tagging algorithm in tag-based image retrieval to illustrate that our algorithm can really enhance the performance of social image tagging related applications.