  Over the years, quantifying the similarity of nodes has been a hot topic in
complex networks, yet little has been known about the distributions of
node-similarity. In this paper, we consider a typical measure of
node-similarity called the common neighbor based similarity (CNS). By means of
the generating function, we propose a general framework for calculating the CNS
distributions of node sets in various complex networks. In particular, we show
that for the Erd\"{o}s-R\'{e}nyi (ER) random network, the CNS distribution of
node sets of any particular size obeys the Poisson law. We also connect the
node-similarity distribution to the link prediction problem. We found that the
performance of link prediction depends solely on the CNS distributions of the
connected and unconnected node pairs in the network. Furthermore, we derive
theoretical solutions of two key evaluation metrics in link prediction: i)
precision and ii) area under the receiver operating characteristic curve (AUC).
We show that for any link prediction method, if the similarity distributions of
the connected and unconnected node pairs are identical, the AUC will be $0.5$.
The theoretical solutions are elegant alternatives of the traditional
experimental evaluation methods with nevertheless much lower computational
cost.
