## 4 Tc\(\alpha\)-PIa
### Node Clustering Based on Similarity Tree
: _The neighborhood centrality of an edge is used to measure the importance or centrality of an edge in a network, which describes the influence of an edge \((v_{i},v_{j})\) in its neighborhood and can be expressed by the following equation:_

\[NC\{v_{i},v_{j}\}=\frac{|\Gamma(v_{i})\cup\Gamma(v_{j})|-|\Gamma(v_{i})\cap \Gamma(v_{j})|}{2 max(deg)}. \tag{3}\]

_where \(NC\) represents the neighborhood centrality of the edge \((v_{i},v_{j})\), and \(\Gamma(v_{i})\) denotes the number of neighbors of node \(v_{i}\). Since the edges between two nodes are removed randomly, there is a risk of destroying the triangles in the graph. Therefore, based on the above definition, this paper uses the edge participation measure mentioned in Definition 11 to minimize the effect on the triangle structure. The calculation is as follows:_

\[NC\_remove(v_{i},v_{j})=NC(v_{i},v_{j})\times(r_{\Delta_{g_{i}}}+1) \tag{4}\]

_where \(NC\_remove(v_{i},v_{j})\) is the edge to be removed._

Figure 5 provides an example to illustrate the process of \(\alpha\)-partial isomorphism anonymization based on the above definitions. (1) First, the seed node, highlighted in red, is selected as the node with the largest number of neighbors in each cluster. Simultaneously, the maximum \(\alpha\) value for each cluster is determined and labeled as \(\alpha_{i}\) (\(i=1,2,3,4\)), also highlighted in red in Figure 5. (2) Next, we establish the mapping relationship between the \(1\)-neighborhood graph of each node and the \(1\)-neighborhood graph of the seed node in descending order by node degree within each cluster, and establish mapping matrices _MD_. For illustration, we use cluster \(C_{2}\), which contains nodes \(v_{2}\) and \(v_{3}\), with a similar process applied to other clusters. We calculate the percentage of identical structures between nodes \(v_{2}\) and \(v_{3}\) by comparing the common edges in the _MD_, where \(MD[i][j]=1\) indicates the presence of an edge between the two nodes and \(MD[i][j]=0\) indicates its absence. Although \(v_{2}\) and \(v_{3}\) have the same \(1\)-neighborhood structure with six identical edges, the unequal number of neighbors means that \(\alpha_{2}\) (\(100\%\))-partial isomorphism is not satisfied. To achieve

\begin{table}
\begin{tabular}{c c c} \hline \hline \(g_{i}\) & **Degree\_Sequence** & **Map\



structural isomorphism with the seed node \(v_{2}\), a fake node \(f_{1}\) is added and connected to \(v_{3}\). (3) After modifications within all clusters, the fake nodes are merged to avoid the excessive addition of fake nodes, as shown in Figure 5. Merging \(f_{1}\) and \(f_{2}\) is effective because it does not compromise the privacy of nodes \(v_{3}\) and \(v_{8}\). Algorithm 3 presents a detailed description of graph anonymity based on \(\alpha\)-partial isomorphism anonymization. (1) First, the node with the largest number of neighbors in each cluster is selected as the seed node, and the maximum value of \(\alpha_{i}\) is determined for each cluster \(C_{i}\) (lines 1-3). The selection of \(\alpha_{i}\) is based on the privacy threshold specified by the users. The privacy requirements of the users are classified into three levels, strong, medium, and weak, corresponding to the intervals [0%, 30%], (30%, 60%], and (60%, 100%], respectively. \(\alpha_{i}\) is determined by identifying the highest privacy requirement within each cluster. For example, if the privacy requirements of three users in cluster \(C_{i}\) are 25%, 52%, and 20%, then \(\alpha_{1}\) is set to 52% for \(C_{i}\), indicating a medium privacy requirement. (2) Second, after selecting the seed node and max \(\alpha_{i}\) in each cluster, we use the mapping matrix to evaluate the structural similarity between the seed node and other nodes. If the similarity meets the threshold \(\alpha_{i}\), these nodes are considered isomorphic to the seed node and require no further anonymization. Otherwise, we adjust their 1-neighborhood subgraph structures until \(\alpha_{i}\) is reached (lines 4-37).