Locating information with uncertainty in fully interconnected networks with applications to World Wide Web information retrieval

In this paper we examine the problem of searching for some information item in the nodes of a fully interconnected computer network, where each node c ontains information relevant to some topic as well as links to other networ k nodes that also contain information, not necessarily related to locally k ept information. These links are used to facilitate the Internet users and mobile software agents that try to locate specific pieces of information. H owever, the links do not necessarily point to nodes containing information of interest to the user or relevant to the aims of the mobile agent. Thus a n element of uncertainty is introduced. For example, when an Internet user or some search agent lands on a particular network node, they see a set of links that point to information that is, supposedly, relevant to the curren t search. Therefore, we can assume that a link points to relevant informati on with some unknown probability p that, in general, is. related to the num ber of nodes in the network (intuitively, as the network grows, this probab ility tends to zero since adding more nodes to the network renders some ext ant links less accurate or obsolete). Consequently, since there is uncertai nty as to whether the links contained in a node's Web page are correct or n ot, a search algorithm cannot rely on following the links systematically si nce it may end up spending too much time visiting nodes that contain irrele vant information. In this work, we will describe and analyze a search algor ithm that is only allowed to transfer a fixed amount of memory along commun ication links as it visits the network nodes. The algorithm is, however, al lowed to use one bit of memory at each node as an 'already visited' flag. I n this way the algorithm has its memory distributed to the network nodes, a voiding overloading the network links as it moves from node to node searchi ng for the information. We work. on fully interconnected networks for simpl icity reasons and, moreover, because according to some recent experimental evidence, such networks can be considered to be a good approximation of the current structure of the World Wide Web.