Nearest neighbor graph | 近邻图

最近在开发一套自己的单细胞分析方法，所以copy paste事业有所停顿。

实例：

R eNetIt v0.1-1

data(ralu.site)
  

# Saturated spatial graph
 sat.graph <- knn.graph(ralu.site, row.names=ralu.site@data[,"SiteName"])
  head(sat.graph@data)
 
 # Distanced constrained spatial graph
 dist.graph <- knn.graph(ralu.site, row.names=ralu.site@data[,"SiteName"], max.dist = 5000)

 par(mfrow=c(1,2))	
plot(sat.graph, col="grey")
  points(ralu.site, col="red", pch=20, cex=1.5)
     box()
     title("Saturated graph")	
plot(dist.graph, col="grey")
  points(ralu.site, col="red", pch=20, cex=1.5)
     box()
     title("Distance constrained graph")
  

一下来自wiki

The nearest neighbor graph (NNG) for a set of n objects P in a metric space (e.g., for a set of points in the plane with Euclidean distance) is a directed graph with P being its vertex set and with a directed edge from p to q whenever q is a nearest neighbor of p (i.e., the distance from p to q is no larger than from p to any other object from P).^[1]

NNG图，在多维空间里我有很多个点，如上例，在17维空间里，我有31个点，一个常见的距离度量就是欧氏距离，NNG是有方向的，因为q是p的邻居并不代表p是q的邻居！

In many discussions, the directions of the edges are ignored and the NNG is defined as an ordinary (undirected) graph. However, the nearest neighbor relation is not a symmetric one, i.e., p from the definition is not necessarily a nearest neighbor for q.

In some discussions, in order to make the nearest neighbor for each object unique, the set P is indexed and in the case of a tie the object with, e.g., the largest index is taken for the nearest neighbor.^[2]

The k-nearest neighbor graph (k-NNG) is a graph in which two vertices p and q are connected by an edge. if the distance between p and q is among the k-th smallest distances from p to other objects from P. The NNG is a special case of the k-NNG, namely, it is the 1-NNG. k-NNGs obey a separator theorem: they can be partitioned into two subgraphs of at most n(d + 1)/(d + 2) vertices each by the removal of O(k^1/dn^1 − 1/d) points.^[3]

在k-NNG里，就不是最近邻了，而是考虑k-th，就是把k-th内的点都当做邻居。

Another special case is the (n − 1)-NNG. This graph is called the farthest neighbor graph (FNG).

如果k=n-1，那么就是FNG图。

In theoretical discussions of algorithms a kind of general position is often assumed, namely, the nearest (k-nearest) neighbor is unique for each object. In implementations of the algorithms it is necessary to bear in mind that this is not always the case.

NNGs for points in the plane as well as in multidimensional spaces find applications, e.g., in data compression, motion planning, and facilities location. In statistical analysis, the nearest-neighbor chain algorithm based on following paths in this graph can be used to find hierarchical clusterings quickly. Nearest neighbor graphs are also a subject of computational geometry.