|
Instructions
If you don't see anything above, please install Java 1.4. A walker walks from 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 node. 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. To easier catch the distance field in the network, nodes close to the target are painted bigger than remote nodes. The speed button sets anti-aliasing of the image on and off. More applets |
Philosophy
 Navigation 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). |
