Navigation in Hypertext

The Converted Distance Matrix

The structural analysis of hyperdocuments is based on the distance matrix. The figure below shows a graph and its associated distance matrix. The numbers represent the minimum number of steps (links) that are needed to get from the source node to the destination node. If a node cannot be reached from another node their distance is infinite.

To formalize notions like "centrality" (how central is a node in the hyperdocument), we wish to take the sum of the distances from a node to all other nodes. However, in the matrix of the example the sum would always be infinite. To get meaningful sums we replace infinity by a reasonably large number K, which we call the conversion constant. The result is a converted distance matrix. The higher K the more important the fact becomes that a node is not reachable from another node. For identifying hierarchies a large K improves the choice of a "good" root node, while for calculating metrics the influence of K should be reduced, so a smaller K is better. A generally usable choice of K is the number of nodes. Any finite distance is always smaller than the number of nodes in a hyperdocument.

Source: De Bra.

Last modified: 6 Nov 2002 by Kathy Nguyen Dang