Friday, May 12, 2017

Visualizing Network Traversal

As part of an experiment I was doing related to network traversal I started to trying to visualize coverage of a network by a single visitor traveling through the nodes. The idea was to set a gradient between two colors and as a node was visited more times it would slowly take on a change in color over the gradient. If the goal was to visit each node N times, then the visualization would indicate current progress as a 'heat map' of the network according to the number of visits to each node.

The outputs were interesting in that controlling the traversal policy would change the distribution of color over the image. This is perhaps obvious given the experimental construct but still provided an alternate mechanism for 'measuring' the accuracy of the traversal. For example, if the goal is to cover the network as evenly as possible during the traversal, the kurtosis of a distribution then becomes a measure of how close one is to this goal.

To demonstration this I set up an NxN grid network and ran three example traversals over that grid. I captured the 'heat map' when the median of all the visit values for the nodes was at half of the target visits. The results are below.

Random Choice Walk:
At any node, a visitor will choose to move up, down, left, or right by random selection.

Backpressure Walk:
Uses a notion of backpressure to control the traversal. At each node, a visitor checks for the the least visited neighboring node and travels there.

Not really a traversal, I just did it to see what it would look like. At each node, a visitor chooses a random node within the grid and jumps there directly.