With the fast development of social networks, privacy protection on social network data has already attracted more and more research attention. If an adversary has collected enough information by intentionally querying a social network, the privacy of social network data might be successfully inferred based on the previous query results, which is seldom investigated by most existing approaches. In this paper, we first formulate the correlated query results as the non-zero prior knowledge, then propose a novel differential privacy approach to enhance privacy of social network data from being inferred. The corresponding ϵ-difference is re-formulated as well as the calculation of the sensitivity between two “neighboring” social graphs. Particularly, the calculation of sensitivity is proposed for three widely adopted queries on social networks, i.e., node degree distribution query, cut set query and the shortest path query. To evaluate our approach, rigorous experiments have been performed on three real world data sets. The promising experimental results have demonstrated that the proposed approach is superior to the state-of-the-art privacy protection approaches with respect to data privacy and data utility.