On the k-Anonymization of Time-varying and Multi-layer Social Graphs

Part of book or chapter of book, Preprint English OPEN
Rossi, Luca ; Musolesi, Mirco ; Torsello, Andrea (2015)
  • Subject: Computer Science - Social and Information Networks | Computer Science - Cryptography and Security
    arxiv: Computer Science::Cryptography and Security

The popularity of online social media platforms provides an unprecedented opportunity to study real-world complex networks of interactions. However, releasing this data to researchers and the public comes at the cost of potentially exposing private and sensitive user information. It has been shown that a naive anonymization of a network by removing the identity of the nodes is not sufficient to preserve users’ privacy. In order to deal with malicious attacks, k -anonymity solutions have been proposed to partially obfuscate topological information that can be used to infer nodes’ identity. In this paper, we study the problem of ensuring k anonymity in time-varying graphs, i.e., graphs with a structure that changes over time, and multi-layer graphs, i.e., graphs with multiple types of links. More specifically, we examine the case in which the attacker has access to the degree of the nodes. The goal is to generate a new graph where, given the degree of a node in each (temporal) layer of the graph, such a node remains indistinguishable from other k-1 nodes in the graph. In order to achieve this, we find the optimal partitioning of the graph nodes such that the cost of anonymizing the degree information within each group is minimum. We show that this reduces to a special case of a Generalized Assignment Problem, and we propose a simple yet effective algorithm to solve it. Finally, we introduce an iterated linear programming approach to enforce the realizability of the anonymized degree sequences. The efficacy of the method is assessed through an extensive set of experiments on synthetic and real-world graphs.
  • References (39)
    39 references, page 1 of 4

    Andersen, R.; Borgs, C.; Chayes, J.; Feige, U.; Flaxman, A.; Kalai, A.; Mirrokni, V.; and Tennenholtz, M. 2008. Trust-based recommendation systems: an axiomatic approach. In Proceedings of WWW'08, 199-208. ACM.

    Backstrom, L.; Dwork, C.; and Kleinberg, J. 2007. Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography. In Proceedings of WWW'07, 181-190.

    2009. Class-based graph anonymization for social network data.

    Proceedings of the VLDB Endowment 2(1):766-777.

    2010. Prediction promotes privacy in dynamic social networks. In Proceedings of WOSN'10. USENIX Association.

    Bunke, H. 1997. On a relation between graph edit distance and maximum common subgraph. Pattern Recognition Letters 18(8):689-694.

    Casas-Roma, J.; Herrera-Joancomart´ı, J.; and Torra, V. 2013. An algorithm for k-degree anonymity on large networks. In Proceedings of ASONAM'13, 671-675. ACM.

    Cheng, J.; Fu, A. W.-c.; and Liu, J. 2010. K-isomorphism: privacy preserving network publication against structural attacks. In Proceedings of SIGMOD'10, 459-470. ACM.

    Chester, S.; Gaertner, J.; Stege, U.; and Venkatesh, S. 2012.

    Anonymizing subsets of social networks with degree constrained subgraphs. In Proceedings of ASONAM'12, 418-422. IEEE Computer Society.

  • Metrics
    No metrics available
Share - Bookmark