Random-based Algorithm

RGO (Random Graph Obfuscation) Algorithm

RGO is an random-based algorithm. It uses different concepts in order to select edges to be deleted or created on the anonymous network.

Related work was presented in:

  • Casas-Roma, J., Herrera-joancomartí, J., and Torra, V. (2013). Analyzing the Impact of Edge Modifications on Networks. In The 10th International Conference on Modeling Decisions for Artificial Intelligence (pp. 296-307). Barcelona: Springer-Verlag. doi:10.1007/978-3-642-41550-0_26
  • J. Casas-Roma (2014). Privacy-Preserving on Graphs using Randomization and Edge-Relevance. In V. Torra, Y. Narukawa and Y. Endo, editors, Proceedings of the 11th International Conference on Modeling Decisions for Articial Intelligence, volume 8825 of Lecture Notes in Articial Intelligence, pp. 204-216. Berlin, Heidelberg, 2014. Springer Berlin Heidelberg. doi:10.1007/978-3-319-12054-6_18

Abstract: The problem of anonymization on graphs and the utility of the released data are considered in this paper. Although there are some anonymization methods for graphs, most of them cannot be applied on medium or large graphs due to their complexity. Nevertheless, random-based methods are able to work with medium or large graphs while fulfilling the desired privacy level. In this paper, we devise a simple and efficient algorithm for randomization on graphs. Our algorithm considers the edge’s relevance, preserving the most important edges of the graph, in order to improve the data utility and reduce the information loss on anonymous graph. We apply our algorithm to different 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.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s