Go to Google Home
Go
A data-code-compute resource for research and education in information visualization
InfoVis Home Learning Modules Software Databases Compute Resources References

Software > k Random-Walk Search Algorithm

Description | Pros and Cons | Applications | Details | Usage Hints | References | Acknowledgments

line
Description

Search in a graph is defined as finding a path from a start node to a destination node. The cost of a search is the number of edges traversed in locating the destination node (i.e. the number of "messages" sent in the network during the search process).

Random walk on a graph is a well known uninformed search technique [1,2]. In this approach, a reduction in message overhead is attempted by having a single message routed through the network at random. Search proceeds from the start node by randomly selecting one of its neighbors N. Then node N further selects one of its neighbors, avoiding re-selecting the node, the search message came from. This process continues until the desination node is found.

This search mechanism does not generate as much message traffic as the Breadth-First-Search (BFS) algorithms since there is only one message being routed through the network graph. The trade-off is that the search response time is significantly longer. k-random walk extends this process to k random walkers that operate simultaneously with the goal of reducing user-perceived response time.

line
Pros & Cons

Applicable to network graphs only. k-Random Walk Search Algorithm can be used to perform search on any of the structured (e.g. CAN, Chord), unstructured (e.g. PRU, Hypergrid) or random network models.


line
Applications

This algorithm can be used to perform search on any network graph (structured or unstructured). The search cost can be useful in comparing search performance among structured and unstructured P2P networks and also across different toplogies.


line
Details

Pseudo Code of the algorithm is as follows:

define kRandomWalk(Graph g, int numWalkers, Node startNode, Node destinationNode)
     Node n := startNode
     while( n not equals destinationNode)
          for walker (1...numWalkers)
               int count := numNeighbors(g, n)
               if (count > 1)
                    int randomNumber := rand(count)
                    Node prev = n
                    n := getNeighbor(g,n,randomNumber)
               else
                     n = prev

line
Usage Hints

In the IVC Software Framework, simply select a network data model and use Analysis > Search > k Random-Walk Search to analyze it.


line
References

line
Acknowledgments

This package was developed by George Fletcher and Hardik Sheth. Hardik Sheth integrated the code into the IVC Software Framework.

line
Information Visualization Cyberinfrastructure @ SLIS, Indiana University
Last Modified July 10th, 2004