The invention discloses a differential privacy protection method for an online social network based on a stratified random graph. The differential privacy protection method comprises the following steps: inputting a network; constructing a tree structure of the network based on a stratified random graph model; sampling in the network through a Markov chain Monte Carlo method according to a preset privacy budget so as to obtain a sampled tree; taking the root node of the sampled tree as an initial current node; calculating an associated probability value of the current node according to the preset privacy budget; finding out a set of node pairs by taking the current node as the nearest father node in the network, and setting an edge among the set of node pairs according to the associated probability value; judging whether traversal of the sampled tree is completed or not, and if not, continuously traversing the next node in the sampled tree; and otherwise, outputting a purified network composed of edges arranged among all the sets of nodes and nodes thereof. According to the invention, the privacy protection problem of sensitive structural data information in the social network can be solved; differential privacy protection requirements can be satisfied; and simultaneously, the good data availability is kept.