The release of social network data may lead to the disclosure of user privacy; for example, the user identity may be recognized by malicious attackers by analyzing the degree of nodes in the network. Concerning this problem, a k-degree anonymous privacy protection scheme based on the average degree of nodes is proposed. The scheme first depends on the greedy algorithm based on the average degree to divide social network nodes, so that the degrees of nodes in the same group are modified to the average degree, thus generating k-degree anonymous sequences; then the graph structure modification method with priority to retain important edges is used to modify the graph, thus achieving k-degree anonymity of the graph. In this scheme, the average degree is introduced when k-degree anonymous sequences are generated, which improves clustering accuracy and reduces the cost of graph structure modification. At the same time, because the indicator-neighborhood centrality, which measures the importance of edges, is considered in the graph structure modification, important edges are retained in preference, and a stable network structure is maintained. The experimental results show that this scheme improves the network resistance to degree attacks, greatly reduces information loss, and improves the utility of published data while protecting user privacy.