  In this paper, we incorporate the realistic scenario of key protection into
link privacy preserving and propose the target-link privacy preserving (TPP)
model: target links referred to as targets are the most important and sensitive
objectives that would be intentionally attacked by adversaries, in order that
need privacy protections, while other links of less privacy concerns are
properly released to maintain the graph utility. The goal of TPP is to limit
the target disclosure by deleting a budget limited set of alternative
non-target links referred to as protectors to defend the adversarial link
predictions for all targets. Traditional link privacy preserving treated all
links as targets and concentrated on structural level protections in which
serious link disclosure and high graph utility loss is still the bottleneck of
graph releasing today, while TPP focuses on the target level protections in
which key protection is implemented on a tiny fraction of critical targets to
achieve better privacy protection and lower graph utility loss. Currently there
is a lack of clear TPP problem definition, provable optimal or near optimal
protector selection algorithms and scalable implementations on large-scale
social graphs. Firstly, we introduce the TPP model and propose a dissimilarity
function used for measuring the defense ability against privacy analyzing for
the targets. We consider two different problems by budget assignment settings:
1) we protect all targets and to optimize the dissimilarity of all targets with
a single budget; 2) besides the protections of all targets, we also care about
the protection of each target by assigning a local budget to every target,
considering two local protector selections. We also implement scalable
implementations and experiments to demonstrate the effectiveness and efficiency
of the proposed algorithms.
