This paper addresses the problem of graph anonymization, specifically focusing on k-degree anonymity. The goal is to modify a graph so that each node has the same degree as at least k-1 other nodes, thereby preventing re-identification of individuals. The authors propose a framework for achieving this by modifying the graph with minimal edge additions or deletions. They define a k-degree anonymous graph as one where every node has the same degree as at least k-1 other nodes. The problem is formalized as finding a k-degree anonymous graph that requires the minimum number of modifications to the original graph. The authors develop algorithms based on principles related to the realizability of degree sequences. They apply their methods to a wide range of synthetic and real datasets, demonstrating the efficiency and practical utility of their approach. The paper also discusses related work, including previous studies on graph anonymization and privacy concerns in social networks. The authors propose a two-step approach for solving the graph anonymization problem: first, constructing a k-anonymous degree sequence with minimal modifications, and then constructing a graph with that degree sequence. They present algorithms for both steps, including dynamic programming and greedy approaches. The paper also discusses the realizability of degree sequences and presents algorithms for constructing graphs with specific degree sequences. The authors conclude that their approach provides an effective solution for graph anonymization while preserving the utility of the original graph.This paper addresses the problem of graph anonymization, specifically focusing on k-degree anonymity. The goal is to modify a graph so that each node has the same degree as at least k-1 other nodes, thereby preventing re-identification of individuals. The authors propose a framework for achieving this by modifying the graph with minimal edge additions or deletions. They define a k-degree anonymous graph as one where every node has the same degree as at least k-1 other nodes. The problem is formalized as finding a k-degree anonymous graph that requires the minimum number of modifications to the original graph. The authors develop algorithms based on principles related to the realizability of degree sequences. They apply their methods to a wide range of synthetic and real datasets, demonstrating the efficiency and practical utility of their approach. The paper also discusses related work, including previous studies on graph anonymization and privacy concerns in social networks. The authors propose a two-step approach for solving the graph anonymization problem: first, constructing a k-anonymous degree sequence with minimal modifications, and then constructing a graph with that degree sequence. They present algorithms for both steps, including dynamic programming and greedy approaches. The paper also discusses the realizability of degree sequences and presents algorithms for constructing graphs with specific degree sequences. The authors conclude that their approach provides an effective solution for graph anonymization while preserving the utility of the original graph.