Guy Melancon
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.
- M. Amiel, G. Melançon, and C. Rozenblat. Réseaux multi-niveaux: l'exemple des échanges aériens mondiaux. M@ppemonde, 78, 2005.Google Scholar
- 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. Google ScholarDigital Library
- A.-L. Barabasi and R. Albert. Emergence of scaling in random networks. Science, 286:509--512, 1999.Google ScholarCross Ref
- B. Bollobás. Random Graphs. Academic Press, London, 1985.Google Scholar
- S. Bornholdt and G. Schuster, editors. Handbook of Graphs and Networks: From the Genome to the Internet. Wiley-VCH, 2003. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- Y. Chiricota, 2006. Personal communication.Google Scholar
- M. Delest, T. Munzner, D. Auber, and J.-P. Domenger. Exploring infovis publication history with tulip (2nd place - infovis contest). In IEEE Symposium on Information Visualization, page 110. IEEE Computer Society, 2004. Google ScholarDigital Library
- 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.Google Scholar
- S. N. Dorogovtsev and J. F. F. Mendes. Evolution of Networks: From Biological Nets to the Internet and WWW. Oxford University Press, 2003. Google ScholarDigital Library
- H. Ebel, L.-I. Mielsch, and S. Bornholdt. Scale-free topology of e-mail networks. Physics Reviews E, 66(035103(R)), 2002.Google Scholar
- P. Erdos and A. Renyi. On random graphs. Publ. Math. Debrecen, 6:290--297, 1959.Google Scholar
- P. Erdos and A. Rényi. On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci., 5:17--61, 1960.Google Scholar
- J.-D. Fekete, G. Grinstein, and C. Plaisant. "ieee infovis 2004 contest", the history of infovis (www.cs.umd.edu/hcil/iv04contest), 2004.Google Scholar
- B. Gaume, 2003. Personal communication.Google Scholar
- 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.Google Scholar
- M. Ghoniem. Outils de visualisation et d'aide à la mise au point de programmes avec contraintes. Phd, Université de Nantes, 2005.Google Scholar
- M. Ghoniem, J.-D. Fekete, and P. Castagliola. Comparaison de la lisibilité des graphes en représentation noeuds-liens et matricielle. In IHM 2004, ACM International Conference Proceedings Series, pages 77--84, Namur, Belgique, 2004. ACM Press. Google ScholarDigital Library
- M. Ghoniem, J.-D. Fekete, and P. Castagliola. A comparison of the readability of graphs using node-link and matrix-based representations, 2004.Google Scholar
- M. Ghoniem, J.-D. Fekete, and P. Castagliola. On the readability of graphs using node-link and matrix-based representations: a controlled experiment and statistical analysis. Information Visualization, 4(2):114--135, 2005. Google ScholarDigital Library
- A. Iamnitchi, M. Ripeanu, and I. T. Foster. Small-world file-sharing communities. In IEEE INFOCOM. IEEE Communications Society, 2004.Google ScholarCross Ref
- D. Jungnickel. Graphs, Networks and Algorithms. Springer Verlag, 1999.Google Scholar
- B. Lee, C. S. Parr, C. Plaisant, B. B. Bederson, V. D. Veklser, W. D. Gray, and C. Kotfila. Treeplus: Interactive exploration of networks with enhanced tree layouts. IEEE Transactions on Visualization and Computer Graphics, Special Issue on Visual Analytics, To appear. Google ScholarDigital Library
- 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.Google Scholar
- M. Newman, D. Watts, and S. Strogatz. Random graph models of social networks. Proceedings of the National Academy of Sciences, 99:2566--2572, 2002.Google ScholarCross Ref
- M. E. J. Newman. The structure and function of complex networks. SIAM Review, 45:167--256, 2003.Google ScholarDigital Library
- 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.Google Scholar
- J. Park and M. E. J. Newman. The statistical mechanics of networks. Physics Reviews E, 70, 2004.Google Scholar
- A. Wagner. How the global structure of protein interaction networks evolves. Proceedings of the Royal Society London B, 270:457--466, 2003.Google ScholarCross Ref
- D. Watts and S. H. Strogatz. Collective dynamics of "small-world" networks. Nature, 393:440--442, 1998.Google ScholarCross Ref
- D. J. Watts. Small Worlds. Princeton University Press, 1999.Google Scholar
- D. J. Watts. Six Degrees: The Science of a Connected Age. W. W. Norton & Company, 2004.Google Scholar
- J. v. Wijk and F. v. Ham. Interactive visualization of small world graphs. In T. Munzner and M. Ward, editors, IEEE Symposium on Information Visualisation, Austin, TX, USA, 2004. IEEE Computer Science press. Google ScholarDigital Library
- S. Wuchty, A.-L. Barabasi, and M. T. Ferdig. Stable evolutionary signal in a yeast protein interaction network. BMC Evolutionary Biology, 6(8), 2006.Google Scholar
Index Terms
- Just how dense are dense graphs in the real world?: a methodological note
Recommendations
Note: Many disjoint dense subgraphs versus large k-connected subgraphs in large graphs with given edge density
It is proved that for all positive integers d,k,s,t with t>=k+1 there is a positive integer M=M(d,k,s,t) such that every graph with edge density at least d+k and at least M vertices contains a k-connected subgraph on at least t vertices, or s pairwise ...
Dense graphs are antimagic
An antimagic labeling of graph a with m edges and n vertices is a bijection from the set of edges to the integers 1,…,m such that all n vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with the same ...
Supereulerian width of dense graphs
For a graph G, the supereulerian width(G) of a graph G is the largest integer s such that G has a spanning (k;u,v)-trail-system, for any integer k with 1ks, and for any u,vV(G) with uv. Thus (G)2 implies that G is supereulerian, and so graphs with ...
Comments