KONECT
KONECT > Plots > Hop plot

Hop plot

The hop plot is a visualization of the distribution of pairwise distances in a network. The distance between two nodes in a network is defined as the number of edges in the shortest path connecting the two nodes. Let a network have n vertices. Then there are n² node pairs, each a specific distance from each other. The hop plot shows, for each possible distance d, the number of node pairs at a distance d from each other. The X axis thus shows distance values starting at zero (the minimal distance only reached by node pairs of the form (i, i)) up to the diameter of the network. The Y axis shows the number of node pairs at a distance at most d from each other, divided by the total number of node pairs, i.e. n². Pairs of the form (i, i) are included, and the pairs (i, j) and (j, i) are counted separately. Only the largest connected component is considered. In directed networks, the direction of edges is ignored.

An alternative interpretation of the hop plot is as the fill of the matrix I + A + A2 + … + Ad for each number d.

The hop plots also show the mean distance, median distance and 90-percentile effective diameter of the network. The mean distance is computed over all n² node pairs, and is indicated with a dashed green line. The median distance is also computed over all n² node pairs, and is given by the intersection of the hop plot with the 50% horizontal line. To find that intersection, the points of the hop plot are connected by line segments. The 90-percentile effective diameter is given analogously as the intersection of the hop plot with the 90% line. In fact, the median distance is also the 50-percent effective diameter. Both the median distance and the 90-percentile effective diameter are shown as continuous red lines. The diameter of the network can be read off the plot as the X-axis coordinate of the righmost point on the hop plot.