Drew Harry's Portfolio

k-Clique Reduction

Duration

3 Weeks

Semester

Fall 2004

Team

Dan Lindquist

Course

Discrete Math

Instructor

Prof. Sarah Adams

As graphs are generated with greater numbers of vertices and edges, it becomes increasingly important to develop effective ways to visualize them. Current methods can automatically layout reasonably complex graphs, but graphs with small world properties and high edge densities are still extremely challenging.

This paper proposes two approaches to creating graph abstractions; graphs which exhibit the same topological features and express the details of the original graph in an effective visual way. We call the first method k-Clique Minimization. In this method, we use a graph heuristic to quickly find completely connected subgraphs. Each of these subgraphs is replaced in the abstracted graph with a single node, whose size is related to the size of the complete subgraph that has been replaced. To further simplify the graph, we "erode" once, removing pendant vertices, and showing them graphically as a dark halo around remaining vertices.

Our second method, Centrality Erosion, is an iterative process in which nodes with a centrality of zero are removed from the graph, until the remaining nodes all have a centrality value of greater than zero. Nodes are colored and sized based on how many erosion cycles they sustained before being removed.

Final Report

Final report for the project, including graphical examples and psuedo-code for implementing our algorithms. (PDF, 2.7 MB)

Final Presentation

The final presentation for this project. (PPT, 1.8 MB)

Resumé

social software

Traces: Location Based Services
Sharing Music Presence

visualization

TreeFlow
k-Clique Reduction

anthropology

World of Warcraft Ethnography
Go Community Ethnography
Community and Carpe-diem

design

Mailing List Design
Bike Messenger Design