Graphics Reference
In-Depth Information
Figure 4-2:
The two graphs shown here each have five nodes and five
edges. The left graph has a diameter of 2. The graph on the right has a
diameter of 3 (for example, from A to D).
In business applications, paths are interesting when there is a sequence
being analyzed, such as paths through a website, or a
customer journey
to
purchase a new vehicle. The goal of the analysis may be to minimize the
number of steps in the path, reduce the number of abandoned shopping
carts, or make each step in the journey a positive experience.
Referring back to the Kevin Bacon game, the target of the game is to find
the shortest path (in less than six steps) to Kevin Bacon. The game could be
more accurately renamed to “Shortest Path to Kevin Bacon.” The reference
to six degrees is a reference to earlier social network theory that everyone in
the world is only six steps away from any other person in the world. When
talking about graphs, the term
distance
is used to measure lengths of paths
whereas the term
degree
(discussed next) is a property of a node.
Degree
Node degree
is the number of edges connecting to a given node. A node
with degree zero is a node with no edges—it is an isolated node. A node with
degree one has only a single edge and is often called a
leaf node
.
When considering the entire graph, the
average degree
is simply an
average of the degree of all nodes. When the average degree is higher, each
node has high connectivity, the graph is densely connected with a large
number of edges, and dense graphs tend to become more difficult to lay out
nicely (for example, there will often be many more crossing lines).
