Just how dense are dense graphs in the real world?: a methodological note

ABSTRACT

This methodological note focuses on the edge density of real world examples of networks. The edge density is a parameter of interest typically when putting up user studies in an effort to prove the robustness or superiority of a novel graph visualization technique. We survey many real world examples all being of equal interest in Information Visualization, and draw a list of conclusions on how to tune edge density when randomly generating graphs in order to build artificial though realistic examples.

REFERENCES

• 1: M. Amiel, G. Melançon, and C. Rozenblat. Réseaux multi-niveaux: l'exemple des échanges aériens mondiaux. M@ppemonde, 78, 2005.
• 2: D. Auber, Y. Chiricota, F. Jourdan, and G. Melançon. Multiscale navigation of small world networks. In IEEE Symposium on Information Visualisation, pages 75--81, Seattle, GA, USA, 2003. IEEE Computer Science Press.
• 3: A.-L. Barabasi and R. Albert. Emergence of scaling in random networks. Science, 286:509--512, 1999.
• 4: B. Bollobás. Random Graphs. Academic Press, London, 1985.
• 5: Stefan Bornholdt , Heinz Georg Schuster, Handbook of Graphs and Networks: From the Genome to the Internet, John Wiley & Sons, Inc., New York, NY, 2003
• 6: F. Boutin, J. Thièvre, and M. Hascoët. Focus-based filtering + clustering technique for power-law networks with small world phenomenon. In R. F. Erbacher, J. C. Roberts, M. T. Gröhn, and K. Börner, editors, SPIE Electronic Imaging/Visualization and Data Analysis, volume 6060, San Jose, California, 2006. SPIE IS&T.
• 7: Q. Chen, H. Chang, R. Govindan, and S. Jamin. The origin of power laws in internet topologies revisited. In IEEE INFOCOM, Anchorage, Alaska, 2001. IEEE Communications Society.
• 8: Y. Chiricota, 2006. Personal communication.
• 9: Maylis Delest , Tamara Munzner , David Auber , Jean-Philippe Domenger, Exploring InfoVis Publication History with Tulip, Proceedings of the IEEE Symposium on Information Visualization (INFOVIS'04), p.216.10, October 10-12, 2004 [doi>10.1109/INFOVIS.2004.23]
• 10: D. Dion, D. Auber, B. Leblanc, and G. Melançon. Graphe d'associations verbales: élaboration et visualisation. In Cognitique: vers une informatique plus cognitive et sociale, pages 223--232. Cépaduès-Editions, 2003.
• 11: S. N. Dorogovtsev and J. F. F. Mendes. Evolution of Networks: From Biological Nets to the Internet and WWW. Oxford University Press, 2003.
• 12: H. Ebel, L.-I. Mielsch, and S. Bornholdt. Scale-free topology of e-mail networks. Physics Reviews E, 66(035103(R)), 2002.
• 13: P. Erdos and A. Renyi. On random graphs. Publ. Math. Debrecen, 6:290--297, 1959.
• 14: P. Erdos and A. Rényi. On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci., 5:17--61, 1960.
• 15: J.-D. Fekete, G. Grinstein, and C. Plaisant. "ieee infovis 2004 contest", the history of infovis (www.cs.umd.edu/hcil/iv04contest), 2004.
• 16: B. Gaume, 2003. Personal communication.
• 17: B. Gaume, N. Hathout, and P. Muller. Désambiguïsation par proximité structurelle. In Conférence Traitement Automatique du Langage Naturel (TALN'2004), pages 205--214, Fez, Maroc, 2004. ATALA.
• 18: M. Ghoniem. Outils de visualisation et d'aide à la mise au point de programmes avec contraintes. Phd, Université de Nantes, 2005.
• 19: Mohammad Ghoniem , Jean-Daniel Fekete , Philippe Castagliola, Comparaison de la lisibilité des graphes en représentation noeuds-liens et matricielle, Proceedings of the 16th conference on Association Francophone d'Interaction Homme-Machine, p.77-84, August 30-September 03, 2004, Namur, Belgium [doi>10.1145/1148613.1148625]
• 20: M. Ghoniem, J.-D. Fekete, and P. Castagliola. A comparison of the readability of graphs using node-link and matrix-based representations, 2004.
• 21: Mohammad Ghoniem , Jean-Daniel Fekete , Philippe Castagliola, On the readability of graphs using node-link and matrix-based representations: a controlled experiment and statistical analysis, Information Visualization, v.4 n.2, p.114-135, July 2005 [doi>10.1057/palgrave.ivs.9500092]
• 22: A. Iamnitchi, M. Ripeanu, and I. T. Foster. Small-world file-sharing communities. In IEEE INFOCOM. IEEE Communications Society, 2004.
• 23: D. Jungnickel. Graphs, Networks and Algorithms. Springer Verlag, 1999.
• 24: Bongshin Lee , Cynthia S. Parr , Catherine Plaisant , Benjamin B. Bederson , Vladislav D. Veksler , Wayne D. Gray , Christopher Kotfila, TreePlus: Interactive Exploration of Networks with Enhanced Tree Layouts, IEEE Transactions on Visualization and Computer Graphics, v.12 n.6, p.1414-1426, November 2006 [doi>10.1109/TVCG.2006.106]
• 25: G. Melançon and I. Herman. Dag drawing from an information visualization perspective. In W. d. Leeuw and R. v. Liere, editors, Joint Eurographics and IEEE TCVG Symposium on Visualization (Data Visualization '00), pages 3--13, Amsterdam, 2000. Springer-Verlag.
• 26: M. Newman, D. Watts, and S. Strogatz. Random graph models of social networks. Proceedings of the National Academy of Sciences, 99:2566--2572, 2002.
• 27: M. E. J. Newman. The structure and function of complex networks. SIAM Review, 45:167--256, 2003.
• 28: A. Noack. An energy model for visual graph clustering. In 11th International Symposium on Graph Drawing (GD 2003), volume 2912 of Lecture Notes in Computer Science, pages 425--436, Perugia, Italy, 2003.
• 29: J. Park and M. E. J. Newman. The statistical mechanics of networks. Physics Reviews E, 70, 2004.
• 30: A. Wagner. How the global structure of protein interaction networks evolves. Proceedings of the Royal Society London B, 270:457--466, 2003.
• 31: D. Watts and S. H. Strogatz. Collective dynamics of "small-world" networks. Nature, 393:440--442, 1998.
• 32: D. J. Watts. Small Worlds. Princeton University Press, 1999.
• 33: D. J. Watts. Six Degrees: The Science of a Connected Age. W. W. Norton & Company, 2004.
• 34: Frank van Ham , Jarke J. van Wijk, Interactive Visualization of Small World Graphs, Proceedings of the IEEE Symposium on Information Visualization (INFOVIS'04), p.199-206, October 10-12, 2004 [doi>10.1109/INFOVIS.2004.43]
• 35: S. Wuchty, A.-L. Barabasi, and M. T. Ferdig. Stable evolutionary signal in a yeast protein interaction network. BMC Evolutionary Biology, 6(8), 2006.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Evaluation/methodology

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms
  G.3 PROBABILITY AND STATISTICS

  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Benchmarking

Keywords:
edge density, graph models, information visualization, interface evaluation, random generation, real world examples