anything above, please install Java
A walker walks
a source to a target node and uses a specified amount of information at
every node to find the correct exit link. The walker takes the shortest
path if the available information is sufficient. The amount of
available information at every node, counted in bits, can be adjusted
by the scroll bar in the lower right corner.
The source and the target can be changed. Push the
mouse button on
a node without releasing the button and move the mouse to another node
and release the button. The node where the button was pushed is the new
source and the node where the button was released is the new target
The environment of the walk can be changed by clicking on one of the
network buttons. The random Erdos-Rényi networks have average
degree 4 and the scale-free networks have a power law with
exponent 2.2 to mimic real-world networks.
The right panel also
gives information about the total amount of
information used to go from the source to the target together with the
number of walked steps and the shortest path length. The total
information and the number of walked steps are averaged over all walks
between the two points.
easier catch the
distance field in the network, nodes close to the
target are painted bigger than remote nodes.
speed button sets
anti-aliasing of the image on and off.
is a challenging problem for everyday life. The problem arises because
the amount of available information typically is limited and often
insufficient. We here abstract this problem to be navigation between a
source and a target on different networks. The scenario is the
following: You are standing on a node, say s in a) in the figure above and want to
go to node t. By using 2 bits
of information at s you can
find the best exit among the 4 possible (the link in north-west
direction because on the next step only one question is enough). But by
using 1.2 bits of information (as indicated in
the figure) you can exclude the
to links downwards and choose the links upwards with probabilities
according to the color of the links. This is actually the optimal way
if the goal is to reach t with
as little information as possible. You loose a few questions when you
take the link in north-east direction, but the risk is only 1/4 and on
average it is a better choice because you save 0.8 bits of information
at s. With this strategy the
total amount of information to go from s
to t will be 2.6 bits and the
length 2 steps.
In b) the amount of available
information is limited to 0.2 bits of information at every node. In
this case you can not exclude the wrong exit links from s if you want to take the shortest
path to t. The chance to take
a link from a node is indicated by the color of the link. In this
scenario with limited information you on average only use 0.7 bits of
information to go from s to t, but you have to pay by walking
longer, on average 4.5 steps compared to 2 steps in a).