## 4 Tc\(\alpha\)-PIa
### Node Clustering Based on Similarity Tree  
This section proposes a clustering method by constructing the similarity tree. This method groups similar nodes into multiple clusters, denoted as \(\mathcal{C}=\{\mathcal{C}_{1},\mathcal{C}_{2},\ldots,\mathcal{C}_{T}\}\), where \(T\) is the number of clusters. In Algorithm 1, the process is divided into three main steps. First, we compute the similarity between each pair of nodes (lines 1-15). Second, we construct a similarity tree based on the similarity results (lines 16-26). Finally, we perform branch unification on the constructed similarity tree to minimize inter-cluster differences (line 27). The details are as follows. ```
0: Original graph \(G(V,E)\), anonymity parameter \(k\), number of nodes \(n\)
0: Number of clusters \(C\), ordered similarity list \(D\), similarity tree \(Tree\)
1:for\(i=1\) to \(n\)do
2: Compute \(\mathbf{x}_{i}=<d_{i},E_{\mathcal{S}_{i}},\Delta_{i},OE_{\Delta_{i}}>\) for each node
3:endfor
4:\(m=0\)
5:for\(i=1\) to \(n\)do
6:for\(j=i+1\) to \(n\)do
7: Calculate the similarity of each node 1-neighborhood graph
8:endfor
9:\(M=\) Sort Based on Similarity
10:for\(z=1\) to \(n\)do
11:\(D(m,0)=M(z-1,0)\)
12:\(D(m,1)=M(z-1,1)\)
13:\(m=m+1\)
14:endfor
15:endfor
16:\(m=0\), \(Tree\leftarrow\) null, \(Tree.root\leftarrow\) null
17:for\(i=1\) to \(n\)do
18:\(v_{i}.parent\gets D(m,1)\)
19:\(v_{i}.parent.children\gets v_{i}\)
20:\(m=m+n\)
21:endfor
22:for\(i=1\) to \(n\)do
23:if\(v_{i}.parent\) is nullthen
24:\(v_{i}.parent\gets Tree.root\)
25:endif
26:endfor
27: Branch Unification seeing Algorithm 2 return\(C\), \(D\), Tree

Figure 1: An overview of TCa-PIA. Step 1: node similarity calculation.The similarity between each pair of nodes is calculated by the combined criterion, which includes four factors: the node's degree, the number of edges in the 1-neighborhood subgraph of the node, the number of triangles in which the node participates (triangles involving the node), and the number of common edges of triangles in which the node participates (overlapping edge of participating triangles). The latter two factors are further given as follows:

**Definition 8** (Triangles involving the node). : _An undirected and unlabeled original graph \(G(V,E)\), where \(V=V(G)\) is the set of nodes and \(E=E(G)\) is the set of edges. The triangles involving the node \(v\) are defined as \(\Delta(v)=\{v\mid z\in V\wedge u\in V\wedge(u,v)\in E(G)\wedge(v,z)\in E(G) \wedge(u,z)\in E(G)\}\), where \(u\), \(v\), and \(z\) are nodes in \(G\). For example, Figure 2a is the 1-neighborhood subgraph of \(v_{2}\). It contains two triangles: one comprises \(v_{1}\), \(v_{2}\), and \(v_{3}\), and the other comprises \(v_{2}\), \(v_{3}\), and \(v_{5}\). For ease of understanding, we will use the term \"participating triangle\" in the following._

**Definition 9** (Overlapping edge of participating triangles). : _An undirected, unlabeled graph \(G(V,E)\), where \(V\) is the set of nodes and \(E\) is the set of edges. We define the common edge between several participating triangles in Definition 10 as the overlapping edge of the participating triangles: \(OE=\{(u,v)\mid u,v\in V\wedge(u,v)\in E(\Delta_{1})\cap E(\Delta_{2})\wedge E (\Delta_{1}),E(\Delta_{2})\in E\}\). For example, the red line in Figure 2b is the common edge between the above two triangles._

Then, we give the formula of similarity calculation based on the four factors mentioned above. \[\Delta f=\big{\|}\mathbf{x}_{i}-\mathbf{x}_{j}\big{\|}. \tag{1}\]

\[\mathbf{x}_{i}=<d_{i},E_{gi},\Delta_{i},OE_{\Delta_{i}}>. \tag{2}\]

where \(\Delta f\) is the similarity function, and the smaller its result, the higher the similarity between two nodes. \(\mathbf{x}_{i}\) is a vector about the node \(v_{i}\), and it includes four factors: \(d_{i}\), \(E_{gi}\), \(\Delta_{i}\), and \(OE_{\Delta_{i}}\).