DIMACS
DIMACS REU 2012

General Information

me
Student: Marco A. Perez
Office: CoRE 450
School: University of California, Los Angeles
E-mail(s):

mperez@dimacs.rutgers.edu
perezmarco@g.ucla.edu
Project: Differential Graph Privacy

Project Description

The notion of differential privacy has become a popular standard for database privacy. Differential privacy tries to formalize the idea that privacy is preserved if the risk of inferring anything sensitive about an individual does not change significantly if he/she participates in a statistical database.

In this project I will examine the possibility of generating synthetic graphs "similar" to an original graph that satisfies this definition of privacy, to enable sharing of potentially sensitive graphs for analysis and research. I will work on examining private estimation of various parameters of several Stochastic graph models (such as, the Kronecker Graph model and the Exponential Random Graph Model), and compare the experimental performance of synthetic graphs across models. A related aim is to study analytically and/or experimentally the growth of a quantity called the "smooth sensitivity" of some graph statistics like the number of triangles in a graph.


Weekly Log

Week 1:
The first week I attended orientation and met my mentors. We discussed the possibilities in terms of projects and I chose Differential Graph Privacy. I met with both my mentors twice this week and I was assigned two introductory readings to get acquainted with the definitions. I also presented my topic and the focus of my research to the group.
Week 2:
This week I met with Dr. Abello to discuss the possibility of taking another route in terms of my research. The other student and I had a group discussion where we talked about our projects and progress. I was assigned differential privacy excercises to reinforce what I have been reading. And Finally, I downloaded, and started to get acquainted with MATLAB.
Week 3:
I was assigned a reading by one of my mentors, I downloaded Octave, a free alternative to MATLAB, and also met with Darakhshan. I also had to implement the definition of Differential Privacy to the Mean (using a list of values) and the number of edges (using an adjacency matrix).
Week 4:
This week I met with Darakhshan to discuss whether I should work on the original idea or shift focus and implement the idea of Dr. Abello. I was given feedback and made the necessary corrections to my MATLAB program.
Week 5:
I went over one of the previous papers to read about smooth sensitivity and its implementation. I met with Dr. Abello and Darakhshan to discuss my progress. I was also given a reading on Kronecker graphs.
Week 6:
I worked with a smooth sensitivity proof on the number of triangles in a graph presented in one of the papers and implemented it on MATLAB. I also attended a Graduate School Panel.
Week 7:
I worked on my presentation and the direction I would take after the program ended. I presented on Friday in front of the group and I started to read on Random Kronecker Graphs.
Week 8:
On the last week I finished the documentation for my project and began to work on my final report. I met with one of my mentors to discuss research possibilities other than the main project I was assigned.

Presentations


Additional Information