Transcript Circular Layout

Visualization
Taxonomies and Techniques
Graphs
University of Texas – Pan American
CSCI 6361
Graphs and Networks
Graphs Show “Connections”
• Connections among …anything
• Model connected set 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 visualization
NSFNET Traffic 1991, NSFNET backbone nodes
are shown at the top, regional networks below,
traffic volume is depicted from purple (zero
bytes) to white (100 billion bytes), visualization
by NCSA using traffic data provided by the Merit
Graphs Show “Connections”
• Connections among …anything
• Model connected set 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 visualization
Trade among countries.
There are many challenges …
Graphs Show “Connections”
• Connections among …anything
• Model connected set 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 visualization
SEMNET, 1987
Graphs Show “Connections”
• Connections among …anything
• Model connected set 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 visualization
vizster, social network, Facebook
http://vis.stanford.edu/jheer/projects/vizster/
(download *.wmv)
Social Network Visualization
• Social Network Analysis
– Among first studied
• By no means new …
– http://www.insna.org
– Early, by social scientists
• Sociologists,
anthropologists
• Now, very keen interest in
social networks
– From Facebook to terrorists
Graphs and Networks
Will see some techniques
• Graph layout
• Node link layouts
– Layered / Sugiyama
– Force directed
– Other
• Matrix layouts
• Attribute based layouts
About Graphs
• Graph: G = (V, E)
• Vertices (nodes) connected by
edges (links)
– Can have cycles
– Edges can be directed or undirected
– Degree of vertex is number of edges
connected to it
•
In-degree and out-degree for directed graphs
– Edges can have values (weights)
•
nominal, ordinal or quantitative … or be
semantic
• Trees, again …
– Special case of general graph – no
cycle
– Typically directed edges
– Special designated root vertex
Graph Visualization Challenges
• Graph layout and positioning
– Make a concrete rendering of
abstract graph
• Navigation/Interaction
– How to support user changing
focus, moving around the graph,
…
• Scale
– Small graphs are not hard for
above
– BUT, 10 – 100 – 1000 … which are
the interesting ones
• Layout – an entire research
community focus
Aesthetic Considerations
How to lay out a graph, consider …
• Line (edge) 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-line
• All at once!
– Various studies examined which of the aesthetic factors matter most and/or what
kinds of layout/vis techniques look best
– Results mixed: Edge crossings do seem important
Graph Visualization
Task Taxonomy
• 1. Topology-based tasks
–
–
–
–
Adjacency: Find the set of nodes adjacent to a node
Accessibility: Find the set of nodes accessible to a node
Common connection: Given nodes, find the set of nodes connected to all
Connectivity: Find shortest path, Identify clusters, Identify connected components
• 2. Attribute-based tasks
– For nodes: Find the nodes having a specific attribute value
– For edges: Given a node, find nodes connected only by certain kinds of edges
• 3. Browsing tasks
– Follow path: Follow a given path
– Revisit : Return to a previously visited node
• 4. Overview task
– Compound exploratory task : Estimate size of a network, find patterns, …
Layout Techniques
Quick Look – there are many …
• Layout algorithms
can create:
– polyline edges
– planar –
•
no edge crossings
– orthogonal –
•
horizontal and vertical
lines/polylines
– grid-based •
–
–
–
–
vertices, crossings,
edge bends have
integer coords
curved lines
hierarchies
circular
...
•
P. Mutzel, et al.
Graph Drawing ’97
Layout Techniques
Quick Look
• Will see a couple
• Common
techniques:
–
–
–
–
–
–
–
Hierarchical
Force-directed
Circular
Geographic-based
Clustered
Attribute-based
Matrix
Another Graph Drawing Examples
Human Disease
• Lens to
view
•
http://www.nyti
mes.com/intera
ctive/2008/05/0
5/science/2008
0506_DISEASE
.html
Hierarchical Graph Layout
Hierarchical Graph Layout
Sugiyama layout
• Often called Sugiyama
layout
• Try to impose hierarchy on
graph
– Reverse edges if needed to
remove cycles
• Introduce dummy nodes
• Put nodes into layers, or
levels
• Order l->r to minimize
crossings
Hierarchical Layout
Sugiyama Layout
• Readable top down
flow
• Good for graphs
that have an
intrinsic ordering
– Not suitable for
graphs that don’t
have an intrinsic top
down structure
– ‘Depth’ in graph
mapped to one axis
• Lots of graph
drawing libraries
– graphviz lib:
–
http://www.graphviz.org
http://gephi.org
Unix “ancestry”
Hierarchical Layout
Sugiyama Layout
• Readable top down
flow
• Good for graphs
that have an
intrinsic ordering
– Not suitable for
graphs that don’t
have an intrinsic top
down structure
– ‘Depth’ in graph
mapped to one axis
• Lots of graph
drawing libraries:
– graphviz lib,
–
http://www.graphviz.org
http://gephi.org
Force-Directed Layout
Force-Directed Layout
• Define through equations
• Spring model (common), or,
more generally, force directed
– Edges – Springs (gravity
attraction)
– Vertices – Charged particles
(repulsion)
• Equations for forces
• Iteratively recalculate to
update positions of vertices
http://mbostock.github.io/protovis/ex/force.html
• Seeking local minimum of
energy
– Sum of forces on each node is 0
Force-Directed Example
• “Springs (forces) find iteratively find equilibrium”
Force-Directed Examples
Protovis and D3
• Protovis: http://vis.stanford.edu/protovis/ex/force.html
• D3 (cf collapsible force directed): https://github.com/mbostock/d3/wiki/Gallery
Graphs
Force Directed Layout
• Very flexible, aesthetic layouts on many types of graphs
– Can add custom forces
– Relatively easy to implement
• Repulsion loop is O(n2) per iteration
– Can speed up to O(n log n) using quadtree or k-d tree
• Prone to local minima
– Can use simulated annealing
Graphs
Force directed layout
• Many variations, but physical analogy:
• Repulsion : fR(d) = CR * m1*m2 / d2
– m1, m2 are node masses
– d is distance between nodes
• Attraction : fA(d) = CA * (d – L)
– L is the rest length of the spring
– i.e. Hooke’s Law
• Total force on a node x with position x’
– Σ neighbors(x) : fA(||x’-y’||) * (x’-y’) + -fR(||x’-y’||) * (x’-y’)
• Examples
– 23 second example: http://www.youtube.com/watch?v=AYrkWSDkfLM
– 60 second example: http://www.youtube.com/watch?v=QlXRapQW4q0
Graphs
Force-directed layout
• Recall
Force Directed with Magnets
•
http://www.youtube.com/watch?v=K4GOxJywB-U
•
Not much 1st minute
Other Layouts
• Orthogonal
– Good for UML diagrams
– algorithmically complex
Circular Layout
• Circular Layout
–
–
–
–
Very simple
Space vertices out around circle
Draw lines (edges) to connect vertices
But, aesthetic heuristics …
• Textarc (more next time)
Textarc: http://www.textarc.org/
Nested Layouts
• Recursively
apply layout
algorithms
• Good for
graphs with
hierarchical
structure
Graphs
visual complexity
•
http://www.visualcomplexity.com/vc/
Graphs
Adjacency Matrix
Graphs
Adjacency Matrix
• Alternative to node link
• Adjacency matrix representation
– “Mark” where edges are, as shown in the grid below for the graph at left
– E.g., A-B, A-C (and inverse)
Graphs
Adjacency matrix
• Good for dense graphs
– Visually scalable
– Can spot clusters
• Nodes of high degree have
many connections, so
many entries in adjacency
tale
• Lots of dots at clusters
• However
– Abstract visualization
– Hard to follow paths (indeed)
Matrix Representations
• Interest in matrix
representations of
graphs
• Regularity, symmetry,
and structure of a
matrix good
• Well understood
• Difficulties of scale
E.g., “MatrixExplorer”
• Provides matrix view in combination with node-link and various
operations for gaining different perspectives
– Henry & Fekete TVCG (InfoVis) ‘06
“MatrixExplorer”
Node Reordering
• Important operation with matrix representations
E.g., “NodeTrix”
• Hybrid of matrix and
node-link
– Henry & Fekete
TVCG (InfoVis) ‘07
Graphs
Attribute Driven
Graphs
Attribute-driven layout
• Large node-link diagrams can be challenging to perceptually order
• Can use data attributes to perform layout
– E.g., scatterplot based on node values
– Dynamic queries and/or brushing can be used to enhance perception of
connectivity
Barsky, 2008
Graphs
Attribute-driven layout
• Semantic substrates
– E.g., below shows relations between Circuit Court cases and Supreme Court
cases
Shneiderman, 2006
Trees and Graphs Conclusion
• Trees:
– Indentation
• Simple, effective for small trees
– Node link and layered
• Looks good but needs exponential space
– Enclosure (treemaps)
• Good for size related tasks but suffer in structure related tasks
• Graphs:
– Node link
• Familiar, but problematic for dense graphs
– Adjacency matrices
• Abstract, hard to follow paths
– Attribute-driven
• Not always possible
• No single “best” solution – a design problem
Web Pages and Videos
Graphs
•
•
•
•
•
•
•
vizster, social network, Facebook: http://vis.stanford.edu/jheer/projects/vizster/, (download *.wmv)
NY Times diseases: http://www.nytimes.com/interactive/2008/05/05/science/20080506_DISEASE.html
Force directed layout protovis: http://mbostock.github.io/protovis/ex/force.html
Protovis: http://vis.stanford.edu/protovis/ex/force.html
D3 (cf collapsible force directed): https://github.com/mbostock/d3/wiki/Gallery
Magnets and graphs: http://www.youtube.com/watch?v=K4GOxJywB-U
Force directed layout examples
– 23 second example: http://www.youtube.com/watch?v=AYrkWSDkfLM
– 60 second example: http://www.youtube.com/watch?v=QlXRapQW4q0
• Visual complexity: http://www.visualcomplexity.com/vc/
End
• .