Similarity-based network formation

We consider the problem of similarity-based network formation. That is, we are given a set of nodes where each node is characterized by a feature vector (point) in a metric space. The goal of each node is to identify all other nodes that are similar to them, i.e. whose feature vector is close to their own feature vector with respect to the metric distance. The challenge of the problem is that node can not directly observe the the distance of their own feature vector to the feature vector of other nodes, but can obtain only noisy estimates (observations) of the actual distance. The fundamental question that we study is whether it is possible for nodes to overcome this observation noise and be able to perfectly identify all the nodes that are within a given distance from their own feature vector. For this problem, we present recent result that we obtained for well-known latent-space and planted partition models. This network formation problem has applications in online social networks where users want to connect to other users who have similar interests, as well as in peer-to-peer networks where nodes want to connect to other nodes that have similar content in order to minimize the content search time and overhead. We provide an overview of recent results that have been obtained for the two cases of the well-known planted partition and latent space models. A main result of this existing work is that there exists a simple, distributed algorithm that is able to achieve "perfect network formation" for both the planted partition model, as well as a one-dimensional latent space model. The extension of this result to more general (e.g. n-dimensional metric spaces) is an open problem.