UMGA Algorithm

UMGA (Univariant Micro-aggregation for Graph Anonymization) Algorithm

UMGA is an algorithm for k-degree anonymization on large networks. It uses the concept of univariant micro-aggregation to anonymize the degree sequence of the network. Then, it applies edge swap to modify graph structure in order to implement to the anonymized k-degree sequence.

It was presented in:

  • Casas-Roma, J., Herrera-Joancomartí, J., and Torra, V. (2013). An Algorithm For k-Degree Anonymity On Large Networks. In The 2013 IEEE/ACM International Conference on Advances on Social Networks Analysis and Mining (pp. 671-675). Niagara Falls, doi:10.1145/2492517.2492643
  • J. Casas-Roma, J. Herrera-joancomartí and V. Torra. (2016). k-Degree Anonymity And Edge Selection: Improving Data Utility In Large Networks. Knowledge and Information Systems (KAIS), Vol. 50(2), pp. 447-474. doi:10.1007/s10115-016-0947-7

Abstract: In this paper, we consider the problem of anonymization on large networks. There are some anonymization methods for networks, but most of them can not be applied on large networks because of their complexity. We present an algorithm for k-degree anonymity on large networks. Given a network G, we construct a k-degree anonymous network, G*, by the minimum number of edge modifications. We devise a simple and efficient algorithm for solving this problem on large networks. Our algorithm uses univariate micro-aggregation to anonymize the degree sequence, and then it modifies the graph structure to meet the k-degree anonymous sequence. We apply our algorithm to a different large real datasets and demonstrate their efficiency and practical utility.

The code (implemented in Java) can be downloaded:

For any trouble or comment, please feel free to contact me.

4 Responses to UMGA Algorithm

  1. hossein says:

    Repository jcasasr/umga-java not found ERROR in download.please fix it

  2. Ola says:

    Can you please specify where the SimpleIntGraph class is found, in which file. Thank you

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s