Node cluster-based random walk search in peer-to-peer network

In order to simplify the complex structure of unstructured peer-to-peer (P2P) networks such as Gnutella, a node cluster-based random walk search algorithm is proposed. In this algorithm, node clusters are used to store file indices, and the search process is constrained in node clusters to improve the search performance. Afterwards, the upper and lower bounds of search performance are formulated based on the theoretical analysis of the mathematical model. Experimental results indicate that the search performance of the proposed algorithm is closely related to the cluster threshold c, and that, at the suggested value of c, namely half of the maximum degree in the system, the success rate of searching rare files increases by at least 250% and the transfer and storage cost decreases by one order of magnitude, as compared with the common random walk algorithm. The proposed algorithm is of the advantages of low storage cost high search efficiency as well as ease realization and deployment.