Graphics Reference
In-Depth Information
does it take to connect Arnold Schwarzenegger with Kevin Bacon?”) This
game is so popular that a number of websites exist to find the shortest path
between an actor and Kevin Bacon (for example,
http://oracleofbacon.org
).
The answer to previous question, by the way, is only two steps to connect
Schwarzenegger and Bacon (for example through Tom Arnold or John
Cleese).
Path
A
path
is a sequence of edges that connect a pair of vertices. The
distance
betweenanytwonodescanbethoughtofastheshortestpathbetweenapair
of nodes in the graph and is measured as the number of edges used to create
this route.
Average path length
is a property of the entire graph that indicates the
average number of edges across all the shortest paths for every possible pair
of nodes in a network. Intuitively speaking, it measures how many edges
must be travelled across to get from one place in the network to another.
The
diameter
of a graph is simply the largest of all the shortest paths
between each pair of nodes in the graph. Graph diameter can be an
interesting measure to get a sense of how spread out or how compact the
graph is. Different layouts can emphasize (for example, force-directed) or
hide (for example, chord) the sense of diameter. A layout that emphasizes
diameter will emphasize the outermost leaves, as well as make the center
more visually apparent.
Figure 4-2
shows an example.
