In this paper we consider the classical network formation problem where nodes want to connect to other nodes that have similar “interests”. This problem is of fundamental importance in the network formation of peer-to-peer networks and online social networks. For this problem, we study whether there exists an algorithm that is robust with respect to the underlying interest graph that models the similarity of nodes in the networks. With robust, we mean that the algorithm is simple and achieves high-performance for a variety of interest graph models. The concrete interest graph models that we consider are the widely used planted partition and latent space model. We propose a network formation mechanism based on a cosine-neighbourhood refinement step and formally show that it performs well for the planted partition model. In addition, it can be shown that this mechanism based on cosine-neighbourhood refinement step also performs well under a latent space model for a one-dimensional sphere. To the best of our knowledge, this is the first time that a network formation mechanism has been shown to be robust and perform well for both the planted partition and latent space model. The proposed algorithm is simple and can be implemented in a distributed or centralized manner.

A fundamental challenge in peer-to-peer and online social networks is the design of a simple, distributed algorithm that allows users to discover, and connect to, peers who closely match their interests or preferences. In this paper, we consider an algorithm that is based on simple, local comparisons, and analyze it to provide insights into why similar peer discovery algorithms work well in practice. To do so, we use a mathematical framework to characterize the closeness of individual interests, and formally introduce the notion of a “perfect network formation” under the framework. Our analysis shows that the proposed algorithm indeeds achieves perfect network formation. Our analysis uses bounding techniques based on Chernoff bounds.