## 1 Introduction  
With the rise of social platforms like WeChat and Twitter, a vast number of users have joined, forming large-scale social networks and generating massive amounts of data. This published data has significant value, and social network operators often share user relationship graphs and other information with third parties [1] to facilitate data analysis and mining, social group analysis, and personalized recommendations. However, directly publishing unprocessed data poses significant privacy risks for things such as privacy theft attacks, identity attacks, and social relationship inference attacks. To protect user privacy in social networks, various privacy-preserving mechanisms have been widely employed, such as naive anonymization mechanisms [2], \(k\)-anonymity [3; 4; 5], encryption techniques [6; 7; 8], and differential privacy [9; 10; 11; 12]. Naive anonymization replaces identity information in social network data with random pseudo-identities, effectively defending against zero-knowledge adversaries. However, it fails to protect against attackers who possess knowledge of the graph structure. Encryption techniques encrypt social network data to protect the privacy of sensitive information. However, these techniques are costly in terms of data encryption, decryption, and key management. Additionally, they lack flexibility and are vulnerable to privacy attacks once the key has been compromised. Differential privacy introduces noise into data and has been widely applied in data mining, machine learning, and data analysis due to its theoretical security and ease of implementation [13]. However, the added noise can reduce the accuracy of data analysis, affecting the practical utility of the data. In contrast, \(k\)-anonymity is based on the concept of data generalization, ensuring that each node in the graph is indistinguishable from at least \(k-1\) other nodes by adding or deleting nodes and/or edges in the social network graph. This significantly reduces the possibility of attackers identifying users to \(1/k\). In summary, \(k\)-anonymity provides stronger anonymity than naive mechanisms, avoids the high computational overhead and complex key management required by encryption techniques, and is easier to understand and implement compared to differential privacy. Many efforts have been made to develop an efficient \(k\)-anonymity scheme. For example, [PERSON] et al. [14] proposed an EDPSO algorithm based on \(k\)-anonymity. This algorithm clusters nodes and edges in the network into super-nodes and super-edges to protect the structural information of individuals, thereby protecting user privacy. Although this approach effectively protects structural privacy, it does not address the personalized anonymization needs of users, indicating potential for further improvement. [PERSON] et al. [15] proposed the GCA-DA algorithm. This algorithm clusters nodes by quantifying the distance and attribute similarity between them, ensuring that each cluster contains at least \(k\) nodes before anonymizing them. It protects privacy through attribute generalization and distinguishes between numerical and non-numerical attributes to maintain data usability. While this approach enhances clustering quality, it lacks flexibility. [PERSON] et al. [16] introduced a social network privacy protection scheme called GPPS. This scheme first employs degree-based graph entropy and spectral clustering algorithms for cluster nodes, and then adjusts 1-neighborhood graphs using a maximum weight bipartite matching method to achieve \(k\)-anonymity. However, it does not focus on graph isomorphism and fails to consider different user privacy requirements, indicating that the scheme can be further improved. Therefore, to effectively address the aforementioned problems and balance the privacy and utility of the anonymity scheme in social networks, this paper proposes a similarity tree clustering method and an \(\alpha\)-partial isomorphism anonymization scheme based on the concepts of clustering and isomorphism.