Analysis and Visualization of Complex Graphs

Sponsor: 
NSF
Sponsor Group: 
IIS

This project focused on methods for manipulating large social networks to better reveal organization and other information. Social networks pose a special challenge to computational methods because of their variance in node degree, with many low degree nodes and few high degree nodes. Our analyses were based on betweenness centrality (BC), which measures how many shortest paths between pairs of nodes pass through each node or edge.

We showed that removing edges in order of decreasing BC simplifies a social network into its major communication backbone and improves the layout of the full network. We showed that removing edges in order of increasing BC reveals a community hierarchy that we can present in a better balanced radial layout. We also showed how to leverage GPU processing for better layout and improved BC computation, the latter using a new edge-parallel approach that improves throughput by avoiding the memory contention caused by node-parallel approaches. In addition to papers, the project generated code samples as well as a facebook app for visualizing friend networks.

The proposal supported the research of three graduate students, including Yuntao Jia (now at facebook), Apeksha Godiyal (now at Microsoft Visio) and Jared Hoberock (now at Nvidia Research).

Duration: 
Sep. 2006 - Aug. 2009
Status: 
Completed
Publications: 
(Proc. Infovis) IEEE Transactions on Visualization and Computer Graphics 14(6), Nov. 2008, pp. 1285-1292

Proc. Graph Drawing 2008, Lecture Notes in Computer Science, Springer, 2009, pp. 90-101


Theme by Danetsoft and Danang Probo Sayekti inspired by Maksimer