An analysis of the number of message receivers in highly clustered peer-to-peer networks

This paper presents a method to calculate the number of newly visited nodes at each step of a query spreading process, which is closely related to various types of performance such as search success rate and search time. Our method is based on the analytical framework proposed by Gaeta et al. Since the existing framework is based on the assumption that the probability of encountering the same node in the query spreading process after multiple hops is negligible, it is not suitable for relatively small networks or highly clustered networks. In this paper, we propose a method to make the analytical framework applicable to those networks by considering the possibility that a node receives the same query from different nodes.