Stats and Layout - Graph Analysis and Visualization - page 102

of nodes are often good for visualizing, and many different layout
techniques will work well.
• Hierarchy —A density less than one hints that the graph could be a
hierarchy and/or has multiple components. A hierarchy (or tree ) is a
sparse graph with a density where the number of edges is one less than
the number of nodes for a single tree. If you have multiple separate
trees, the difference between the nodes and edges indicates the number
of trees.
Number of Components
A component is a completely disconnected subgraph from the rest of
the graph. The number of components is the number of these distinct
disconnected subgraphs. You can measure each component for size by
counting the number of nodes and edges within that component. A single
node with no connections is an isolated node .
When visualizing a graph with multiple components, use a layout that
clearly separates the different components. Edges that crisscross make it
more difficult to visually distinguish the different components, as shown in
Figure 4-1 .
Figure 4-1: Different components are easier to identify if they do not
overlap in the graph layout.
Degree and Paths
The famous graph game “Six Degrees of Kevin Bacon” is incorrectly named!
Forthoseunfamiliarwiththegame,arandomlynamedmovieactorislinked
to Kevin Bacon through other actors, where each pair of actors must have
co-starred in a movie together. The challenge is to connect the random actor
to Kevin Bacon in as few edges as possible (for example, “How many steps