DOC PREVIEW
GT CS 7450 - Graphs and Networks

This preview shows page 1-2-3-21-22-23-43-44-45 out of 45 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1Graphs and NetworksCS 4460/7450 - Information VisualizationMarch 24, 2009John StaskoConnections• Connections throughout our lives and the world− Circle of friends− Delta’s flight plans− …• Model connected set as a GraphSpring 2009 2CS 4460/74502What is a Graph?• Vertices (nodes) connected by• Edges (links)1 2 30 1 01 0 10 1 01231: 22: 1, 33: 2132Adjacency matrixAdjacency listDrawingSpring 2009 3CS 4460/7450Graph Terminology• Graphs can have cycles• Graph edges can be directedor undirected• The degreeof a vertex is the number of edges connected to it−In-degreeand out-degreefor directed graphs• Graph edges can have values (weights) on them (nominal, ordinal or quantitative)Spring 2009 4CS 4460/74503Trees are Different• Subcase of general graph• No cycles• Typically directed edges• Special designated root vertexSpring 2009 5CS 4460/7450Graph Uses• In information visualization, any number of data sets can be modeled as a graph− US telephone system− World Wide Web− Distribution network for on-line retailer− Call graph of a large software system− Semantic map in an AI algorithm− Set of connected friends• Graph/network visualization is one of the oldest and most studied areas of InfoVisSpring 2009 6CS 4460/74504Graph Visualization Challenges• Graph layout and positioning− Make a concrete rendering of abstract graph• Navigation/Interaction− How to support user changing focus and moving around the graph• Scale− Above two issues not too bad for small graphs, but large ones are much tougherSpring 2009 7CS 4460/7450Layout Examples• Homework assignment• Let’s judge!Spring 2009 8CS 4460/74505Results• What led to particular layouts being liked more?• DiscussSpring 2009 9CS 4460/7450Layout AlgorithmsEntireresearchcommunity’sfocusSpring 2009 10CS 4460/74506Vertex Issues• Shape• Color• Size• Location• LabelSpring 2009 11CS 4460/7450Edge Issues • Color• Size• Label• Form− Polyline, straight line, orthogonal, grid, curved, planar, upward/downward, ...Spring 2009 12CS 4460/74507Aesthetic Considerations••CrossingsCrossings-- minimize towards planar••Total Edge LengthTotal Edge Length-- minimize towards proper scale••AreaArea-- minimize towards efficiency••Maximum Edge LengthMaximum Edge Length-- minimize longest edge••Uniform Edge LengthsUniform Edge Lengths-- minimize variances••Total BendsTotal Bends-- minimize orthogonal towards straight-lineSpring 2009 13CS 4460/7450Which Matters?• Various studies examined which of the aesthetic factors matter most and/or what kinds of layout/vis techniques look best− Purchase, Graph Drawing ’97− Ware et al, Info Vis1(2)− Ghoniem et al, Info Vis4(2)− van Ham & Rogowitz, TVCG‘08− …• Results mixed: Edge crossings do seem importantSpring 2009 14CS 4460/74508Shneiderman’s NetViz Nirvana1) Every node is visible 2) For every node you can count its degree3) For every link you can follow it from source to destination4) Clusters and outliers are identifiableSpring 2009 15CS 4460/7450Layout Heuristics• Layout algorithms can be− planar− grid-based− orthogonal− curved lines− hierarchies− circular− ...Spring 2009 16CS 4460/74509Types of Layout AlgorithmsFrom:P. Mutzel, et alGraph Drawing ‘97Spring 2009 17CS 4460/7450Common Layout Techniques• Force-directed• Circular• Geographic-based• Clustered• Attribute-based• MatrixWe will discuss manyof these further in theslides to comeSpring 2009 18CS 4460/745010Scale Challenge• May run out of space for vertices and edges (turns into “ball of string”)• Can really slow down algorithm• Often use clusteringto help− Extract highly connected sets of vertices− Collapse some vertices togetherSpring 2009 19CS 4460/7450Navigation/Interaction Issues• How do we allow a user to query, visit, or move around a graph?• Changing focus may entail a different renderingSpring 2009 20CS 4460/745011Graph Drawing Resources• Book− diBattista, Eades, Tamassia, and Tollis, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, 1999• Tutorial (talk slides)− http://www.cs.brown.edu/people/rt/papers/gd-tutorial/gd-constraints.pdf• Web links− http://graphdrawing.org− http://www.graphviz.orgSpring 2009 21CS 4460/7450Graph Drawing Uses• Many domains and data sets can benefit significantly from nice graph drawings• Let’s look at some examples…Spring 2009 22CS 4460/745012Social Analysis• Facilitate understanding of complex socio-economic patterns • Social Science visualization gallery (Lothar Krempel):− http://www.mpi-fg-koeln.mpg.de/~lk/netvis.html• Next slides: Krempel & Plumper’s study of World Trade between OECD countries, 1981 and 1992Spring 2009 23CS 4460/74501981http://www.mpi-fg-koeln.mpg.de/~lk/netvis/trade/WorldTrade.htmlSpring 2009 24CS 4460/7450131992Spring 2009 25CS 4460/7450Social Network Visualization• Social Network Analysis− http://www.insna.orgSpring 2009 26CS 4460/745014People connectionsCharles Isbell, CobotSpring 2009 27CS 4460/7450Spring 2009 28CS 4460/745015Spring 2009 29CS 4460/7450Spring 2009 30CS 4460/7450163 Subway Diagrams• Geographic landmarks largely suppressed on maps, except water (rivers in Paris, London) and asphalt (highways in Atlanta)− Rather fitting, no?• These are more graphsgraphsthan maps!Spring 2009 31CS 4460/7450http://www.ncsa.uiuc.edu/SCMS/DigLib/text/technology/Visualization-Study-NSFNET-Cox.htmlByte traffic into the ANS/NSFnet T3 backbone for the month of November, 1993Spring 2009 32CS 4460/745017TouchGraphwww.touchgraph.comSpring 2009 33CS 4460/7450Mucho Exampleshttp://www.visualcomplexity.comSpring 2009 34CS 4460/745018But InfoVis?• I generally don’t consider a pure graph layout (drawing) algorithm to be InfoVis− Nothing wrong with that, just an issue of focus• For InfoVis, I like to see some kind of interaction or a system or an application…Spring 2009 35CS 4460/7450Case Study• NicheWorks− Interactive Visualization of Very Large Graphs Graham WillsLucent (at that time)Spring 2009 36CS 4460/745019Big Graphs• 20,000 - 1,000,000 Nodes• Works well with 50,000• Projects− Software Engineering− Web site analysis− Large database correlation− Telephone fraud detectionSpring 2009 37CS 4460/7450Features• Typical interactive operations• Sophisticated graph layout algorithm− 3 LayoutsCircularHexagonalTree− 3 Incremental


View Full Document

GT CS 7450 - Graphs and Networks

Documents in this Course
Animation

Animation

23 pages

Load more
Download Graphs and Networks
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Graphs and Networks and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Graphs and Networks 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?