A visual-analytic toolkit for dynamic interaction graphs

ABSTRACT

In this article we describe a visual-analytic tool for the interrogation of evolving interaction network data such as those found in social, bibliometric, WWW and biological applications. The tool we have developed incorporates common visualization paradigms such as zooming, coarsening and filtering while naturally integrating information extracted by a previously described event-driven framework for characterizing the evolution of such networks. The visual front-end provides features that are specifically useful in the analysis of interaction networks, capturing the dynamic nature of both individual entities as well as interactions among them. The tool provides the user with the option of selecting multiple views, designed to capture different aspects of the evolving graph from the perspective of a node, a community or a subset of nodes of interest. Standard visual templates and cues are used to highlight critical changes that have occurred during the evolution of the network. A key challenge we address in this work is that of scalability - handling large graphs both in terms of the efficiency of the back-end, and in terms of the efficiency of the visual layout and rendering. Two case studies based on bibliometric and Wikipedia data are presented to demonstrate the utility of the toolkit for visual knowledge discovery.

REFERENCES

• 1: James Abello , Frank van Ham , Neeraj Krishnan, ASK-GraphView: A Large Scale Graph Visualization System, IEEE Transactions on Visualization and Computer Graphics, v.12 n.5, p.669-676, September 2006 [doi>10.1109/TVCG.2006.120]
• 2: Sitaram Asur , Srinivasan Parthasarathy , Duygu Ucar, An event-based framework for characterizing the evolutionary behavior of interaction graphs, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281290]
• 3: Lars Backstrom , Dan Huttenlocher , Jon Kleinberg , Xiangyang Lan, Group formation in large social networks: membership, growth, and evolution, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150412]
• 4: Klaus Berberich , Srikanta Bedathur , Thomas Neumann , Gerhard Weikum, A time machine for text search, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277831]
• 5: Andrei Z. Broder , Moses Charikar , Alan M. Frieze , Michael Mitzenmacher, Min-wise independent permutations, Journal of Computer and System Sciences, v.60 n.3, p.630-659, June 2000 [doi>10.1006/jcss.1999.1690]
• 6: Stuart K. Card , Jock D. Mackinlay , Ben Shneiderman, Readings in information visualization: using vision to think, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 7: Deepayan Chakrabarti , Ravi Kumar , Andrew Tomkins, Evolutionary clustering, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150467]
• 8: Peter A. Gloor , Rob Laubacher , Scott B. C. Dynes , Yan Zhao, Visualization of Communication Patterns in Collaborative Innovation Networks - Analysis of Some W3C Working Groups, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956875]
• 9: Peter A. Gloor , Yan Zhao, Analyzing Actors and Their Discussion Topics by Semantic Social Network Analysis, Proceedings of the conference on Information Visualization, p.130-135, July 05-07, 2006 [doi>10.1109/IV.2006.23]
• 10: Jeffrey Heer , Danah Boyd, Vizster: Visualizing Online Social Networks, Proceedings of the Proceedings of the 2005 IEEE Symposium on Information Visualization, p.5, October 23-25, 2005 [doi>10.1109/INFOVIS.2005.39]
• 11: Nathalie Henry , Jean-Daniel Fekete, MatrixExplorer: a Dual-Representation System to Explore Social Networks, IEEE Transactions on Visualization and Computer Graphics, v.12 n.5, p.677-684, September 2006 [doi>10.1109/TVCG.2006.160]
• 12: Varun Kacholia , Shashank Pandit , Soumen Chakrabarti , S. Sudarshan , Rushi Desai , Hrishikesh Karambelkar, Bidirectional expansion for keyword search on graph databases, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 13: David Kempe , Jon Kleinberg , Éva Tardos, Maximizing the spread of influence through a social network, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956769]
• 14: Gautam Kumar , Michael Garland, Visual Exploration of Complex Time-Varying Graphs, IEEE Transactions on Visualization and Computer Graphics, v.12 n.5, p.805-812, September 2006 [doi>10.1109/TVCG.2006.193]
• 15: Jure Leskovec , Jon Kleinberg , Christos Faloutsos, Graphs over time: densification laws, shrinking diameters and possible explanations, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081893]
• 16: M. Newman. Clustering and preferential attachment in growing networks. Phys. Rev. E, 64, 2001.
• 17: Adam Perer , Ben Shneiderman, Balancing Systematic and Flexible Exploration of Social Networks, IEEE Transactions on Visualization and Computer Graphics, v.12 n.5, p.693-700, September 2006 [doi>10.1109/TVCG.2006.122]
• 18: Ermir Qeli , Wolfgang Wiechert , Bernd Freisleben, Visual Exploration of Time-Varying Matrices, Proceedings of the Ninth International Conference on Information Visualisation, p.889-895, July 06-08, 2005 [doi>10.1109/IV.2005.136]
• 19: P. Resnik. Semantic similarity in a taxonomy: An information-based measure and its application to problems of ambiguity in natural language. Journal of Artifical Intelligence Research, 11:95--130, 1999.
• 20: Ravi Samtaney , Deborah Silver , Norman Zabusky , Jim Cao, Visualizing Features and Tracking Their Evolution, Computer, v.27 n.7, p.20-27, July 1994 [doi>10.1109/2.299407]
• 21: Nan Wang , Srinivasan Parthasarathy , Kian-Lee Tan , Anthony K. H. Tung, CSV: visualizing and mining cohesive subgraphs, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376663]
• 22: H. Yang, S. Parthasarathy, and S. Mehta. Mining spatial object patterns in scientific data. Proc. 9th Intl. Joint Conf. on Artificial Intelligence, 2005.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Measurement

Keywords:
dynamic interaction networks, graph visualization, visual analytics