K en yakın komşu yönlü çizgelerinin olasılıksal incelenmesi

This thesis is devoted to the investigation of the asymptotic behaviour of quantities based on random k nearest neighbor (kNN) digraphs. The kNN digraph of a finite point set in R^d is obtained by inserting arcs from each point to its k nearest neighbors (i.e., k closest members in the set). We first study the number of copies of a given fixed digraph in kNN digraph of the data from a random point process in R^d. Based on the asymptotic theory for functionals of point sets under homogeneous Poisson process and uniform binomial process, we provide a general result for the asymptotic behavior of the subdigraph counts; and as corollaries, we obtain asymptotic results for the number of vertices with fixed indegree, the number of shared kNN pairs and the number of reflexive kNNs in a kNN digraph. Under some special settings, we also derive the exact values of the means and variances of these quantities and examine stochastic dependence between them. kNN type relations are widely used in spatial data analysis e.g. for testing spatial patterns of segregation and association . In a data set consisting of multiple classes, spatial segregation occurs when members of a class tend to be found near members of the same class while spatial association occurs when members of a class tend to be found near members of the other class or classes. We study these patterns using kNN digraph of the data points. We construct a contingency table called k nearest neighbor contingency table (kNNCT) based on classifying the arcs with respect to the classes of their endpoints. We analyze asymptotic distribution of the cell counts in a kNNCT under four different random settings. For two of these random settings, data points are obtained from a marked point process whereas in the other two, points are assumed to be fixed but their class identities (or labels) are randomly assigned. For each underlying process, we derive exact or asymptotic values of the expectations, variances and covariances of the cell counts of the kNNCT and obtain asymptotic distribution of the cell counts and quadratic forms based on them. Moreover, we demonstrate that random kNN digraphs are isomorphism-invariant. We extend the classification of isomorphism-invariant random graphs to digraphs and along this line, we introduce new families of random digraphs according to where randomness resides in the structure, namely, arc random digraphs, vertex random digraphs and vertex-arc random digraphs. We introduce randomness in the direction of the edges of a random graph and obtain direction random digraphs as well. We study relations between these four random digraph families and also determine where random kNN digraphs fall according to this classification.