I study two privacy-preserving social network graphs to dis- close the types of relationships of connecting edges and provide flexible multigrained access control. To create such graphs, my schemes employ the concept of secretaries and types of relationships. It is significantly more efficient than those that using expensive cryptographic primitives. I also show how these schemes can be used for multigrained access control with various options. In addition, I describe how much these schemes are resilient to infer the types of connecting edges.
Zheleva and Getoor @cite_1 addressed the problem of preserving privacy of sensitive relationship in a social network. The authors introduced five different edge anonymization algorithms by adopting different removing edges or clustering edges between nodes under the very specific assumptions.
@cite_1
1544573083
In this paper, we focus on the problem of preserving the privacy of sensitive relationships in graph data. We refer to the problem of inferring sensitive relationships from anonymized graph data as link reidentification. We propose five different privacy preservation strategies, which vary in terms of the amount of data removed (and hence their utility) and the amount of privacy preserved. We assume the adversary has an accurate predictive model for links, and we show experimentally the success of different link re-identification strategies under varying structural characteristics of the data.