## 4 Tc\(\alpha\)-PIa
### Node Clustering Based on Similarity Tree
For \(k\geq 15\), the APL change for TC\(\alpha\)-PIA(\(\alpha_{1}\)) is slightly higher than GPPS. Additionally, as \(\alpha\) decreases, the APL impact of TC\(\alpha\)-PIA decreases accordingly. Figure 9c shows the APL changes for the Facebook dataset. The results are similar to those in Figure 9a,b, so no further details are provided. Figure 8: Comparison of the change in ACC on complete graphs. Figure 9: Comparison of the change in APL on complete graphs. * **Error rate of EC. ** Figure 9(a) shows the error rate of EC on the soc-wiki-Vote dataset. All three TC\(\alpha\)-PIA schemes outperform GPPS on this metric, as TC\(\alpha\)-PIA better preserves graph structural features. Additionally, as \(\alpha\) decreases, the EC error rate for TC\(\alpha\)-PIA decreases significantly. Figure 9(b) shows the error rate of EC on the Email-Eu-core dataset. TC\(\alpha\)-PIA(\(\alpha_{3}\)) has a lower error rate than GPPS. For \(k<15\), TC\(\alpha\)-PIA(\(\alpha_{2}\)) shows a slightly higher error rate than GPPS, but for \(k>15\), it performs better. This is because TC\(\alpha\)-PIA uses triangle-structure-based similarity to minimize the impact on original nodes and controls the addition of fake nodes and edges, preserving more of the original graph's structure. TC\(\alpha\)-PIA(\(\alpha_{1}\)) performs slightly worse than GPPS due to additional matrix elements that increase graph modifications. Figure 9(c) shows the error rate of EC on the Facebook dataset. The experimental results are similar to those shown in Figure 9(a),b, and no further elaboration is needed. To clarify the impact of controlling the addition of fake nodes on the graph, we compared two approaches based on this metric. The first approach is the original TC\(\alpha\)-PIA\(second\), which merges and removes nodes after adding fake nodes. The second approach, referred to as TC\(\alpha\)-PIA\(third\), does not apply any post-processing after adding fake nodes and does not control their number. Figure 11 shows the experimental comparison results of the two approaches on three datasets, showing that TC\(\alpha\)-PIA\(second\) consistently outperforms TC\(\alpha\)-PIA\(third\). This suggests that controlling for the addition of fake nodes effectively reduces the impact on the original graph. Random graphs
* **Comparison of IL. ** Figure 12 shows the effect of TC\(\alpha\)-PIA and GPPS on IL in four random graph datasets. TC\(\alpha\)-PIA consistently outperforms GPPS for all values of \(\alpha\) and \(k\). TC\(\alpha\)-PIA performs better as \(\alpha\) decreases. As \(k\) increases, IL decreases for all methods, reflecting more graph modifications to meet stricter privacy requirements. Results from CA-CM\({}_{2}\) show worse performance than CA-CM\({}_{1}\), indicating that larger datasets require more modifications. While the results fluctuate due to dataset randomness, the overall trend is downward. Figure 11: Comparison of fake node schemes on the error rate of EC. \[IL=\delta\cdot ND(G,G^{*})+(1-\delta)\cdot ED(G,G^{*})\]0 Comparison of the error rate of EC on complete graphs. * **Change in ACC and APL. ** Figures 13 and 14 show the effect of TC\(\alpha\)-PIA and GPPS on changes in ACC and APL across random graph datasets. In almost all cases, TC\(\alpha\)-PIA results in smaller changes in ACC and APL compared to GPPS. This is because TC\(\alpha\)-PIA focuses on triangle structures during anonymization, minimizing the addition of edges. \[IL=\delta\cdot ND(G,G^{*})+(1-\delta)\cdot ED(G,G^{*})\]1 Comparison of IL on random graphs. \[IL=\delta\cdot ND(G,G^{*})+(1-\delta)\cdot ED(G,G^{*})\]2 Comparison of the change in ACC on random graphs. * **Error rate of EC. **

Figure 15 shows the effect of different schemes on the EC error rate in four random graph datasets. The trend is similar to that in Figure 10, with analogous analysis and underlying reasons.