Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Rossi, Luca; Musolesi, Mirco; Torsello, Andrea (2015)
Languages: English
Types: Part of book or chapter of book
Subjects: Computer Science - Social and Information Networks, Computer Science - Cryptography and Security

Classified by OpenAIRE into

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.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • 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.
    • Clauset, A., and Eagle, N. 2007. Persistence and periodicity in a dynamic proximity network. In Proceedings of DIMACS Workshop on Computational Methods for Dynamic Interaction Networks.
    • Erdo˝s, P. L.; Miklo´s, I.; and Toroczkai, Z. 2010. A Simple HavelHakimi Type Algorithm to Realize Graphical Degree Sequences of Directed Graphs. Electronic Journal of Combinatorics 17(1):R66.
    • Erdo˝s, P. 1960. Graphs with prescribed degrees of vertices (hungarian). Mat. Lapok 11:264-274.
    • Fung, B.; Wang, K.; Chen, R.; and Yu, P. S. 2010. Privacypreserving data publishing: A survey of recent developments. ACM Computing Surveys 42(4):14.
    • Hamada, K.; Iwama, K.; and Miyazaki, S. 2011. The hospitals/residents problem with quota lower bounds. In Proceedings of Algorithms-ESA'11. Springer. 180-191.
    • Hartung, S.; Hoffmann, C.; and Nichterlein, A. 2014. Improved upper and lower bound heuristics for degree anonymization in social networks. arXiv preprint arXiv:1402.6239.
    • Hay, M.; Miklau, G.; Jensen, D.; Weis, P.; and Srivastava, S. 2007.
    • Anonymizing social networks. Computer Science Department Faculty Publication Series 180.
    • Hay, M.; Miklau, G.; Jensen, D.; Towsley, D.; and Weis, P. 2008.
    • Resisting structural re-identification in anonymized social networks. Proceedings of the VLDB Endowment 1(1):102-114.
    • Holme, P., and Sarama¨ki, J. 2012. Temporal networks. Physics Reports 519(3):97-125.
    • Hristova, D.; Musolesi, M.; and Mascolo, C. 2014. Keep Your Friends Close and Your Facebook Friends Closer: A Multiplex Network Approach to the Analysis of Offline and Online Social Ties.
    • In Proceedings of ICWSM'14.
    • Jain, A. K., and Dubes, R. C. 1988. Algorithms for clustering data.
    • Krumke, S. O., and Thielen, C. 2013. The generalized assignment problem with minimum quantities. European Journal of Operational Research 228(1):46-55.
    • Kwak, H.; Lee, C.; Park, H.; and Moon, S. 2010. What is twitter, a social network or a news media? In Proceedings of WWW'10, 591-600. ACM.
    • Liu, K., and Terzi, E. 2008. Towards identity anonymization on graphs. In Proceedings of SIGMOD'08, 93-106. ACM.
    • Lu, X.; Song, Y.; and Bressan, S. 2012. Fast identity anonymization on graphs. In Database and Expert Systems Applications, 281-295.
    • 2012. Sensing the “health state” of a community. IEEE Pervasive Computing 11(4):36-45.
    • Medforth, N., and Wang, K. 2011. Privacy risk in graph stream publishing for social network data. In Proceedings of ICDM'11, 437-446. IEEE.
    • Meyerson, A., and Williams, R. 2004. On the complexity of optimal k-anonymity. In Proceedings of PODS'04, 223-228. ACM.
    • Mislove, A.; Marcon, M.; Gummadi, K. P.; Druschel, P.; and Bhattacharjee, B. 2007. Measurement and analysis of online social networks. In Proceedings of IMC'07, 29-42. ACM.
    • Mucha, P. J.; Richardson, T.; Macon, K.; Porter, M. A.; and Onnela, J.-P. 2010. Community structure in time-dependent, multiscale, and multiplex networks. Science 328(5980):876-878.
    • Opsahl, T., and Panzarasa, P. 2009. Clustering in weighted networks. Social Networks 31(2):155-163.
    • Page, L.; Brin, S.; Motwani, R.; and Winograd, T. 1999. The pagerank citation ranking: Bringing order to the web. Technical Report 1999-66, Stanford InfoLab.
    • Shetty, J., and Adibi, J. 2005. Discovering Important Nodes through Graph Entropy: The Case of Enron Email Database. In Proceedings of LinkKDD'05, 74-81. ACM.
    • Zhou, B., and Pei, J. 2008. Preserving privacy in social networks against neighborhood attacks. In Proceedings of ICDE'08, 506- 515. IEEE.
    • Zhou, B., and Pei, J. 2011. The k-anonymity and l-diversity approaches for privacy preservation in social networks against neighborhood attacks. Knowledge and Information Systems 28(1):47- 77.
    • Zou, L.; Chen, L.; and O¨ zsu, M. T. 2009. K-automorphism: A general framework for privacy preserving network publication. Proceedings of the VLDB Endowment 2(1):946-957.
  • No related research data.
  • No similar publications.

Share - Bookmark

Funded by projects


Related to

  • fet-fp7FET Proactive: Dynamics of Multi-Level Complex Systems (DyM-CS)
  • fet-fp7FET Proactive: multi-LAyer SpAtiotemporal Generalized NEtworks

Cite this article