## 4 Tc\(\alpha\)-PIa
### Node Clustering Based on Similarity Tree
For example, connect \(v_{3}\) to \(v_{1}\) and \(v_{2}\) to \(v_{4}\), while removing the edge between \(v_{4}\) and \(v_{3}\). (3) \(v_{1}\) needs to increase its degree, while \(v_{2}\) needs to decrease its degree. We use Formulas (3) and (4) to remove the edge with the lowest centrality in \(v_{2}\)'s neighborhood and reconnect the disconnected node to \(v_{1}\). This adjustment does not affect the degree of the node previously connected to \(v_{2}\), while satisfying the requirement for increasing the degree of \(v_{1}\) and decreasing the degree of \(v_{2}\). (4) \(v_{1}\) needs to decrease its degree, while \(v_{2}\) needs to increase its degree. This process is analogous to (3), so a detailed explanation is omitted here. ### Algorithm Complexity Analysis

According to the previous chapters, TC\(\alpha\)-PIA mainly includes node clustering based on the similarity tree and anonymous graph modification based on \(\alpha\)-partial isomorphism anonymization. In the node clustering phase, the complexity of similarity calculation is \(O(n^{2})\), where \(n\) is the number of nodes. The complexity of similarity tree construction is \(O(n)\). In the branch unification of the similarity tree, nodes and branches not meeting the requirements are removed, with a complexity of \(O(l)\), where \(l\) is the number of branches. The complexity for reallocating these removed nodes and branches has two cases. In the best case, each excluded node can easily find its parent node, and the branch of the parent node can continue to accommodate its child nodes. The complexity is \(O(m)\), where \(m\) is the number of nodes removed from the branches. In the worst case, the parent node's branch cannot accommodate new nodes, and the excluded node must continuously search for the parent node. The complexity is \(O(m\cdot n)\). In summary, the best-case complexity of branch unification for the similarity tree is \(O(n^{2}+n+l+m)\), and the worst-case complexity is \(O(n^{2}+n+l+m\cdot n)\). Since \(l,m\ll n\), the overall complexity of the clustering process is approximately \(O(n^{2})\). In the graph-anonymization phase, each cluster is searched for the seed node and \(\alpha\), with a time complexity of \(O(|C|)\), where \(|C|\) represents the number of clusters identified

Figure 6: Edge modification strategy: (**a**) A degree reduction/edge deletion strategy for when there is an edge between \(v_{1}\) and \(v_{2}\). (**b**) A degree reduction/edge deletion strategy for when there is no edge between \(v_{1}\) and \(v_{2}\). (**c**) A degree increase/edge addition strategy for when there is no edge between \(v_{1}\) and \(v_{2}\). (**d**) A degree increase/edge addition strategy for when there is an edge between \(v_{1}\) and \(v_{2}\). (**e**) An edge swapping strategy for when there is no edge between \(v_{1}\) and \(v_{2}\). (**f**) An edge swapping strategy for when there is an edge between \(v_{1}\) and \(v_{2}\). after branch unification. The complexity of node anonymization in each cluster is \(O(|C_{i}|\cdot d)\), where \(|C_{i}|\) denotes the number of nodes in the cluster and \(d\) represents the average degree difference between nodes requiring modification to achieve partial \(\alpha\)-partial isomorphism with the seed node. In summary, the time complexity of TC\(\alpha\)-PIA is \(O(n^{2}+|C|\cdot|C_{i}|\cdot d)\). ### Privacy Analysis

In this section, we demonstrate the effectiveness of TC\(\alpha\)-PIA for anonymizing the social network graph structure while satisfying users' different privacy requirements. The anonymized graph obtained by the TC\(\alpha\)-PIA scheme can resist attacks from adversaries with different background knowledge. **Theorem 1**. : _For the complete or partial 1-neighborhood graph attack of any target node, the probability that the attacker can re-identify the target node's identity does not exceed 1/k._

Proof of Theorem 1.: Assume there exist two kinds of attacks according to the capability of the attacker: (1) The attacker has partial knowledge of the 1-neighbor subgraph of the target node.