Discovering parametric clusters in social small-world graphs

ABSTRACT

We present a strategy for analyzing large, social small-world graphs, such as those formed by human networks. Our approach brings together ideas from a number of different research areas, including graph layout, graph clustering and partitioning, machine learning, and user interface design. It helps users explore the networks and develop insights concerning their members and structure that may be difficult or impossible to discover via traditional means, including existing graph visualization and/or statistical methods.

References

1. Ahlberg, C., and Shneiderman, B. Visual information seeking: Tight coupling of dynamic query filters with starfield displays. In Human Factors in Computing Systems. Conference Proceedings CHI'94 (1994), pp. 313--317.
2. Albert, R., and Baraba si, A.-L. Statistical mechanics of complex networks. Rev. Mod. Phys. 74 (2002), 47--97.
3. Albert, R., Jeong, H., and Bar'a basi, A.-L. Diameter of the world wide web. Nature 401 (1999), 130--131.
4. Auber, D., Chiricota, Y., Jourdan, F., and Melancon, G. Multiscale visualization of small world networks. In Proceedings of the 2003 IEEE Symposium on Information Visualization (2003), pp. 75--81.
5. Fruchterman, T. M. J., and Reingold, E. M. Graph drawing by force-directed placement. Software - Practice and Experience 21, 11 (1991), 1129--1164.
6. Herman, I., Marshall, M. S., and Melancon, G. Density functions for visual attributes and effective partitioning in graph visualization. In INFOVIS (2000), pp. 49--56.
7. Herman, I., Marshall, M. S., Melancon, G., Duke, D. J., Delest, M., and Domenger, J.-P. Skeletal images as visual cues in graph visualization. In Data Visualization '99, E. Gröller, H. Löffelmann, and W. Ribarsky, Eds. Springer-Verlag Wien, 1999, pp. 13--22.
8. Ianmitchi, A. Resource Discovery in Large Resource-Sharing Environments. PhD thesis, The University of Chicago, 2003.
9. Kohonen, T. Self-Organization and Associative Memory, 3rd ed. Springer-Verlag, Berlin, 1989.
10. Meyer, B. Self-organizing graphs: A neural network perspective of graph layout. In Proceedings of the 6th International Symposium on Graph Drawing (1998), pp. 246--262.
11. Munzer, T. Exploring large graphs in 3d hyperbolic space. In IEEE Computer Graphics and Applications, Vol. 18, No. 4 (1998), pp. 18--23.
12. Noack, A. An energy model for visual graph clustering. In Proceedings of the 11th International Symposium on Graph Drawing (2003), pp. 425--436.
13. Six, J. M., and Tollis, I. G. Effective graph visualization via node grouping. Proceedings of the 2001 IEEE Symposium on Information Visualization (2001), 51--59.
14. Stasko, J. T., and Wehrli, J. F. Three-dimensional computation visualization. In Proc. IEEE Symp. Visual Languages, VL (24-27 1993), E. P. Glinert and K. A. Olsen, Eds., IEEE Computer Society, pp. 100--107.
15. van Dongen, S. Graph Clustering by Flow Simulation. PhD thesis, University of Utrecht, 2000.
16. van Ham, F., and van Wijk, J. J. Interactive visualization of small world graphs. In Proceedings of the 2004 IEEE Symposium on Information. Visualization (2004), pp. 199--206.
17. Ware, C., and Franck, G. Evaluating stereo and motion cues for visualizing information nets in three dimensions. ACM Transactions on Graphics 15, 2 (1996), 121--140.
18. Watts, D., and Strogatz, S. Collective dynamics of small-world networks. Nature 393 (1998), 440--442.

Index Terms

• Computing methodologies

  • Computer graphics

    • Graphics systems and interfaces

  • Machine learning

• Human-centered computing

  • Human computer interaction (HCI)

    • Interaction devices

      • Graphics input devices