Non-linear zooming and Clique highlighting in Network Visualization
Team: Chaman, Nakho, Jeeyoung
Overview
Our group project aims to build an improved network diagram visualization which includes new effective measures for removing data cluttering and highlighting complete subgraphs(“cliques”). Discussing the many challenges in network graphs, we decided that the most basic and concrete problem to improve on will be how to make pattern finding in large datasets easier. Also, we wanted to handle the issue of cliques, which has been widely regarded to provide qualitatively distinct communication patterns.
To remove data cluttering we will explore the possibilities of non-linear zooming, while for visualization of cliques we will focus on how to assign effective visual cues to the subgraphs to make them stand out in the large network graph.
We will be using two distinct network data, one from the social science domain and the other from natural sciences. The first dataset is the coeditor network of the Wikipedia. Wikipedia is an popular open Internet-based collaborative platform to compile all fields of knowledge in a encylopedia format, currently hoding more than 3 million articles. Anyone can write and anyone can edit what anybody else has written. By examining on a large scale which two or more users have written and edited a common article together, we can see how specific knowledge production networks emerge in an open structure.
The second dataset is the protein interaction network of yeasts. Protein-protein interaction reveals functional control of target proteins as well as molecular complexes. This protein-protein interaction data can be in the form of binary interaction or group of interaction. Also, those data can be from several different experiment methods. First, we visualize those interaction information from several methodologies in an efficient way. We cliques overlapping links to have high-confidence interactions. Second, we visually integrate protein-protein interaction with known pathway or genetic interaction. Then, we can investigate the relationship between protein-protein interaction, pathway, and genetic interaction.
Our team is composed of members of different academic backgrounds, which will provide a significant merit if the subtasks are properly allocated. Chaman will be focusing on algorithm implementation, Nakho will provide the Wikipedia data and work on design aspects, and Jeeyoung will provide the protein data and process the raw material into network data. Other subtasks including the literature review will be done collaboratively.
Project schedule(tentative)
Week 1 (~Apr/16) : Planning and compiling the initial literature
Week 2 (~Apr/23) : Literature review, preprocessing of data, analyzing algorithms of existing software (e.g. H3viewer, HypViewer, LGL code), Progress report #1
Week 3 (~Apr/30): initial implementation of improved visualization tools, Progress report #2
Week 4 (~May/6 11am): finalizing tools, presentation, final report
Literature to review (tentative)
– Frishman, Y. & Tal, A. Online Dynamic Graph Drawing IEEE Transactions on Visualization and Computer Graphics, 2008, 14, 727-740
– Frishman’s thesis
– Frishman, Y. & Tal, A. Multi-Level Graph Layout on the GPU IEEE Transactions on Visualization and Computer Graphics, 2007, 13, 1310-1319
– Frishman, Y. & Tal, A. Dynamic Drawing of Clustered Graphs Proc. IEEE Symposium on Information Visualization INFOVIS 2004, 2004, 191-198
– deMoll, S. B. & McFarland, D. A. The Art and Science of Dynamic Network Visualization Journal of Social Structure, 2006, 7
– C. Collberg, S. Kobourov, J. Nagra, J. Pitts, and K.Wampler. A system for graph-based visualization
of the evolution of software. In SoftVis ’03: Proceedings of the 2003 ACM symposium on Software
visualization, pages 77–ff, 2003.
– M. Freire and P. Rodriguez. Preserving the mental map in interactive graph interfaces. In AVI ’06:
Proceedings of the working conference on Advanced visual interfaces, pages 270–273, New York,
NY, USA, 2006. ACM.
– Michael Kaufmann & Dorothea Wagner. Graph Drawing: Methods and Models. 2005. (selected chapters)
– http://www.leader-values.com/Content/detail.asp?ContentDetailID=975 social groups visualization which focuses entirely on design techniques
– http://www.ibluemojo.com/school/clique_algorithm.html algorithms to calculate cliques efficiently
– http://portal.acm.org/citation.cfm?id=860151 algorithms to calculate cliques efficiently
– http://www.cytoscape.org/ Visualization tool used in biological data
– “A survey of visualization tools for biological network analysis” by Pavlopoulos et al. (2008)
– “Visualization of omics data for systems biology” by Gehlenborg et al. (2010)