Privacy in opportunistic network contact graphs

Opportunistic networks are formed by people carrying mobile devices with wireless capabilities. When in mutual transmission range, the nodes of such networks use device-to-device communication to automatically exchange data, without requiring fixed infrastructure. To solve challenging opportunistic networking problems like routing, nodes exchange information about whom they have met in the past and form a contact graph, which encodes the social structure of past meetings. This contact graph is then used to assign a utility to each node (e.g., based on their centrality), thereby defining a ranking of the nodes´ values for carrying a message. However, while being a useful tool, the contact graph represents a privacy risk to the users, as it allows an attacker to learn about social links. In this paper, we investigate the trade-off of privacy and utility in the contact graph. By transforming the graph through adding and removing edges, we are able to control the amount of link privacy. The evaluation of a greedy approach shows that it maintains the node ranking very well, even if many links are changed.