Solution:

The example in the Figure illustrates how neighborhood attacks can take place. Let us consider the graphical representation (see Figure a) of the social network in which a group of persons is connected to each other through the relation of friendship. An edge connecting two nodes represents that they are friends.

In Figure, if an attacker has knowledge about the 1-neighborhood of “Fred”, the node “Fred” can be easily identified from the basic anonymized graph of Figure, as no other node has similar 1-neighborhoods to that of “Fred.” Thus, the privacy of the social network is leaked.

Once this node is identified, other private information such as connectedness, relative position, and relation with other nodes (identified in the same way) is exposed. This necessitates further anonymization processes so that the knowledge about 1-neighborhood cannot be used to identify a node uniquely.

In Figure a, if an edge is added between “Luna” and “Bill,” the 1-neighborhood of “Fred” and “Lily” is similar as shown in Figure b and c and it is not possible to identify ‘Fred’ with a confidence greater than ½ (see Figure a).

If the match is not found, the cost factor is used to decide the pair of vertices to be considered. Their algorithm adheres to the k-anonymity security model.

More importantly, the time complexities of their anonymized algorithms are comparatively less.