[Data Visualization] Arrange Networks and Trees

Networks and Trees

• A network (or graph) is made up of nodes and links and specifies the relationship between two or more nodes.
  • Trees do not have cycles.
• Nodes and links can have attributes independently.
• Example: social network on Facebook
  • Node: accounts (people, organizations, or pages)
  • Link: friendship (or subscription)
  • Node attributes: name, photo, website_url, …
  • Link attributes: last interaction time, …

Network Visualization in InfoVis

• Network visualization is one of the oldest research areas in InfoVis.
• Flight network
• Road network (junctions and roads)
• World Wide Web
• Social networks
• Biological pathways
• Bitcoin Transactions
• Artificial Neural Networks

Two Families of Visualization

• Node link diagram
  • Uses the connection channels
• Adjacency Matrix
• The big question: which is better?
  • Scalability
  • Effectiveness
  • Interactivity

Node Link Diagram

• In a node link diagram, nodes are drawn as point marks and the links connecting them are drawn as line marks.
• Triangular vertical node link layout
• Spline radial layout

Vertical Node-Link Layout

• Root on the top
• Leaves on the bottom
• Vertial spatial position shows depth
• Horizon tal spatial position does not encode an attribute.
  • Chosen by a layout algorithm

Horizontal Node-Link Layout

• Word Tree

Radial Layout

• The distance away from the center shows depth
• Vertical & horizontal spatial positions are chosen by a layout algorithm to avoid overlap.

Scalability

• The naïve node-link diagrams are useful for a tree with a few hundred nodes.
• For bigger trees, we need aggregate edges.

• Toward Better Scalability

Networks

• What tasks do users want to perforn on graphs?
  • Task taxonomy of graph visualization
• Topology-based tasks (can be well supported by node link diagrams)
  • Find the set of nodes adjacent to a node.
  • How many nodes are adjacent to a node?
• Attribute-based tasks
  • Find the nodes having a specific attribute value.
• Browsing tasks
  • Follow a given path.
• See Lee et al., “Task taxonomy for graph visualization” for more details.

Node-link Diagrams for Graphs

• How to determine the position of nodes?

Graph Drawing

• Graph drawing is a research area that aims to find a “good” 2D dep i ction of networks.
• What is a “good” network layout? (= quality measures)
  • Minimize the number of edge crossings
  • Display the symmetries of the graph
  • Minimize the number of bends along the edges
  • Maximize the smallest angle between two edges incident on the same vertex
  • Minimize the sum of edge length and the maximum length of an edge
  • Minimize the area of the drawing by producing a compact graph
  • …

• Many graph drawing algorithms are NP complete and seem not to have a polynomial time algorithm.
• So, we use approximation instead.
• Force-directed graph drawing is a class of algorithms that are based on a physical model
  • We define forces among the set of nodes/links.
  • We find a layout with minimum energy by simulating the movements of nodes/edges.

What are the “Forces”?

• Attractive forces are applied to
  • the two endpoints of an edge toward each other
  • all nodes toward the center of the viewbox
• Repulsive forces are applied to
  • each pair of nodes that are not neighbors
  • Forces applied to a node are summed up and used to compute the next position of the node (after a very small fraction of time = simulation)

Force-Directed Layout

1. Assign random initial positions to nodes
2. Compute the force applied to each node
3. Compute dx and dy
4. Slightly move the nodes towards dx , dy
5. Repeat 2-4 until the layout is stabilized (equilibrium state).

• Strengths:
  • Good quality
  • Easy to implement
  • Intuitive
  • Flexible
  • Interactive
• Weaknesses:
  • Non-deterministic
    • spatial memory cannot be exploited across different runs of the algorithm
  • Scalability (hairball)
  • Poor local minima
  • Continual bouncing

• The Hairball Problem

Toward Better Scalability

• Multilevel scalable force directed placement (sfdp)
• Generate simplified graphs: 𝐺 0 𝐺 1 𝐺 𝑙
  • Graph coarsening
  • Edge collapsing
• Place 𝐺 𝑙
• Use 𝐺 𝑘 1 to place 𝐺 𝑘
• For more information, see “Efficient, High Quality Force Directed Graph Drawing” by Yifan Hu.

• Multilevel Scalable Force-directed Placement

DeepDrawing

• Traditional graph drawing algorithms take long time.
• Sometimes we need to run the algorithm several times to obtain a desired layout (by tuning some parameters)
• Can we accelerate this process using deep learning?
• Wang et al., “DeepDrawing : A Deep Learning Approach to Graph Drawing”(TVCG 2019)

Adjacency Matrix

• All of the nodes in the network are laid out along the vertical and horizontal edges of a square region.
• Links between two nodes are indicated by coloring an area mark in the cell in the matrix that is the intersection between their row and column.
• Additional information about nodes and edges can be encoded by coloring matrix.
  • e.g., cluster of nodes
• The matrix becomes symmetric for an undirected graph.

Node-link Diagram vs Adjacency Matrix

NodeTrix Idiom

• Node-link diagrams are good for revealing the global structure.
• Adjacency matrices are good for revealing the local structure.
• Can we use both at the same time?
  • Social network data: globally sparse and locally dense
• Nathalie Henry, Jean Daniel Fekete, and Michael J. McGuffin, “ NodeTrix : A Hybrid Visualization of Social Networks” (InfoVis 2007)

• Identify communities
• Identify central actors

Enclosure

• Containment marks can be used to visualize the hierarchiy in data.
• Only works for trees (no cycles)

Treemaps

• The hierarchical relationships are shown with containment rather than connection.
• All of the children of a tree node are enclosed within the area allocated that node, creating a nested layout.
• The size of the nodes is mapped to some attribute of the node.

Neighborhood Preserving Treemaps

• Can we reflect the neighborhood relationship in a Treemap layout?
• Duarte et al., “Nmap: A Novel Neighborhood Preservation Space filling Algorithm” (InfoVis 2014)
  • e.g., cities in Korea have a hierarchy
    • Korea
      • Seoul
        • …
      • Gyeonggi do
        • Suwon si
        • Yongin si
        • …
      • …

State Aware Treemaps

Idioms for Tree Data

GrouseFlocks

• Compound network: a network + tree
• Cluster hierarchy atop original network.
• Connection marks for original network, containment marks for cluster hierarchy.

Summary: Arrange Networks and Trees

• A node-link diagram uses connection marks.
  • Force-directed layout
  • Intuitive, topology understanding, unsearchable, no order, not scalable
• An adjacency matrix uses area marks in 2D matrix alignment.
  • Detailed Task, estimating # of nodes, searchable, better scalability, unfamiliar
• A Treemap uses area marks and containment with rectilinear layout.