||University of Central Florida
||michaelp (at) reu.dimacs.rutgers.edu
||Using Clustering Relation to Influence Graph Layout
Given an abstract graph of vertices and edges, how should it be drawing nicely on a piece of paper? There are many algorithms to layout a graph aesthetically. Often, a good drawing conveys clustering relationship between items. And there are reasons to believe that graph layout is a process of graph clustering. However, in practice, it is often the case that even in a good layout, vertices in the same cluster may not be contiguous in space. For example, "countries" in the MusicMap are often fragmented. This could be a reflection of the fact that some vertices may probabilistically belong to multiple clusters. E.g., a music group may be a hybrid of two genres, thus defies hard classification. But for practical visualization, could we use the clustering to influence the layout, devise an algorithm to "pull" the outliers into the main areas, thus making the "countries" contiguous?
- Week 1:
- Currently reviewing papers and working on my force directed graph drawing algorithm.
- Week 2:
- I finished and tested my force directed graph drawing algorithm on smaller graphs. I am now looking
into drawing some of the graphs from the University of Florida Sparse Matrix Collection. After that I will
be working on the LinLog Energy Model. I also had my first weekly meeting with the group going to Prague.
We were given DIMACS/DIMATIA bridge session problems to solve consisting of Graph Theory, Combinatorics, and
Discrete Math problems.
- Week 3:
- On Monday we toured IBM and had several interesting speakers. The talk I found most interesting was by
Dr. Lior Horesh who explained some of the more interesting problems in his research. In regards to my work
this week I managed to draw some of the graphs from the University of Florida Sparse Matrix Collection.
I am also at the point where I am finishing up my LinLog layout to better identify clusters. Next week I
plan on having graphviz setup and looking into the gmap algorithm, where I will begin to fix the problem
of fragmentation in graph layout.
- Week 4:
- On Thursday we had a fun talk on random walks by Dr. Swastik Kopparty. He cited two interesting examples
verifying connectivity in a graph using log n space and googles page rank algorithm. He also talked about concepts
such as the number of times you reach the origin in differnent dimensions. In regards to my research this week I
setup graphviz and wrote some parsers for the input/output file formats. More importantly I was able to have a
nice vizualization of my force directed graph while also coloring the particular clusters of the nodes. I feel
I am almost there I just have to implement the algorithm my advisor and I have discussed to deal with fragmentation.
On another note some of the fellow researchers have found the game WikiWars to be entertaining. In response I have
attempted to create my own program for this task. Currently the transition between the links are random so it can find
popular topics like Florida in ~15 seconds, but it takes longer on more obscure topics. I plan to create some database
of popular hubs/topics and relationships so as to find an intelligent way to probabilisticly transition between links soon!
- Week 5:
- My research is going well. I have completed our initial idea to deal with fragmentation, and produced
good resulsts. I am in the process of organizing my material and recording visualizations of the algorithm using different
methods/parameters. My advisor and I have begun discussing more sophisticated approaches using triangulation and voronoi diagrams. Another item I am looking into is how to relate the distance of the node from the center of the cluster so as to apply a more accurate/proportional attractive force to that particular node.
- Week 6:
- I am begining to compile my material and prepare for the final presentation. Currently I have three methods to deal with
fragmentation, the third being a hybrid of the first two. I have found the results to be more compeling when outputed through
my GUI rather than gvmap, but I have included both. In addition I have found my second method to work well with streaming graphs.
I am also currently in the processes of testing on multiple datasets, and creating different fitness functions or ways
to quantify the "goodness" of my solution.
- Week 7:
- I completed and gave my final presentation. I also finished my final report where I detailed my summer research. I came up
with a few ideas to quantify the "goodness" of my graph visualizations. I also had an idea for future research where I would ask
users to rank visualizations and then I would simply "learn" the features that make a graph visualization good, then utilize that
knowledge on other graph drawings.
- Week 8:
- I am off to prague where I will participate in DIMATIA workshops and the 18th Midsummer Combinatorial Workshop at Charles University.