## 4 Tc\(\alpha\)-PIa
### Node Clustering Based on Similarity Tree
Since not all users require weak privacy, TC\(\alpha\)-PIA\({}_{\text{second}}\) results in slightly lower IL compared to TC\(\alpha\)-PIA(\(\alpha_{3}\)). However, it outperforms TC\(\alpha\)-PIA(\(\alpha_{2}\)), TC\(\alpha\)-PIA(\(\alpha_{1}\)), and GPPS by considering different privacy requirements, rather than applying a uniform \(\alpha\). This reduces unnecessary modifications and makes anonymization more efficient, preserving more of the original graph structure. Figure 7b,c show the results for the Email-Eu-core and Facebook datasets, respectively. In Figure 7b, TC\(\alpha\)-PIA(\(\alpha_{3}\)) significantly outperforms GPPS. For \(k<20\), the IL of TC\(\alpha\)-PIA(\(\alpha_{2}\)) is comparable to that of GPPS, while TC\(\alpha\)-PIA(\(\alpha_{1}\)) performs slightly worse. The analysis for TC\(\alpha\)-PIA\({}_{\text{second}}\) is consistent with the findings in Figure 7a. Overall, TC\(\alpha\)-PIA performs better on the soc-wiki-Vote dataset, and all four TC\(\alpha\)-PIAs outperform GPPS with different parameters because they are better suited for uniformly distributed and moderately sized graph networks. * **Change in ACC. ** Figure 8a shows the effect of different schemes on ACC in the soc-wiki-Vote dataset. TC\(\alpha\)-PIA consistently has a lower rate of change in ACC compared to GPPS, indicating

Figure 7: Comparison of IL on complete graphs. better performance. This result is attributed to the fact that TC\(\alpha\)-PIA considers the triangle structure and number during structural anonymization, which helps to preserve more original edges and structures. As \(k\) increases, the impact of each scheme on the ACC gradually increases, i.e., the difference between the anonymized graph and the original graph increases. This is because higher anonymity levels lead to more changes in the graph. In the TC\(\alpha\)-PIA scheme, a smaller \(\alpha\) results in less disruption to the original graph structure, as indicated by a lower effect on the ACC. The performance of TC\(\alpha\)-PIA\({}_{\text{second}}\) follows a similar trend but outperforms TC\(\alpha\)-PIA (\(\alpha_{2}\)), TC\(\alpha\)-PIA (\(\alpha_{1}\)), and GPPS due to its more personalized approach to user privacy requirements. Figure 8b shows the experimental results for the Email-Eu-core dataset. Under the TC\(\alpha\)-PIA scheme, the change in ACC decreases as \(\alpha\) decreases, mirroring the trend observed for the soc-wiki-Vote dataset in Figure 8a. Therefore, no further details are needed. Compared to GPPS, TC\(\alpha\)-PIA(\(\alpha_{3}\)) consistently shows a lower change in ACC for all \(k\) values. At \(k=15\), TC\(\alpha\)-PIA(\(\alpha_{2}\)) exhibits slightly higher fluctuations than GPPS, but remains lower for other \(k\) values. This fluctuation is due to the non-uniformity of the dataset, but overall TC\(\alpha\)-PIA(\(\alpha_{2}\)) outperforms GPPS. For \(k<20\), TC\(\alpha\)-PIA(\(\alpha_{1}\)) shows a higher change in ACC compared to GPPS, due to the formation of additional triangles for a stable structure. However, for \(k>20\), TC\(\alpha\)-PIA(\(\alpha_{1}\)) gradually outperforms GPPS. Figure 8c compares the TC\(\alpha\)-PIA and GPPS schemes on the Facebook dataset. The analysis is similar to that of Figure 8a,b. * **Change in APL. ** Figure 9a shows the APL changes for the soc-wiki-Vote dataset. For all \(k\) values, the APL changes for TC\(\alpha\)-PIA(\(\alpha_{1}\)), TC\(\alpha\)-PIA(\(\alpha_{2}\)), TC\(\alpha\)-PIA(\(\alpha_{3}\)),and TC\(\alpha\)-PIA\({}_{\text{second}}\) are consistently lower than those for GPPS. This is because TC\(\alpha\)-PIA considers edges that participate more frequently in the shortest paths during anonymization, thus preserving more connection paths between nodes in the original graph. Figure 9b shows the APL changes for the Email-Eu-core dataset. TC\(\alpha\)-PIA(\(\alpha_{2}\)) and TC\(\alpha\)-PIA(\(\alpha_{3}\)) exhibit significantly lower APL changes compared to GPPS. For \(k<15\), the results for TC\(\alpha\)-PIA(\(\alpha_{1}\)) are similar to those of GPPS.