DIMACS
DIMACS REU 2012

General Information

026
Student: Alassane NGaide
Office: CoRE 434
School: New York City College Of Technology
E-mail: ngaide_alassane@yahoo.com
Project: Cluster Analysis & it Apllications to Biodiversity

Project Description

Given the competition graph G= (V, E) based on the Hudson River data sets with the node set (species) V, edge set E, and the weight matrix W (Wij = number of shared preys between ith and jth predators), we want to see if it is possible to partition the competition graph G into two sub graphs GA and GB using the combination of Fiedler order and linkage-based refinements to minimize cut (A, B) while maximizing W(A) and W(B) at the same time.


Weekly Log

Week 1: (6/4/2012)
I arrive at DIMACS on Sunday June 3th, around 2 pm, received my Nichols apartment keys from graduates coordinators Kellen and Yusra. Introduce myself to roommates and fellow researchers. Monday morning, first official day at DIMACS, I met my mentors and got introduce to my summer research. They provided me some reading materials so I can get familiarize with the project. The rest of the week I worked on my introductory project presentation scheduled for June 8.
Week 2: (6/11/2012)
This week we met for the second time our mentor Dr. Ghosh-Dastidar who provide us with more reading materials about Graph theory, clustering and introduction to Laplacian and normalize Laplacian matrix. We discuss about the approach we will use for this project. We wrote a report on an assignment she gave us during our meeting.
Week 3: (6/18/2012)
Dr. Ghosh-Dastidar, Frederic and I worked on the math behind the min-max cut function. We got a better understanding of the use of Mcut in the work we are trying to achieve during this summer.
We worked on actual data from the Hudson River 55 species. We analyzed the competition graph between predators sharing common preys and tried to make sense out of the matrix developed from the graph by a previous study. We found some unconformities between digraph of the food web and matrix associated. We decided to develop our own matrix in the coming days.
Week 4: (6/25/2012)
This week my partner and I developed some proofs related to Mcut function (Objective Function), we got much more familiarize with the Fiedler linear Search Oder and the Linkage based refinements two key approaches that will be used to partition the competition graph. We finally corrected the matrix associated with the Hudson River food web and now are ready for the next step. On Friday (June, 29th) we met our mentor, discussed, about the project and were we heading, handed in our weekly report and got a specific assignment for the fallowing week.
Week 5: (7/2/2012)
This week we had a major setback to prove that minimizing the Cut(A,B), is equivalent to solving the Eigen-System. Our mentor provided some new material regarding this issue and by Tuesday July 10th we finally found a proof. We also learn the advantage of linkage –based refinements method compare to Fiedler order, and why combining the two methods will improve the quality of the cut.
Week 6: (7/9/2012)
This week we familiarized with math lab, explored some algorithm that we will be using for the project. We met twice our mentor Dr. Ghosh who provided more reading material to clarify certain aspect that we need help with. On Wednesday July 11th, we started a draft of the second presentation.
Week 7: (7/16/2012)
We spent most of this week analyzing our results and also getting prepared for the final presentation which is due July 19th.
Week 8: (7/23/2012)
This was the last week of the DIMACS REU research summer program, we spent this week mostly going over the results we produced and collecting all information for the final report. By the end of the week we finished writing the report which we submitted on Friday July 27th

Presentations


Additional Information