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.

Bu tez, rastgele k en yakın komşu (kEYK) yönlü çizgelerini temel alan niceliklerin asimptotik davranışlarının araştırılması üzerinedir. R^d'deki bir sonlu noktalar kümesinin kEYK yönlü çizgesi, her noktadan en yakın k komşusuna (yani, kümedeki ona en yakın k noktaya) oklar çizilmesiyle elde edilir. İlk olarak, verilmiş sabit bir yönlü çizgenin bir rastgele nokta sürecinden elde edilmiş kEYK yönlü çizgedeki kopyalarının sayısını çalışıyoruz. Homojen Poisson süreci ve düzgün nokta süreci sonucu oluşan nokta kümeleri üzerine tanımlı fonksiyonellerle ilgili asimptotik teoriyi kullanarak, alt yönlü çizge sayılarının asimptotik davranışları üzerine genel sonuçlar sağlıyoruz. Bu sonuçlardan çıkarım olarak, bir kEYK yönlü çizgesindeki sabit iç dereceye sahip noktaların sayısı, müşterek kEYK ikililerinin sayısı ve karşılıklı kEYK ikililerinin sayısı için asimptotik sonuçlar elde ediyoruz. Bazı özel koşullar altında, bu sayımların ortalama ve varyans değerlerini hesaplıyoruz ve aralarındaki stokastik bağımlılıkları inceliyoruz. kEYK tipi bağıntılar uzaysal veri analizinde yaygın olarak kullanılmaktadır (örneğin, ayrışma ve ortaşım motiflerini test etmek için). Birden fazla sınıftan oluşan bir veri kümesinde, bir sınıfın elemanları aynı sınıftaki elemanların yakınında bulunuyorsa uzaysal ayrışma; eğer bir sınıfın elemanları başka sınıflardaki elemanların yakınlarında ise uzaysal ortaşım meydana gelir. Bu tarz motifleri, veri noktalarının kEYK yönlü çizgesini kullanarak çalışıyoruz. Okları, iki uç noktalarının ait oldukları sınıflara göre kategorize edip, k en yakın komşu çapraz tablo (kEYKÇT) adında bir çapraz çizelge oluşturuyoruz. Bir kEYKÇT'deki girdilerin asimptotik dağılımını dört farklı rastgele model altında inceliyoruz. Bu dört rastgele modelin ikisinde veri noktaları bir etiketli nokta sürecinden elde edilirken diğer ikisinde ise, noktalar sabit kabul ediliyor ama noktaların sınıf etiketleri rastgele atanıyor. Baz alınan her bir model için, kEYKÇT'deki girdilerin beklenti, varyans ve kovaryans değerlerini tam veya asimptotik olarak hesaplıyoruz ve tablo girdilerinin ve bunlara bağlı karesel ifadelerin asimptotik dağılımlarını elde ediyoruz. Ayrıca, rastgele kEYK yönlü çizgelerinin eşdönüşüm-değişmez olduğunu gösteriyoruz ve eşdönüşüm-değişmez rastgele çizgelerin sınıflandırılmasını yönlü çizgelere uyarlıyoruz. Bu doğrultuda, rastgeleliğin yapının neresinde yer aldığına göre yeni rastgele yönlü çizge kümeleri tanımlıyoruz; şöyle ki, ok rastgele yönlü çizgeleri, köşe rastgele yönlü çizgeleri ve ok-köşe rastgele yönlü çizgeleri. İlaveten, bir rastgele çizgenin kenarlarına rastgele yön atayarak yön rastgele yönlü çizgelerini tanımlıyoruz. Bu dört rastgele yönlü çizge kümesinin arasındaki ilişkileri çalışıyoruz ve ek olarak, rastgele kEYK yönlü çizgelerinin bu sınıflandırmada nereye düştüğünü belirliyoruz.