On the reciprocity of proximity relations

The degree of reciprocity of a proximity order is the proportion, P(1), of elements for which the closest neighbor relation is symmetric, and the R value of each element is its rank in the proximity order from its closest neighbor. Assuming a random sampling of points, we show that Euclidean n-spaces produce a very high degree of reciprocity, $\text{P(1) ≥}\text{1}\text{2}$, and correspondingly low R values, E(R) ≤ 2, for all n. The same bounds also apply to homogeneous graphs, in which the same number of edges meet at every node. Much less reciprocity and higher R values, however, can be attained in finite tree models and in the contrast model in which the “distance” between objects is a linear function of the numbers of their common and distinctive features.