## 4 Tc\(\alpha\)-PIa
### Node Clustering Based on Similarity Tree
\(d_{i}\) is the node's degree, \(E_{gi}\) is the number of edges in the 1-neighborhood subgraph \(g_{i}\) of the node, \(\Delta_{i}\) represents the triangles involving the node, and \(OE_{\Delta_{i}}\) is the overlapping edge of participating triangles. The last two factors, \(\Delta_{i}\) and \(OE_{\Delta_{i}}\), account for the stability of the triangle structures and the number of participating paths, thus better capturing the 1-neighborhood subgraph structure. After calculating the similarity, the results are stored in a list \(\mathbf{D}\) of size \(n\times 2\). \(\mathbf{D}(i,0)\) stores the similarity values between \(v_{i}\) and other nodes in ascending order, denoted as \(Sim(v_{i})=\{Sim(v_{i},v_{j})\mid i,j=1,2,\ldots,n-1\) and \(i\
eq j\}\). \(\mathbf{D}(i,1)\) stores the corresponding nodes in the order of \(Sim(v_{i})\), denoted as \(PN(v_{i})=\{v_{j}\mid j=1,2,\ldots,n-1\}\). Figure 2: Example of triangles involving the node: (**a**) Original graph. (**b**) The 1-neighborhood subgraph of \(v_{2}\) containing two participating triangles \((v_{1},v_{2},v_{3})\) and \((v_{2},v_{3},v_{5})\) and one overlapping edge \((v_{2},v_{3})\). \[\mathbf{D}= \begin{pmatrix}sim(v_{1})&PN(v_{1})\\ sim(v_{2})&PN(v_{2})\\ \vdots&\vdots\\ sim(v_{n})&PN(v_{n})\end{pmatrix} \]

**Step 2: similarity tree construction. ** To ensure tight connections within clusters, we construct a similarity tree based on the calculated similarities. Each node is connected to its most similar node, referred to as the parent node, forming the branches of the tree. For nodes that are most similar but not identical, such as \(v_{2}\) and \(v_{6}\) in Table 1, one node is randomly chosen as the parent and the other as the child to form the relationship tree. Nodes without a parent node are connected directly to the root node, which is used only for tree construction and does not correspond to an actual node in the graph, nor does it participate in the clustering process. Each branch under the root node represents a cluster. The relevant definitions are as follows:

**Definition 10** (Parent-child node relationship). : _For each \(v_{i}\), identify the \(v_{j}\) that is most similar to \(v_{i}\) by selecting the first element in \(PN(v_{i})\), denoted as \(P(v_{i})=PN(v_{i})[1]\), where \(P(v_{i})\) is the parent node of \(v_{i}\)._

Table 1 and Figure 3 show the establishment of parent-child relationships and the construction process of the similarity tree, respectively. Each node is directly connected to its parent node, \(P(v_{i})\). For example, both \(v_{7}\) and \(v_{4}\) have the same parent node, \(v_{6}\), and are directly connected to it. In cases where nodes are most similar, such as \(v_{2}\) and \(v_{6}\), one node is randomly selected as the parent. Here, \(v_{2}\) is chosen as the parent of \(v_{6}\); similarly, the relationship between \(v_{3}\) and \(v_{5}\) is established in the same manner. Consequently, we obtain two branches in Figure 3a: \(\{v_{2},v_{6},v_{7},v_{4},v_{8},v_{9}\}\) and \(\{v_{3},v_{5},v_{1}\}\). From Figure 3a, it is clear that \(v_{2}\) and \(v_{3}\) do not have parent nodes. For such nodes, we directly connect them to the root node; i.e., \(v_{2}\) and \(v_{3}\) are connected directly to the root node, as indicated by the text \"root\" in Table 1. \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \(v_{i}\) & \(v_{1}\) & \(v_{2}\) & \(v_{3}\) & \(v_{4}\) & \(v_{5}\) & \(v_{6}\) & \(v_{7}\) & \(v_{8}\) & \(v_{9}\) \\ \hline \(P(v_{i})\) & \(v_{5}\) & \(v_{6}\) & \(v_{5}\) & \(v_{6}\) & \(v_{3}\) & \(v_{2}\) & \(v_{6}\) & \(v_{7}\) & \(v_{8}\) \\ \hline \end{tabular}
\end{table} 
Table 1: Example of parent–child node relationship. **Step 3: branch unification of the similarity tree. ** The varying branch sizes in the similarity tree can cause differences in anonymity levels and increase the risk of information leakage. We unified branches of the similarity tree, ensuring that all clusters were of the same size.