## 4 Tc\(\alpha\)-PIa
### Node Clustering Based on Similarity Tree
As shown in Figure 3b,c, when \(k=3\), we split the branches that contained significantly more than three nodes. Starting from the bottom, we divided \(v_{9}\), \(v_{8}\), and \(v_{7}\) from the branch to form an independent branch and connected it to the root node. Algorithm 2 presents the details for the branch unification of the similarity tree. The key steps are as follows: (1) Traverse each branch of the similarity tree and perform removal or splitting operations on nodes within the branches (lines 2-10) to achieve a unified number of nodes among branches. The quality of clustering is ensured by rationalizing and reassigning nodes and tree branches. (2) Mark branches with more than \(k\) nodes and those with significantly fewer than \(\sqrt{k}\) nodes. Remove the excess nodes from branches with more than \(k\) nodes and eliminate branches with fewer nodes than \(\sqrt{k}\). Based on the similarity results, reassign the removed nodes to the next-most-similar parent node as sub-nodes of that node (lines 11-19). (3) To maintain clustering quality, check the number of neighbors for the nodes within each branch. Remove nodes with significant differences in similarity and reassign them to the next-most-similar node (lines 20-26). ```
1:\(k\), \(D\), tree root Tree\(\_\)root
2:\(C\), Tree
3:\(S\gets Q\), Tree\(\_\)root \(\_\)root
4:for branch in root.children do\(\triangleright\) Iterate through branches under the root node
5:if\(|\text{branch}|\ll\sqrt{k}\)then
6: Remove the branch from root and add nodes from the branch to \(S\)
7:elseif\(|\text{branch}|>k\)then
8: Place the remaining \(|\text{branch}\%k|\) in \(S\)
9:\(R_{\text{ij}}\leftarrow\) Divide branch into equal branches
10: Add \(R_{\text{hi}}\) into \(\textit{root.children}\)\(\triangleright\) Split the branch and connect to the root node
11:endif
12:endfor
13:while\(S\) not empty do\(\triangleright\) Search for the next parent for the removed nodes
14:for\(i=1\) to \(|S|\)do
15: Find next parent node \(p_{v_{i}}\) from \(D\)
16:if\(|\text{branch}(p_{v_{i}})|\leq k\)then
17:\(v_{i}\).parent \(\leftarrow\)\(p_{v_{i}}\)
18: Remove \(v_{i}\) from \(S\)
19:endif
20:endfor
21:endwhile
22:\(S\leftarrow\emptyset\)
23:forbranch in root.children do
24: Remove nodes with significant differences
25: Add nodes to \(S\)
26:endfor
27:Repeat steps 12-19 until \(S\) is empty
28: Update Tree, \(C\leftarrow\) branches returnC, Tree
```
**Algorithm 2** Branch unification

### Graph Anonymity Modification Based on \(\alpha\)-Partial Isomorphism

After clustering nodes, this section anonymizes nodes within each cluster using the proposed \(\alpha\)-partial isomorphism. This method includes the following steps: (1) Select seed nodes and determine \(\alpha\) values for each cluster. (2) Establish the mapping relationship between the 1-neighborhood graph of the node and the 1-neighborhood graph of the seed node in each cluster. (3) Based on the mapping relationship, establish a mapping matrix between the nodes and their corresponding seed nodes. Compare the structural information in the matrix and calculate the percentage of identical structures. Then, compare thisproportion with the \(\alpha\) value and perform the necessary anonymization modifications based on the requirements. We first give the relevant definitions before presenting the \(\alpha\)-partial isomorphism algorithm. **Definition 11** (Mapping relationship). : _Given a graph \(G(V,E)\), where \(g(v)\) and \(g(u)\) are \(1\)-neighborhood subgraphs of nodes \(v\) and \(u\) in \(G\)., if there is a correspondence between nodes in \(g(v)\) and \(g(u)\), then there is mapping between \(g(v)\) and \(g(u)\), denoted as \(f:g(v)\to g(u)\). Figure 4 and Table 2 show an example of a mapping relationship._

**Definition 12** (Centrality of edge neighborhood [23]).