DIMACS
DIMACS REU 2018

General Information

me
Student: Daniel Nakhimovich
Office: 450
School: The Cooper Union
E-mail: dnahimov@gmail.com
Project: k-component Decomposition of Fixed Points of Degree Peeling

Project Description

How can we leverage human intuition for analyzing a lot of data? The solution is a visualization system that doesn't overload the user with too much information at a time by grouping the data into managable yet meaningful chunks. The approach that I am working to extend starts by taking data and grouping it into sets. These sets are then transformed into region graphs. The region graphs are then decopmosed into fixed points of degree peeling using an iterative edge core decomposition. However, this decomposition still produced rather large layers of graphs that need to be decomposed to be useful for human analysis. That is where k-connected component decomposition comes in. Currently, algorithms exist for decomposing a graph into 1,2 and 3 connected components. The goal with this project is to leverage the properties of fixed points of degree peeling in order to decompose them into arbitrary k-connected components.

Weekly Log

Week 1:
First, I familiarlized myself with the current version of the visualization program the team is working on called peel explorer as well as the iterative edge core decomposition that it performs. Then I spent time researching k-connectivity of graphs and what work has already been done in that area. This research helped me formalize the notion of a k-connected component decomposition. After formalizing that goal, my mentor and I met a few times to discuss different lines of explorartion towards finding an algorithm to perform k-connected component decomposition. My main focus of the week has been to explore the following process: apply breath first search in parallel on two vertices that are the maximally distant in the graph and then find the graph that is induced by overlapping layers of the BFS, then expand that graph by adding back vertices of layers further out and see how various properties of the graph change. Also, while researching other papers on the topic of k-connectivity I found one that proposes and algorithm for k-edge-connected component decomposition. Although this algorithm forms a partition of vertices as opposed to a partition of edges (which is what I'm interested in) I am still keeping it in the back of my mind hoping to find some useful connection or approach from that paper to my specific goal.
Week 2:
After some exploration of the parallel BFS search I think I found a basis for an algorithm and can start experimenting with larger graphs. In order to do this I'm borrowing some of the code from peel explorer and using the python graph-tool library for visualization. Using those tools I developed a small terminal style application to let me generate random graphs or load actual graphs and perform the peel decomposition followed by my experimental decomposition. Using this tool I can more quickly explore the atomic components that come from my decomposition. Next I will be working on adding more graph statistics to track over the execution of my decomposition.
Week 3:
In addition to the pseudo decomposition, I implemented another algorithm that expands subgraphs starting from the middle of the parallel BFS search going outwards to track how its properties change. Thus I finally had to add the ability to track some useful statistics of graphs for both algorithms. The tracked statistics so far are: whether or not the graph is a fixed point, the graphs peel value, the graphs diameter, and the degrees of vertices along the diameter. So far no patterns have stuck out to me with those statistisc but visually I have noticed a rather obvious difference between how random data tends to look and how structured data tends to look when represent through my pseudo decomposition.
Week 4:
Finally finished reading the paper and slides about persistant homology. Although, a lot of the riggor is beyond me I have an intuitive notion of how it works and will continue to think about how I can approuch my task with that tool. Additionally, I've started exploring other metrics of distance to see if they can help cluster k-connected components in a more obvious way. So far I implemented the calculation of resistance distance, treating each edge as a 1 ohm resistor and performing modified nodal analysis with one vertex set to 1V and another set to 0V. Since I already implemented the mna code, I decided to also try just ranking vertices by voltage by picking one vertex on the diameter to be 1V and another to be 0V and letting the resistance of the edges between determine the rest.
Week 5:
I haven't picked up on any useful connection between k-connected components and the resistance distance between vertices so I decided to consider flow again. I read a paper that used a transformation on a graph to make an auxilary graph and then performed the classic Ford-Fulkerson algorithm on the auxilary graph. The resulting minimum edge cut on the auxilary graph corresponds to a minimum vertex cut on the original graph. I implemented this minimum vertex cut algorithm to use in my pseudo decomposition to see how it compares to my previous method of finding a minimum vertex cut.
Week 6:
This week I've been using the decompositions I implemented to look at the atomic components and find characteristics of these atomic components with resepect to the fixed-points of degree peeling they come from. Additionally, the final presentations took place this week so I prepared a slide deck explaining the decompositions I've made as well as how they relate to the overall peel system. I also made a more convenient visualization of my decomposition so I could demo it during the presentation.
Week 7:
I have continued to look at relationships between the size of a graph, the peel value, the diameter, and the k-connectivity. Although I found some general tendencies I found counter examples to disprove any tight bounds I thought I had found. I have also made an interesting observation about how the macro-structure imposed by k-connectivity is limited in complexity by the peel value of the fixed point. On a different note, I also revamped the visualization tool for a better demo in order to show off my decomposition on protein structre data to the providers of that data source.
Week 8:
Since its the last week I took a pause with exploring new directions and just consolidated my thouhts thus far. Also, finally took the time to properly analyze the complexity of the algorithms I implemented. Most of this week was spent writing the final report and makeing sure to cite the relavent papers and software libraries that I read/used.

Presentations and Media

Additional Information