Approach to Construct Cluster in Unstructured P2P Networks Based on Small-World Theory

Node clustering has wide-ranging applications in decentralized P2P networks such as P2P file sharing systems, mobile ad-hoc networks, P2P sensor networks, and so forth. This paper proposes an approach to construct clusters in unstructured P2P networks based on small-world theory. In contrast to centralized graph clustering algorithms, our scheme is completely decentralized and it only uses the knowledge of neighbor nodes instead of requiring a global knowledge of the network to be available. The P2P networks are dynamic and the nodes in P2P networks can entry and exit frequently. To cope with the typical dynamics of P2P networks, we provide mechanisms to allow new nodes to be incorporated into, appropriate existing clusters and to gracefully handle the departure of nodes in the clusters.