Graph data visualization
2
What is graph data
• Data representing relationships between entities
• Entities are represented by nodes (vertices or points)
• Relationships are represented by edges (lines or arcs)
• The graph G(V,E) includes the set of vertices V and the set of
edges E
TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
School of Information and Communication Technology
4
Properties of Graph Data
• Sparsity
• Not all nodes are connected by edges
• Number of edges is often much less than the number of
possible connections between nodes
• Directionality
• Directed edges: Show a one-way relationship between
nodes (e.g., following on Twitter)
• Undirected edges: Show a two-way relationship
between nodes (e.g., friendship on Facebook)
• Weights
• Weights represent the strength or importance of the
relationship between nodes
• Can be numerical values, distances, times, or other
quantities
TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
School of Information and Communication Technology
6
Basic concepts
• An independent set, stable set, coclique or anticlique is a set of
vertices in a graph, no two of which are adjacent.
• Clique is a subset of vertices of an undirected graph such that
every two distinct vertices in the clique are adjacent.
• A graph is said to be connected if every pair of vertices in the
graph is connected.
• A tree is an undirected graph in which any two vertices are
connected by exactly one path, or equivalently a connected acyclic
undirected graph.
TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
School of Information and Communication Technology
Basic concepts
• An articulation point (or cut vertex) (Điểm khớp) is defined as a
vertex which, when removed along with associated edges, makes
the graph disconnected
• A biconnected graph (đồ thị nối đôi) is a connected and
"nonseparable" graph, meaning that if any one vertex were to be
removed, the graph will remain connected.
• A biconnected graph has no articulation vertices.
• A bipartite graph (or bigraph) (đồ thị hai phần) is a graph whose
vertices can be divided into two disjoint and independent sets U
and V such that every edge connects a vertex in U to one in V
TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
School of Information and Communication Technology
Basic concepts
• Degree (bậc) of a vectex
• deg(n) is the number of edges that are incident to
the vertex
• Graph diameter (đường kính)
• diam(G) is the greatest distance (shortest parh)
between any pair of vertices
TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
School of Information and Communication Technology
Graph visualization
TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
School of Information and Communication Technology
Explicit graph visualization (node-link)
TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
School of Information and Communication Technology
Criteria for node-link representation
• Minimizing the intersection edges
• Minimize the distance between the vertices
• Minimize drawing area
• Edges of similar length
• Maximum angle between different edges
• Symmetry (graphs with the same structure must look
the same)
TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
School of Information and Communication Technology
Force-directed graph
• The forces are applied to the nodes, pulling them closer together
or pushing them further apart.
• This is repeated iteratively until the system comes to a mechanical
equilibrium state
https://observablehq.com/@d3/force-directed-graph
TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
School of Information and Communication Technology
Multi-level technique
• Reduce the magnitude of a graph by merging
vertices together, compute a partition on this
reduced graph, and finally project this partition
on the original graph.
TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
School of Information and Communication Technology
Sampling
• Large graphs can overwhelm visualization tools and viewers.
• Sampling allows us to explore a manageable subset of the data.
• Different sampling techniques highlight various aspects of the
graph.
• Key sampling techniques
• Random Sampling
• Degree-Based Sampling
• Ego-Network Sampling
• Community Sampling
TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
School of Information and Communication Technology
Collapse/Expand
• Particularly useful for hierarchical graphs, where sub-
trees can be collapsed or expanded as needed.
• Clarity: Reduces visual clutter, making it easier to focus
on specific areas of interest.
• Scalability: Handles large datasets efficiently by
allowing parts of the graph to be hidden.
http://bl.ocks.org/mbostock/1062288
TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
School of Information and Communication Technology
Fixed arrangement for graphs
• Circos Layout
• Compact Visualization: Efficiently uses space to show large,
complex datasets.
• Pattern Recognition: Facilitates the identification of clusters,
patterns, and relationships.
• Aesthetic Appeal: Attractive and engaging, enhancing the visual
storytelling of data.
TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
School of Information and Communication Technology
Fixed arrangement for graphs
TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
School of Information and Communication Technology
Fixed arrangement for graphs
• Edge bundling
https://observablehq.com/@d3/hierarchical-edge-bundling
TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
School of Information and Communication Technology
Tree layout
TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
School of Information and Communication Technology
https://observablehq.com/@d3/tree
Tree layout
http://bl.ocks.org/mbostock/4339083
TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
School of Information and Communication Technology
Adjacency matrix
TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
School of Information and Communication Technology
Adjacency matrix
TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
School of Information and Communication Technology
Adjacency matrix
• Advantage
• Can represent most graphs (except hypergraphs)
• Focus on edges instead of vertices
• No need to care about layout
• Disadvantage
• Difficult to detect relationships such as paths,
cycles, etc.
TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
School of Information and Communication Technology
Hybrid layout
TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
School of Information and Communication Technology
Implicit presentation
• A treemap chart is a visualization that displays hierarchical data
using nested rectangles.
• Structure
• The entire chart area represents the root of the hierarchy.
• Each rectangle (or cell) represents a branch or leaf node.
• Rectangles are sized and ordered by a quantitative variable.
• Colors can be used to represent different categories or to encode additional
data dimensions.
TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
School of Information and Communication Technology
http://www.nytimes.com/packages/html/ne
wsgraphics/2011/0119-budget/
TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
School of Information and Communication Technology
27
Implicit presentation
• A sunburst chart is a radial visualization that represents
hierarchical data using concentric circles.
• Structure
• The center circle represents the root of the hierarchy.
• Each subsequent ring represents a level in the hierarchy.
• Slices are divided into segments representing subcategories.
• Interactive Exploration: Often allows users to zoom in on segments
for detailed views.
TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
School of Information and Communication Technology
https://observablehq.com/@d3/sunburst
https://observablehq.com/@d3/zoomable-sunburst
• https://observablehq.com/@3cd7d5ec89dc7f6
8/graph-visualization-introduction
TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
School of Information and Communication Technology
29
30
