Uygulamalı Çizge Kuramı - I

Yaklaşık bir haftadır Nesin Matematik Köyü'nde çeşitli derslere katılıyorum. Bu yıl, geçmiş yıllardan farklı olarak MK'da fizikçiler için açılan dersler sebebiyle buradayım aslında ama bir hafta öncesinde gelip özellikle 'Uygulamalı Çizgeler Kuramı' ve 'Diferansiyel Denklemler' derslerini dinlemek istedim. Köydeki ilk haftamın ardından, ilk derslerden aklımda kalanları dokümante etmek ve ileride göz atmak adına düzgün notlar hazırlamak için gün gün derslerin kısa özetlerini yazmayı düşündüm.


Her ne kadar 'Matematik' Köyü'nde olsak da İTÜ Fizik Mühendisliği Bölümü'nden yakın zamanda emekli olan Ayşe Erzan'ın verdiği 'Uygulamalı Çizge Kuramı' dersi, tipik matematiksel notasyondan ve teorem-kanıt akışından farklı olarak, belki de tam anlamıyla 'uygulamalı' bir şekilde, daha çok istatistiksel fizik perspektifinde bir dersti. Dolayısıyla ben de tanımlarım ve hesaplamalarımda benzer yaklaşımı izlemeye çalışacağım. İlk günkü notlarla başlayalım o halde.

Bir çizgeyi (graf ya da ağ'ı) en basit şekliyle belirli ya da sonsuz sayıda düğümler (node) ve bunları ikili şekilde birbirine bağlayan kenarların (edge) bütünü olarak tanımlayabiliriz. Bu köşeler genelde her birine bir isim verilip $V$ kümesi ile ve bunların birbiriyle bağlantılarını ifade eden kenarlar ikililerden oluşan $E$ kümesi ile gösterilirler. Fakat bizim işimiz doğrudan bu kümelerin içindeki bir takım 'matematiksel' ilişkilerin ötesinde, ilerde daha iyi anlaşılacak olan bu yapıların daha çok global özelliklerini anlamak olduğundan bu tip bir formal tanımlamalar üzerinde çok durmayacağız. Üzerinde çalışacağımız çizgeler yönsüz çizgeler olacak; düğümler arasındaki kenarlar herhangi bir yönlü ilişki belirtmiyor olacaklar.

Bir çizgenin karakterini belirleyen çok temel birkaç parametre bulunuyor. Bunlardan ilki düğüm sayısı $N$. Sonlu bir çizgede düğümleri 1'den $N$'ye kadar etiketleyebiliriz ($i = 1,2, ... N$). Diğer önemli parametre ise verili bir düğüme(düğümleri $i$ ile etiketleyelim) bağlı kenar sayısı, yani o düğümün derecesi $d_i$. Yukarıdaki çizgede her bir düğümün derecesini şu şekilde yazabiliriz:

$d(1) = 2$, $d(2) = 3$
$d(3) = 3$, $d(4) = 2$



Bunlardan yola çıkarak tanımlayabileceğimiz bir başka büyüklük, $d$ dereceye sahip ortalama nod sayısı, ki bunu  $p(d)$ ile gösterelim: $p(d) = \frac{N(d)}{N}$; hatırlayalım $N$ toplam düğüm sayısı ve $N(d)$ ise $d $ dereceye sahip düğüm sayısı. Bu değerin $N$ sonsuza giderken $d$ derecesine sahip düğümlerin olasılığına eşit olacağını söyleyebiliriz: $$ p(d) = \lim_{d \to \infty} \frac{N(d)}{N} $$ Böylece, çizgeler üzerinde tanımlayacağımız çeşitli özelliklerin istatistiksel hesaplarında (örneğin ortalama, standart sapma ve çok daha fazlası) kullanabileceğimiz bir olasılık tanımı geliştirmiş bulunuyoruz. Bunu 'derece dağılımı' olarak adlandırırsak, bir çizgenin derece dağılımı bilgisi üzerinden çizgeye dair epey işe yarar şey hesaplamak mümkün. İlk olarak elimizdeki sonsuz sayıda (ya da çok çok fazla) düğüme sahip bir çizgedeki derece dağılımını elde etmeye çalışacağız. Bunun için de 'rasgele çizgeler' olarak tanımlanan iki tip çizgeyi Gilbert çizgesi (bu yazıda) ve Erdös-Renyi çizgesini (ikinci yazıda) inceleyeceğiz.

Gilbert çizgesi:

$G_{N,P}$ olarak gösterilen bu çizge iki parametre ile tanımlanabiliyor: toplam düğüm sayısı $N$ ve bir düğümün diğerine bağlanma olasılığını veren $p$. Sözle ifade edersek; N tane düğümümüzü yerleştiriyoruz ve bunlardan seçtiğimiz tüm ikililer için bunları birbirine bağlayıp bağlamayacağımızı kendimize soruyoruz. $p$ olasılıkla bağlıyoruz, $1-p$ olasılıkla bağlamıyoruz (dolayısıyla yalnız iki seçeneğimiz var ve ikisinin olasılıkları toplamı $p +(1-p) = 1$). Problemi formüle ederken fark edileceği üzere iki durumumuz var ve $N$ tane düğüm arasından seçim yapıyoruz. Rastgele bir şekilde oluşturduğumuz bir çizgede bir düğüme, kalan $N-1$ tane düğümden $d$ tane kenar bağlanma olasılığını binom dağılımı ile karakterize edebiliriz: $$p(d) = \binom{N-1}{d}p^d(1-p)^{N-1-d}$$ $$\sum_{d=0}^{N-1} p(d) = 1$$
Şimdi bu dağılım üzerinde bir takım yaklaşımlar uygulayıp, dağılımın belirli limitlerde nasıl davranacağına bakacağız.

Öncelikle çok büyük N düğüm sayıları için $N-1  \sim  N$ diyebiliriz. Yukarıdaki dağılımın çok küçük bağlanma olasılığı ($p <<1$) için nasıl davrandığına baktığımızda aşağıdaki adımlarla ilerliyoruz:
$$ P(d) = \frac{N!}{d!(N-d)!}p^d(1-p)^{N-1-d} $$ $$  P(d) = \frac{N(N-1)...(N-d+1)}{d!}p^d[1-(N-d)p]$$
$p<<1$ için $(1-p)^{N-1-d} \sim 1-(N-d)p$ diyebiliriz. $N$'nin çok büyük olmasını tekrar kullanıp gönül rahatlığıyla $1-(N-d)p \sim 1-Np $ yazabiliriz. Ayrıca $p$'nin çok çok küçük olmasından yola çıkarak $1- (Np)$ ifadesini de $e^{-Np}$ olarak gösterebiliriz. Son yapacağımız yaklaşıklık ise $N(N-1)...(N-d+1) \sim N^d$ olacak(her bir parantezden bir $N$ çarpanı dışarı çıkarıyoruz). Sonuçta şöyle bir ifade ile karşılaşıyoruz $$ p(d) = \frac{N^dp^d}{d!}e^{-Np}$$ Elde ettiğimiz dağılım meşhur Poisson dağılımı. Yani çok sayıda düğüme sahip, bağlanma olasılığı oldukça düşük rastgele bir çizgede, seçtiğimiz herhangi bir düğümün $d$ derecesine sahip olma olasılığı Poisson dağılımı ile ifade ediliyor. Poisson dağılımı tek bir parametre ile karakterize edilebilen, özellikle fizikte birçok durumda karşımıza çıkan bir dağılım. Bahsi geçen parametre, yukarıda da muhtemelen gözünüze çarpan $Np$ parametresi. Bu parametreyi $\lambda$ ile isimlendirirsek, dağılımın son halini şu şekilde yazabiliriz: $$p(d) = \frac{\lambda^d}{d!}e^{-\lambda}$$ Bu dağılım altında çizgemizdeki ortalama derece sayısını hesapladığımızda:$$\langle d \rangle = \sum_{d=0}^{N-1} P(d)d = \lambda$$ olduğu kolaylıkla görülebilir. Aynı şekilde derece dağılımının standart sapmasını hesapladığımızda ($\sigma_d^2  = \langle d^2 \rangle-\langle d \rangle^2$ ifadesinden yararlanıp) bunun da ortalama değere yani $\lambda$'ya eşit olduğunu görebiliriz. Bunun anlamı, küçük $\lambda$ değerleri yani ortalama değerler için dağılımımız oldukça dar ve ortalama etrafında çok saçılmamış; fakat büyük ortalama değerler için varyansın da aynı şekilde büyüyerek gittikçe daha geniş ve çokça saçılmış bir dağılıma benzediğini gözlüyoruz.

Uzun lafın kısası, sadece $N$ ve $p$ ile karakterize edilen Gilbert çizgemizin çok büyük $N$ düğüm sayıları için, düğüm derecelerinin Poisson şekilde dağıldığını bulmuş olduk. Buradan yola çıkarak da ortalama düğüm derecesinin ve bunun varyansının Poisson dağılımındaki parametre olan $\lambda = Np$ olduğunu göstermiş olduk.

Bir sonraki bölümde, bir diğer rastgele çizge tipi ola Erdös-Renyi çizgesini ele alıp, benzer hesaplamaları onun için de yapıp bunların eş değer olduğunu göstereceğiz. Ayrıca Poisson dağılım gösteren çizgelere alternatif olarak kuvvet yasası gereğince dağılım gösteren çizge tiplerini inceleyeceğiz.