Software > Random Breadth First Search Algorithm
Description | Pros and Cons | Applications | Details | Usage Hints | References | Acknowledgments  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 Breadth First Search (BFS) is an uninformed search algorithm that has been proposed as an alternative to basic uninformed "flooding" [1, 2, 3]. It utilizes only local connectivity knowledge of the graph during search. Basic BFS begins at the source node by checking each neighbor if it is the destination node. If this fails, each of these neighbors check their neighbors and this continues until destination node is found. Random Random Breadth First Search improves upon basic BFS by reducing the number of messages passed during search. It randomly eliminates a fraction p of neighbors that are checked for each node. Search then proceeds from the start node checking only n neighboring nodes and proceeding forward. If at any time during the search a node N contacts a "dead-end" node (a leaf in the graph), the search process backtracks to N and continues.
| Pros & Cons |
Applicable to network graphs only. Random Breadth First 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.
| 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 topologies. It can also be used to study its performance against other widely-known search algorithms like Basic Breadth First Search (BFS), Depth First Search (DFS) or Random Walk [4].
| Details |
Pseudo Code of the algorithm is as follows:
define randomBFS(Graph g, float prob, Node startNode, Node destinationNode)
Node n := startNode
Queue q := {}
Stack s := {}
Enqueue(q, startNode)
visited[startNode] := true
while( n not equals destinationNode)
if (queue empty)
tempNode := pop(s)
Enqueue(tempNode)
for each node (g)
visited[node] := false
n := Dequeue(q)
if (n not equals destinationNode)
push(s, n)
for each neighbor of n
if (visited[neighbor] = false)
if ( prob < rand() )
visited[neighbor] := true
Enqueue(q, neighbor)
| Usage Hints |
In the IVC Software Framework, simply select a network data model and use Analysis > Search > Breadth First Search to analyze it.
| References |
-
Banaei-Kashani, Farnoush and Cyrus Shahabi. Criticality-based Analysis and Design of Unstructured Peer-to-Peer Networks as "Complex Systems. Proc. IEEE/ACM CCGRID'03, pp. 351-358, 2003.
-
Dimakapoulos, Vassilios V. and Evaggelia Pitoura. A Peer-to-Peer Approach to Resource Discovery in Multi-Agent Systems. 7th International Workshop CIA, pp. 62-77, 2003.
-
Kalogeraki, Vana, Dimitrios Gunopulos and D. Zeinalipour-Yazti. A Local Search Mechanism for Peer-to-Peer Networks. Proc. ACM CIKM'02, pp. 300-307, November 2002.
-
George H. L. Fletcher, Hardik A. Sheth and Katy Börner.Unstructured Peer-to-Peer Networks: Topological Properties and Search Performance. AP2PC 2004, July 2004, Springer LNCS, to appear.
| Acknowledgments |
This package was developed by George Fletcher and Hardik Sheth. Hardik Sheth integrated the code into the IVC Software Framework.
Information Visualization
Cyberinfrastructure @ SLIS,
Indiana University
Last Modified July 10th, 2004