DOC PREVIEW
GT CS 7450 - Graphs and Networks

This preview shows page 1-2-3-24-25-26-27-49-50-51 out of 51 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 51 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 51 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 51 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 51 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 51 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 51 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 51 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 51 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 51 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 51 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 51 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1Graphs and NetworksCS 4460/7450 - Information VisualizationFebruary 25, 2010John StaskoHW 3• Due next Thursday• Submit via t-square, more details to comeSpring 2010 CS 4460/7450 22Connections• Connections throughout our lives and the world Circle of friends Delta‟s flight plans …• Model connected set as a GraphSpring 2010 3CS 4460/7450What is a Graph?• Vertices (nodes) connected by• Edges (links)1 2 30 1 01 0 10 1 01231: 22: 1, 33: 2132Adjacency matrixAdjacency listDrawingSpring 2010 4CS 4460/74503Graph 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 2010 5CS 4460/7450Trees are Different• Subcase of general graph• No cycles• Typically directed edges• Special designated root vertexSpring 2010 6CS 4460/74504Graph 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 2010 7CS 4460/7450Graph 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 2010 8CS 4460/74505Layout Examples• Homework assignment• Let‟s judge!Spring 2010 9CS 4460/7450Results• What led to particular layouts being liked more?• DiscussSpring 2010 10CS 4460/74506Layout AlgorithmsEntireresearchcommunity‟sfocusSpring 2010 11CS 4460/7450Vertex Issues• Shape• Color• Size• Location• LabelSpring 2010 12CS 4460/74507Edge Issues • Color• Size• Label• Form Polyline, straight line, orthogonal, grid, curved, planar, upward/downward, ...Spring 2010 13CS 4460/7450Aesthetic Considerations•Crossings-- minimize towards planar•Total Edge Length-- minimize towards proper scale•Area-- minimize towards efficiency•Maximum Edge Length-- minimize longest edge•Uniform Edge Lengths-- minimize variances•Total Bends-- minimize orthogonal towards straight-lineSpring 2010 14CS 4460/74508Which 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 2010 15CS 4460/7450Shneiderman’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 2010 16CS 4460/74509Layout Heuristics• Layout algorithms can be planar grid-based orthogonal curved lines hierarchies circular ...Spring 2010 17CS 4460/7450Types of Layout AlgorithmsFrom:P. Mutzel, et alGraph Drawing „97Spring 2010 18CS 4460/745010Common Layout Techniques• Hierarchical• Force-directed• Circular• Geographic-based• Clustered• Attribute-based• MatrixWe will discuss manyof these further in theslides to comeSpring 2010 19CS 4460/7450Scale Challenge• May run out of space for vertices and edges (turns into “ball of string”)• Can really slow down algorithm• Sometimes use clusteringto help Extract highly connected sets of vertices Collapse some vertices togetherSpring 2010 20CS 4460/745011Navigation/Interaction Challenge• How do we allow a user to query, visit, or move around a graph?• Changing focus may entail a different renderingSpring 2010 21CS 4460/7450Graph 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 2010 22CS 4460/745012Graph Drawing Uses• Many domains and data sets can benefit significantly from nice graph drawings• Let‟s look at some examples…Spring 2010 23CS 4460/7450Social 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 2010 24CS 4460/7450131981http://www.mpi-fg-koeln.mpg.de/~lk/netvis/trade/WorldTrade.htmlSpring 2010 25CS 4460/74501992Spring 2010 26CS 4460/745014Social Network Visualization• Social Network Analysis http://www.insna.orgSpring 2010 27CS 4460/7450People connectionsCharles Isbell, CobotSpring 2010 28CS 4460/745015Spring 2010 29CS 4460/7450Spring 2010 30CS 4460/745016Spring 2010 31CS 4460/74503 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 graphsthan maps!Spring 2010 32CS 4460/745017http://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 2010 33CS 4460/7450TouchGraphwww.touchgraph.comSpring 2010 34CS 4460/745018Mucho Exampleshttp://www.visualcomplexity.comSpring 2010 35CS 4460/7450But 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… Still, understanding the layout algorithms is very important for infovisSpring 2010 36CS 4460/745019Tree Layout• Run a breadth-first search from a vertex This imposes a spanning tree on the graph• Draw the spanning tree• Simple and fast, but obviously doesn‟t represent the whole graphSpring 2010 CS 4460/7450 37Hierarchical LayoutSpring 2010 CS 4460/7450 38http://www.csse.monash.edu.au/hons/se-projects/2006/Kieran.Simpson/output/html/node7.html#sugiyamaexampleOften called


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?