Project:	Efficient Algorithms for Bipartite Graph Alignment
Disciplines:	Electrical Engineering, Computer Science, ACM
Mentor:	Daniel Cullina, Assistant Professor, (EAS), cullina@psu.edu, Phone: 773915-3639
Mentor URL:	https://sites.psu.edu/cullina  (opens in new window)
Background:	NOTE: This project is being offered by a Caltech alum and is open only to Caltech students. The project will be conducted at Penn State University in State College, Pennsylvania. One way to attack anonymized user data is to exploit statistical correlations between the anonymous data and other available data to uncover true user identities. Bipartite graph alignment problems appear in deanonymization scenarios where both the users and the objects have been anonymized. From an algorithmic point of view, they interpolate between the computationally easy problem of database alignment and the hard problem of general graph alignment.
Description:	The student will explore algorithms for bipartite graph alignment, implement them, and test them on both synthetic and natural data. This will help us understand the boundary between computationally easy and hard regimes for this problem. The student will start by comparing the performance of various methods and then will begin developing more sophisticated algorithms that combine these basic ideas. Depending on the student's background, there is an opportunity to work on the mathematical analysis of the accuracy of the algorithms on random data.
Student Requirements:	Proficiency in probability, linear algebra, and algorithms (CS38)
Programs:	This AO can be done under the following programs:   Program    Available To        SURF    Caltech students only  Click on a program name for program info and application requirements.