最近邻图(NNG)最近邻图K最近邻图

Thenearest neighbor graph(NNG)近邻图 is adirected graphdefined for a set of points in ametric space, such as theEuclidean distanceinthe plane. The NNG has avertexfor each point, and adirected edgefromptoqwheneverqis a nearest neighbor ofp, a point whose distance frompis minimum among all the given points other thanpitself.^[1]

In many uses of these graphs, the directions of the edges are ignored and the NNG is defined instead as anundirected graph. However, the nearest neighbor relation is not asymmetric one, i.e.,pfrom the definition is not necessarily a nearest neighbor forq. In theoretical discussions of algorithms a kind ofgeneral positionis 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. For situations in which it is necessary to make the nearest neighbor for each object unique, the setPmay be indexed and in the case of a tie the object with, e.g., the largest index may be taken as the nearest neighbor.^[2]

Thek-nearest neighbor graph(k-NNG)k近邻图 is a graph in which two verticespandqare connected by an edge, if the distance betweenpandqis among thek-th smallest distances frompto other objects fromP. The NNG is a special case of thek-NNG, namely it is the 1-NNG.k-NNGs obey aseparator theorem: they can be partitioned into two subgraphs of at mostn(d+ 1)/(d+ 2)vertices each by the removal of O(k^1/dn^1−1/d) points.^[3]

Another variation is thefarthest neighbor graph(FNG), in which each point is connected by an edge to the farthest point from it, instead of the nearest point.

NNGs for points in the plane as well as in multidimensional spaces find applications, e.g., indata compression,motion planning, andfacilities location. Instatistical analysis, thenearest-neighbor chain algorithmbased on followingpathsin this graph can be used to findhierarchical clusteringsquickly. Nearest neighbor graphs are also a subject ofcomputational geometry.

k-近邻图(k-nearest neighbor graph)
选定参数k，对于顶点v_i,i=1,..,n，把离它最近的k个点与之相连，所得到的图就是k-近邻图。
需要注意的是，因为这样的邻近关系并不是对称的(v_j是v_i的k近邻 ≠v_i是v_j的k近邻)，故而得到的图将会是“有向”的。为了得到无向的图（图的赋权邻接矩阵W应是对称的），一般采取的办法有两种：
(1)忽视边的方向。即只要v_j是v_i的k近邻，或者v_i是v_j的k近邻，就用一条无向边把v_i与v_j连接起来。通常称的k-近邻图就是这一种。
(2)仅当v_j是v_i的k近邻，且vi是vj的k近邻时，才把vi与vj连接起来。这样得到的图称为混合k-近邻图(mutual k-nearest neighbor graph)

Having simple dataset:

you create a graph from k-NN:

after partitioning the graph will be much simplified (having large kk at the begging might not have any influence at all, because most of the edges will be removed during partitioning).

REF

https://blog.csdn.net/qingdanry/article/details/44685411

https://en.wikipedia.org/wiki/Nearest_neighbor_graph

https://stats.stackexchange.com/questions/165047/how-are-graphs-of-k-nearest-neighbors-built-for-clustering