## 4 Tc\(\alpha\)-PIa
### Node Clustering Based on Similarity Tree
(2) The attacker has complete knowledge of the 1-neighbor subgraph of the target node. **Partial protection analysis. ** The attacker has a partial 1-neighbor subgraph structure of the target node. In this scenario, the attacker's matching results may be biased, and cannot be guaranteed to fully match the corresponding node clusters. In addition, it can be guaranteed that at least \(k-1\) nodes have a 1-neighbor subgraph identical to that of the target node. Therefore, the probability that the attacker can uniquely identify the target node is not higher than \(1/k\). **Complete protection analysis. ** The attacker has completed the 1-neighbor subgraph structure of the target node. Since our scheme allows subgraphs to be isomorphic, at least \(k-1\) nodes will have the same 1-neighborhood subgraph as the target node. Therefore, TC\(\alpha\)-PIA satisfies the anonymity requirement; i.e., the probability that the attacker can uniquely identify the target node is no higher than \(1/k\). ## 5 Experimental Evaluations

In Section 5.1, we introduce the datasets used in the experiments. In Section 5.2, we describe the metrics used to evaluate the experimental results. In Section 5.3, we explore the performance of TC\(\alpha\)-PIA and the comparative experiment. ### Datasets

Four real datasets are used in our experiments, and their statistics are shown in Table 3.

* The Facebook dataset [36] from SNAP, with 4039 nodes representing users and 88,234 edges representing relationships. * The Ca-CondMat dataset [36] on condensed matter physics, with 23,133 nodes representing papers and 186,936 edges representing co-authorship. * The email-Eu-core dataset [36], with 986 nodes representing users and 25,571 edges representing email communications. * The soc-wiki-Vote dataset [37], with 889 nodes representing Wikipedia users and 2916 edges representing voting interactions. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Dataset** & \(|N|\) & \(|E|\) & **AVD** & **ACC** & **APL** \\ \hline Facebook & 4039 & 88,234 & 44 & 0.605 & 4.7 \\ CA-CondMat & 23,133 & 186,936 & 8 & 0.633 & 6.4 \\ email-Eu-core & 986 & 24,929 & 32.58 & 0.407 & 2.587 \\ soc-wiki-Vote & 889 & 2914 & 6.56 & 0.153 & 4.096 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Real-world graph datasets. ### Utility Metrics

To evaluate the proposed TC\(\alpha\)-PIA scheme, we used the following metrics:

* **Information Loss (IL)**. IL refers to the data difference between the modified graph and the original graph after modifications. Modifications include adding or deleting nodes and edges, and edge swapping, which can cause information loss in the original graph. The formula for calculating the information loss [13] is as follows. \[IL=\delta\cdot ND(G,G^{*})+(1-\delta)\cdot ED(G,G^{*})\] (5) where \[ND=\frac{1}{2}\cdot(\frac{|N(G)\cap N(G^{*})|}{|N(G)|}+\frac{|N(G)\cap N(G^{* })|}{|N(G^{*})|})\] (6) \[ED=\frac{1}{2}\cdot(\frac{|E(G)\cap E(G^{*})|}{|N(G)|}+\frac{|E(G)\cap E(G^{* })|}{|N(G^{*})|})\] (7) where \(ED\) represents the information loss of edges, \(ND\) represents the information loss of nodes, \(E(G)\) represents the edges of the original graph, \(E(G^{*})\) represents the edges of the anonymized graph, and \(ND(G)\) and \(ND(G^{*})\) represent the nodes in the original and anonymized graphs, respectively. \(\delta\) represents the weight parameter, with a value range of [0,1]. The above formula can calculate different results based on the different emphases of the anonymity scheme on nodes and edges in the graph. In general, the larger the calculated result, the higher the degree of information preservation from the original graph. * **Average Clustering Coefficient (ACC)**. ACC focuses on the closeness between nodes, that is, the number of connections between nodes. The change in ACC can reveal the degree of change in the connection relationship between nodes in the graph after anonymization.