  The rapid growth of computer systems which generate graph data necessitates
employing privacy-preserving mechanisms to protect users' identity. Since
structure-based de-anonymization attacks can reveal users' identity's even when
the graph is simply anonymized by employing naive ID removal, recently,
$k-$anonymity is proposed to secure users' privacy against the structure-based
attack. Most of the work ensured graph privacy using fake edges, however, in
some applications, edge addition or deletion might cause a significant change
to the key property of the graph. Motivated by this fact, in this paper, we
introduce a novel method which ensures privacy by adding fake nodes to the
graph.
  First, we present a novel model which provides $k-$anonymity against one of
the strongest attacks: seed-based attack. In this attack, the adversary knows
the partial mapping between the main graph and the graph which is generated
using the privacy-preserving mechanisms. We show that even if the adversary
knows the mapping of all of the nodes except one, the last node can still have
$k-$anonymity privacy.
  Then, we turn our attention to the privacy of the graphs generated by
inter-domain routing against degree attacks in which the degree sequence of the
graph is known to the adversary. To ensure the privacy of networks against this
attack, we propose a novel method which tries to add fake nodes in a way that
the degree of all nodes have the same expected value.
