## 4 Tc\(\alpha\)-PIa
### Node Clustering Based on Similarity Tree
(3) Third, since the anonymization process described in Step 2 may involve the addition of fake nodes, we propose a node-merging strategy. This strategy evaluates pairs of fake nodes to determine whether they can be merged without compromising the privacy of the connected nodes. If merging fake nodes changes their 1-neighborhood structure and does not satisfy the \(\alpha_{i}\) structure anonymity requirements for the connected nodes, then the fake nodes should not be merged. This approach ensures privacy while optimizing the graph structure and minimizing the disruption caused by the addition of fake nodes (lines 38-42). Figure 5: \(\alpha\)-partial isomorphism: (**a**) Original graph \(G\). (**b**) Select the seed node with the largest number of neighbors and maximum \(\alpha_{i}\) value in each cluster. (**c**) Establish the mapping relationship between the 1-neighborhood subgraph of a node and the 1-neighborhood subgraph of the seed node in each cluster. (**d**) Modify the 1-neighborhood subgraph structure of a node to achieve \(\alpha_{i}\)-partial isomorphism by referencing the 1-neighborhood structure of the seed node. (**e**) Anonymized graph \(G^{\sim}\). (**f**) Merge the fake nodes to obtain the final anonymized graph \(G^{*}\). ```
0:\(G(V,E)\), Structure level anonymity threshold \(\alpha\)
0:Anonymized graph \(G^{*}\)
1:for\(i=1\) to C do
2: Find seed node in \(C_{i}\)
3: determine the maximum \(\alpha_{i}\) value in \(C_{i}\)
4:for node in \(C_{i}\)do
5:if\(\text{sim}(\text{node},\text{seed})<\alpha_{i}\)then
6: Add \((d_{\text{seed}}-d_{\text{node}})\) fake nodes into \(g_{\text{node}}\)
7: Sort the nodes in subgraph \((g_{\text{seed}},g_{\text{node}})\) according to degree
8:\(M_{p}(g_{\text{seed}}.g_{\text{node}})\leftarrow\text{Mapping node in seed node}\)
9:\(MD(g_{\text{seed}},g_{\text{node}})\leftarrow\text{Mapping matrix}\)
10:\(S_{1}\leftarrow\emptyset\), \(S_{2}\leftarrow\emptyset\)
11:for\(v\) in \(g_{\text{node}}\)do
12:if\(d_{v}<d_{M_{v}(v,\text{seed})}\)then
13: Add \(v\) into \(S_{1}\)
14:elseif\(d_{v}>d_{M_{v}(v,\text{seed})}\)then
15: Add \(v\) into \(S_{2}\)
16:endif
17:endfor
18:for\(v_{1},v_{2}\) in \(S_{1}\)do
19: Add the edge(\(v_{1},v_{2}\))
20:endfor
21:for\(v_{1},v_{2}\) in \(S_{2}\)do
22:if\(d_{v_{1}}>d_{M_{v}(v_{1},\text{seed})}\) and \(v_{2}\in g_{v_{1}}\) and \(\min\{NC_{\text{remove}}(v_{1},v_{2})\}\)then
23: Remove the edge(\(v_{1},v_{2}\))
24:endif
25:endfor
26: Update \(S_{1},S_{2}\)
27:if\(\text{sim}(\text{node},\text{seed})<\alpha_{i}\)then
28: Matching triangle structures with \(MD(g_{\text{seed}}.g_{\text{node}})\)
29: Repeat similar steps 6-27
30:if\(\text{sim}(\text{node},\text{seed})<\alpha_{i}\)then
31: Modify edges using \(MD\)
32:endif
33: Repeat until \(\text{sim}(\text{node},\text{seed})\geq\alpha_{i}\)
34:endif
35:endif
36:endfor
37:endfor
38:for each fake node pair \((f_{1},f_{2})\)do
39:if No node privacy is compromised by merging \(f_{1}\) and \(f_{2}\)then
40: Merge fake nodes \(f_{1}\) and \(f_{2}\)
41:endif
42:endforreturn\(G^{*}\)
```

**Algorithm 3** Graph anonymity

Figure 6 shows examples of edge addition and deletion in the Algorithm 3, covering cases not illustrated in Figure 5.

(1) Both \(v_{1}\) and \(v_{2}\) need to decrease their degrees. If there is an edge between \(v_{1}\) and \(v_{2}\), delete the edge between the two nodes. If there is no edge between \(v_{1}\) and \(v_{2}\), use Formulas (3) and (4) to find and delete the edge with the least effect. To ensure the degrees of \(v_{3}\) and \(v_{4}\) remain unchanged, add an edge between them. (2) Both \(v_{1}\) and \(v_{2}\) need to increase their degrees. If there is no edge between \(v_{1}\) and \(v_{2}\), add one. If an edge already exists between \(v_{1}\) and \(v_{2}\), find non-adjacent nodes for \(v_{1}\) and \(v_{2}\), and connect them to \(v_{1}\) and \(v_{2}\), respectively. To maintain the original degrees, the existing edge between the newly connected nodes should be removed.