## 4 Tc\(\alpha\)-PIa
### Node Clustering Based on Similarity Tree
#### 5.3.2 Impact of Different Clustering Algorithms on Scheme Performance

To compare the tree clustering algorithm based on the new combined criterion proposed in this paper with the traditional Euclidean similarity clustering algorithm, we conducted an analysis under the same anonymization approach, employing the \(\alpha\)-partial isomorphism anonymization scheme for both, to explore their effect on the final experimental results. Figure 16a shows the effect of the TC\(\alpha\)-PIA scheme based on tree clustering and the traditional clustering scheme EC\(\alpha\)-PIA based on Euclidean similarity on the IL in the soc-wiki-Vote dataset. Under the same levels of anonymization, \(k\) and \(\alpha\), the IL of the TC\(\alpha\)-PIA scheme is significantly higher than that of the EC\(\alpha\)-PIA scheme, indicating that

\[IL=\delta\cdot ND(G,G^{*})+(1-\delta)\cdot ED(G,G^{*})\]3 Comparison of the change in APL on random graphs. \[IL=\delta\cdot ND(G,G^{*})+(1-\delta)\cdot ED(G,G^{*})\]4 Comparison of the error rate of EC on random graphs. the combined criterion in tree clustering takes into account more graph structural factors, thereby improving clustering accuracy and laying a foundation to reduce the modifications needed for anonymization in subsequent steps. The analysis for Figure 16b,c is similar to that for Figure 16a and is not repeated. ## 6 Conclusions

This paper proposes TC\(\alpha\)-PIA, a privacy protection scheme based on \(k\)-anonymity for undirected social network graphs. The main goal is to protect users' personal information while satisfying different privacy requirements. TC\(\alpha\)-PIA sets a threshold for structural similarity between 1-neighborhood subgraphs and anonymizes the graphs accordingly. TC\(\alpha\)-PIA involves three main steps: First, it constructs a relationship tree based on node similarity calculation and clusters nodes into distinct groups. Second, to defend against differential attacks between clusters, TC\(\alpha\)-PIA ensures that each cluster has a similar size by unifying the number of nodes across clusters. Finally, it performs \(\alpha\)-partial isomorphism anonymization on the graph. Experimental comparisons using different types and scales of datasets indicate the following: (1) TC\(\alpha\)-PIA satisfies different privacy requirements while effectively preserving graph utility, achieving a balance between privacy and utility. (2) The TC\(\alpha\)-PIA scheme is applicable to other networks that can be abstracted as consisting of nodes and edges, such as the email network dataset and the Wikipedia voting dataset used in our experiments, enabling targeted privacy protection based on user needs. As social networks expand, anonymization algorithms face efficiency challenges. Future research will focus on optimizing these algorithms to meet the demands of large-scale, complex networks while developing real-time privacy protection schemes to address dynamic changes in user information. Additionally, we will consider a broader range of user privacy requirements and integrate and enhance different privacy mechanisms to propose more comprehensive personalized privacy protection schemes. Conceptualization, M.Z. and Y.H. ; methodology, M.Z. ; software, M.Z. ; validation, M.Z. and Y.H. ; investigation, M.Z. and P.L. ; resources, L.C. ; data curation, M.Z. ; writing--original draft preparation, M.Z. ; writing--review and editing, M.Z., L.L. and Y.H. ; project administration, L.L. ; funding acquisition, L.C. All authors have read and agreed to the published version of the manuscript. This work was funded by the National Natural Science Foundation of China (Nos. U22A2099, 62462019, 62172350), the Open Project Program of Guangxi Key Laboratory of Digital Infrastructure (No. GXDIOP2024019), the Guangdong Basic and Applied Basic Research Foundation (No. 2023A1515012846), the Key Research and Development Program of Guangxi (Nos. AB24010085, AB23026120), and the Natural Science Foundation of Guangxi Province (No. 2021 GXNSFBA196054).