k-anonymity over social networks has been defined. Basically, we can view a social network (like FaceBook, Google Circles, etc.) as a graph. The nodes constitute people. The links between nodes constitute friend relationships. In general, it is not sufficient simply to remove node identifiers. Therefore the structure of the graph itself is anonymized. The notion of k-anonymity here is to change the graph by adding links so that at least k of the nodes looks exactly similar to each other (at the 1-neighbor level). This question has two parts:

Is personalized k-anonymity (i.e., if each person sets a different level of k) meaningful in this context?

What would differential privacy mean in this context? I.e., can you specify how differential privacy would be applied (i.e., what would be the input, output, whose privacy is being protected)?

Suppose, given the entire social network graph, I decided to answer the following set of questions: for every pair of people A and B in the social network, we ask are A and B connected through at most 6 friends. I decided to give this answer in a differentially private sense. Will this then preserve my privacy?