5 Ağustos 2015 Çarşamba

Uygulamalı Çizge Kuramı - III

Üçüncü bölümde periyodik çizge yapılarından yola çıkarak farklı dallanma tiplerine sahip 'ağaçsı çizgeler' için karakteristik uzunluk ve yarıçap tanımı yapacağız. Ardından bu uzunluğun  düğüm sayısı ile logaritmik ilişkisi ile 'küçük dünya' fenomenini ortaya koyacağız.. Son olarak, ilk iki bölümde incelediğimiz rastgele ağ modellerinin aslında birer 'küçük dünya' olduklarını göstereceğiz.

İki boyutlu, düğümleri arası birim uzunlukta, her bir boyutu L uzunluğunda periyodik bir çizge (örneğin bir lattice-kafes) ele alalım. Öncelikle bu tip bir çizgede $N = L^2$ tane düğüm noktası olduğunu görüyoruz. Bu çizgedeki düğümler arasındaki uzaklıklara baktığımızda, arasında en uzun mesafe olan iki düğümün arasındaki uzaklığın en fazla $2L$ olduğunu, dolayısıyla bu çizge üzerinde karakteristik uzaklığın $\sim L$ ($L$ mertebesinde) olduğunu söyleyebiliyoruz. Benzer bir hesaplamayı gene düzgün, periyodik fakat üç boyutlu bir çizge üzerinde yaptığımızda düğüm sayısının $N^3$ ile fakat uzaklığın gene $\sim L$ ile gittiğini görüyoruz. Bunu genelleştirdiğimizde bu tip periyodik çizgelerdeki karakteristik uzaklığın şu şekilde olduğunu söyleyebiliriz: $$\bar{l} \sim N^{\frac{1}{d_E}}$$ $d_E$ çizgemizin Öklidyen boyutu olarak tanımlanıyor. İki boyut için $2$, üç boyut için $3$ vs vs...

Ağaçsı çizgeleri oluşturmak için ilk başta bir düğüm (kök) ile başlayarak, her bir iterasyonda (jenerasyonda) $b$ tane düğüm ekleyip bunu bir önceki köke bağlayarak çizgeyi büyütüyoruz. İlk noktayı $0.$ jenerasyon olarak tanımlarsak, ilk jenerasyonda $b$ tane, ikinci jenerasyonda $b^2$ tane yeni düğümümüz ve bağlantımız oluyor. $r$ tane jenerasyona sahip bu tip bir çizgedeki toplam düğüm sayısı: $$N = 1 + b + b^2 + b^3 + ... + b^r = \sum_{n=0}^r b^n = \frac{b^{r+1} - 1}{b-1} \sim b^r$$ $$ N \sim b^r$$

Ağaçsı çizgelere iki örnek; sağdaki $b = 2$ dallanma katsayısına sahip, soldakinin dallanma katsayısı her jenerasyonda farklı (2-3-4... diye gidiyor) 

Bizim peşinde olduğumuz büyüklük, bu tip bir çizgedeki karakteristik uzunluk, yani $\bar{l}$. Ağacın yapısını incelediğimizde birbiri arasında en uzun mesafeye sahip olan düğümlerin, ilk jenerasyonda birbirinden ayrılan dalların en ucundaki düğümler olduğunu; bunların arasındaki mesafenin de $l_{max} = 2r$ olduğunu görüyoruz. Dolayısıyla yukarıdaki düğüm sayısını veren ifadeden $r$'yi çekmek için: $$ \log{N} = r\log{b}$$ $$r = \frac{\log{N}}{\log{b}}$$ $$l_{max}= \frac{2\log{N}}{\log{b}}$$ $$\bar{l} \sim \frac{\log{N}}{\log{b}} \tag{1}$$ $(1)$ nolu ifadenin gösterdiği üzere karakteristik uzaklık ($\bar{l}$) düğüm sayısının logaritması ile gidiyor. Periyodik çizgeler için hesapladığımız $1/d_E$ üssünden de yavaş bir şekilde gidiyor kısacası. Bunun anlamı ise, bu tip ağaçsı çizgelerde düğüm sayısı çok büyüse de bir düğümden diğer herhangi bir düğüme ulaşmak için kat edilmesi gereken mesafe çok yavaş artıyor, dolayısıyla herkes birbirine oldukça 'yakın'. Bu tip yapıya sahip çizgelere 'küçük dünya' (small world) ağları adı veriliyor. Bunlara en güzel örnek olarak belki de Amerika'da 1950'lerde insanların sosyal ağları üzerine yapılan bir araştırmada, rastgele bir Amerikan vatandaşının önceden belirlenen bir kişiye, kendisi veya tanıdığı (ya da tanıdığının tanıdığı vs..) vasıtasıyla kaç adımda 'tanışıklık' üzerinden uzak olduğunu belirlemeye çalıştıkları çalışma verilebilir. Elde edilen verilere göre ortalama 5.2 kişide bahsi geçen kişiye ulaşabiliyorsunuz. Benzer 'küçük dünya' etkisini internet gibi diğer ölçeksiz ağlarda da gözlemek mümkün...

İkinci kısımda, Erdös-Renyi çizgelerinde $L$ uzunluğundaki döngülerin sayılarına bakarak, bu sayının düğüm sayısı $N$'den bağımsız olduğunu göstereceğiz. Böylece çok büyük düğüm sayısına sahip çizgelerde bu tip döngülerin epey nadir ve ihmal edilebilir oldukları sonucuna varacağız. Ardından ortalama dallanma sayını hesaplayıp (1) nolu ifadede yerine koyarak bu çizgelerin de birer 'küçük dünya' olduklarını göstereceğiz.

İlk olarak L uzunluğundaki ortalama döngü sayısını hesaplayalım. Böyle bir dögü için öncelikle $N$ tane düğümden birini seçelim, ardından geriye kalan $N-1$ tanesinden de $L-1$ tane seçip bunları toplam L tane bağlantı olacak şekilde bağlayalım. Her bir bağlama olasılığımızın $\langle q \rangle N$ olduğunu biliyoruz. Oluşacak her bir kenarı yönden bağımsız seçmek için  yarısını alıp, ilk baştaki seçimizi L farklı şekilde uygulayıp aynı çizgeyi elde edebileceğimizden bir de $1/L$ faktörü geliyor olacak. Kısacası formülümüz şu şekilde: $$ N_L = N \binom{N-1}{L-1} \frac{(L-1)!}{2} \Big( \frac{\langle q \rangle}{N} \Big)$$ $$ = \frac{N(N-1)(N-2)..(N-L+1)}{(L-1)!}\frac{(L-1)!}{2L}\Big( \frac{\langle q \rangle}{N} \Big)^L$$ Yine $N>>1$ ve $L \leq < N$ olmak üzere $$N_L \sim \frac{N^L}{2L}\frac{\langle q \rangle^L}{N^L} = \frac{\langle q \rangle^L}{2L} \tag{2}$$
(2)'de elde ettiğimiz $L$ uzunluğundaki ortalama döngülerin sayısının düğüm sayısı $N$'den bağımsız olduğunu bulduk.

İkinci olarak, ortalama dallanma katsayısı için bir değer bulmak amacıyla, ele aldığımız bir düğüme komşu bir düğümün $q$ tane kenara yani $q$ derecesine sahip olması olasılığına bakacağız. İlk bakışta bunun dağılımının da derece dağılımı ile aynı şekilde ($\langle q \rangle$) olacakmış gibi, görünse de, bahsi geçen olasılığı koşullu olasılık gibi düşündüğümüzde biraz daha farklı bir sonuç vereceğini göreceğiz. Bu olasılığı şu şekilde tanımlayalım: $P_a(q)$, seçilen bir düğüme komşu olan $a$ ile isimlendirdiğimiz düğümün $q$ tane düğüme sahip olma olasılığını göstersin: $$P_a(q) = \frac{qN(q)}{N \langle q \rangle} \tag{3}$$ (3) nolu ifadede paydaki değer $q$ derecesine sahip tüm düğüm sayısı ile düğümlerin çarpımı, paydadaki değer ise tüm düğüm sayısını veriyor. Bahsi geçen $a$ düğümünün ortalama düğüm derecesini hesaplamak için de: $$\langle q_a \rangle = \sum_q qP_a(q) = \frac{1}{\langle q \rangle}\sum_q q^2 \frac{N(q)}{N}$$ $$\langle q_a \rangle = \frac{\langle q^2 \rangle}{\langle q \rangle} = \frac{\langle q \rangle^2}{\langle q \rangle} +1 = \langle q \rangle +1$$ $$\langle q^2 \rangle = \langle q \rangle^2 + \langle q \rangle$$ $$\Rightarrow \bar{b} = \langle q_a \rangle -1 = \langle q \rangle$$

E-R çizgelerinin, büyük düğüm sayıları için, içinde çok nadir bulunan döngüleri nedeniyle topolojik olarak 'ağaçsı' olduklarını (2) ile göstermiştik. Dolayısıyla ağaçsı çizgelerdeki karakteristik uzunluğu veren ifadeyi (1) E-R çizgeleri için de uygulayabiliriz. Dolayısıyla: $$\bar{l} \sim \frac{\ln{N}}{\ln {b}} = \frac{\ln{N}}{ln{\langle q \rangle}}$$ Elde ettiğimiz bu sonuca göre E-R tipi bir rastgele çizgede düğüm sayıları arttıkça sadece logaritmik, yavaş bir artışın yanında; artan ortalama düğüm derecesi ile de azalan bir uzaklık söz konusu. Yani E-R çizgelerini de tıpkı ölçeksiz bir ağda olduğu gibi birer 'küçük dünya' olduklarını söyleyebiliriz.

Dördüncü bölümde, çizgeleri ifade etmek ve üzerinde bir takım şeyler hesaplamak için kullanılan bir takım matrisler tanımlayacağız. Bunlardan ilki komşuluk ve derece matrisi olacak, ardından bunları birleştirip çizge Laplasyenini oluşturup bu operatörün işlevini ve özdeğer spektrumunu çıkaracağız.

2 Ağustos 2015 Pazar

Uygulamalı Çizge Kuramı - II

Bir önceki yazıda rastgele çizgelere giriş yapıp Gilbert çizgesinden bahsetmiştik. Bu yazıda öncelikle Erdös-Renyi (E-R) çizgesi olarak bilinen çizgeyi gösterip bu çizgenin Gilbert modeli ile eşdeğer olduğunu göstereceğiz. Ardından kuvvet yasası şeklinde farklı bir olasılık dağılımına sahip başka tip çizgeler üzerine konuşup bu çizgeler üzerindeki derece dağılımlarını inceleyeceğiz.

Erdös-Renyi Çizgeleri

Kısaca E-R çizgesi olarak ifade edilen bu çizgede, Gilbert çizgesine benzer şekilde, $N$ tane düğüm sayımız var,  fakat bu sefer düğümlerin birbirine bağlanma olasılığı $p$ yerine, toplam kenar sayısı $E$ veriliyor. Dolayısıyla $E$ tane kenarı, $N$ tane düğüm arasında paylaştırıyoruz gibi düşünebiliriz. Bu şekilde düşündüğümüzde, verilen her $N$ ve $E$ sayıları için oluşturduğumuz her bir çizgenin, bu yolla oluşturulabilecek tüm çizge ailesinin bir üyesi olduğunu söyleyebiliriz (Bu kavram aslında istatistiksel fizikteki 'grand canonical ensemble'ın çizgeler üzerinde bir analogu ve sabit olan düğüm sayısı parçacık sayısına, kenar sayısı da kimyasal potansiyele denk geliyor).

Bu çizge üzerinde gene derece dağılımıyla ilişkili olarak ortalama derece sayısını hesaplayabiliriz. $d_i$ i. düğümün derecesi olmak üzere, şunları biliyoruz: $$\frac{1}{N} \sum_i d_i = \langle d \rangle $$ $$\sum_i^N d_i = 2E $$ $$\Rightarrow \langle d \rangle = \frac{2E}{N} \tag{1}$$ Düğüm sayıları toplamının $2E$ olmasının sebebi, her bir kenarın ucunda ikişer düğüm bulunuyor, dolayısıyla tüm dereceleri topladığımızda kenar sayısının iki katı kadar düğüm toplamış oluyoruz.

Bir E-R çizgesinde $N$ tane düğüm ile elde edebileceğimiz en fazla kenar sayısı bağlantısı: $$E_{max} = \frac{N(N-1)}{2} = \binom{N}{2}$$ Bu çizge üzerinde kenarlar için tanımlayacağımız $p$ olasılığı, mevcut (ortalama) kenar sayısı ve olabilecek tüm $E_{max}$ kenarı arasında şöyle bir ilişkiyi temsil ediyor: $$ \langle E \rangle = E_{max}p $$ Yukarıdaki $(1)$ nolu eşitliğe geri dönüp, $E$ yerine bu ifadeyi yazarsak:
$$\langle d \rangle = \frac{2 E_{max}p}{N} = \frac{2N(N-1)p}{2N} = Np \tag{2} $$ Sonda yapılan $$(N-1)p \sim Np$$ yaklaşımı bir önceki bölümdeki hesapta da karşılaşmıştık ($N>>1$). Dolayısıyla $(2)$'de gösterdiğimiz üzere: $$\langle d \rangle = Np $$ Bulduğumuz ifade, $G_{N,p}$ Gilbert çizgesinde elde ettiğimizin aynısı! Buradan bu iki çizge modelinin her ne kadar farklı tanımlansalar da çok sayıda düğüm ve düşük bağlanma olasılıklarında birbirlerine denk olduğunu göstermiş oluyoruz.

Kuvvet Yasası Derece Dağılımlı Çizgeler

Şu ana kadar değindiğimiz iki tip çizge de birbirine denk olduğundan, her ikisinin de derece dağılımlarının benzer yani Poisson olduğunu söyleyebiliyoruz. Bu dağılımın karakteristik özelliğine göre, dereceler üzerinden konuşuyorsak, derece sayısını ortalama etrafında kümelenmiş bir değer civarında bulmayı bekliyoruz. Bir düğümün yüksek sayıda derece sayısına sahip olma olasılığı, ortalama değerden sonra paydaki $e^{-Np}$ ve $N!$ faktörleri nedeniyle hızlı bir şekilde azalıp sıfıra gidiyor. Alternatif olarak bu tip sıfıra düşme durumunun bu kadar hızlı gerçekleşmediği, dolayısıyla yüksek sayıda dereceye sahip düğümleri hala oldukça yüksek olasılıklarla bulduğumuz dağılımlara bir örnek olarak 'kuvvet yasası(power-law) dağılımları' verilebilir. Bu tip dağılımlar $P(q) \sim q^{- \gamma}$ şeklinde ifade ediliyorlar.

Bu dağılımlara yönelmemizin motivasyonu aslında zamanında A. Barabasi ve o zamanlar doktora öğrencisi R. Albert'in özellikle internet ağı tipi büyük ağların nasıl büyüdükleri üzerine yaptıkları çalışmalardan kaynaklanıyor. İkilinin önerdikleri 'seçmeli büyüme' (preferential attachment) modeliyle basitçe, düğümlere yeni bir kenar bağlanma olasılığı o düğümün mevcut derecesi ile doğru orantılı olacak şekilde bir çizge büyüme kuralı ortaya atıyorlar. Bu model ile mevcut internet ağını oldukça gerçeğe yakın modelleyerek, aynı zamanda bu tip bir çizgede ortaya çıkabilecek ilginç yapıları da gösteriyorlar. Bunlardan en öne çıkanı, merkez (hub) olarak tanımlanan derecesi çok yüksek ve o ağ üzerindeki bir çok bağlantıyla ilişkili düğümlerin varlığı... Sosyal ilişkilerde 'popüler insanlar', internet ortamında 'çok takip edilen ünlü kişiler', çok ziyaret edilen ve çok fazla bağlantı verilen internet siteleri gibi örnekler bu merkezlere örnek verilebilir. Bu modelin en önemli çıktısı, bu tip bir büyüme modeliyle oluşturulan çizgelerin derece dağılımlarının $\gamma = 3$ parametresi ile karakterize edilen kuvvet yasası dağılımları olduğunu göstermesi. Modelden elde edilen $\gamma = 3$ değerinin internet ağı için gerçek değere çok yakın olduğu görülüyor.

Bu tip kuvvet yasası dağılımına sahip çizgelerde Poisson dağılımlı çizgelerin tersine çok sayıda düğümle bağlantıya sahip düğüm sayısı sıfıra çok yavaş gidiyor, dolayısıyla yüksek sayıda dereceye sahip düğümleri bu tip çizgelerde gözleyebiliyoruz (örneğin bir önceki paragraftaki 'hub'lar). Bu tip dağılımları karakterize etmek için belirli bir ölçek olmadığını görüyoruz çünkü birazdan hesaplayarak göstereceğimiz üzere bu tip dağılımlara sahip çizgelerin belirli bir ortalamaları veya standart sapmaları genellikle olmayabiliyor. Bu nedenle bu tip çizgelere 'ölçeksiz (scale-free) çizgeler' deniyor. Bu çizgeleri karakterize eden kuvvet yasası dağılımları, büyük değerler için sıfıra gitmeleri nedeniyle 'kalın-kuyruklu' (fat-tail) dağılımlar olarak da adlandırılabiliyorlar.

Rasgele(random) ve ölçeksiz(scale-free) çizgelerin derece dağılımları arasındaki fark. Sağdaki kuvvet yasası dağılımının logaritmik ölçekte çizildiğine dikkat edin. (Kaynak)

Şimdi bu tip dağılıma sahip çizgeler için ortalama ve standart sapma hesapları yapacağız. Düğüm derecesine, integrasyondaki $d$ ile karışmaması için $q$ deyip devam edeceğiz. $q$ düğüm derecesinin ortalaması için:
$$\langle q \rangle = \sum_{d=0}^N P(q)q \sim \int_{0}^N P(q) q dq$$
$$\langle q \rangle = \int_{0}^N q^{- \gamma} q dq = \frac{q^{-\gamma +2}}{-\gamma + 2}\Big|_0^N $$ Eğer $\gamma >2$ ise: $$\langle q \rangle = \frac{-1}{2- \gamma}\Big[\frac{1}{N^{\gamma - 2}} - \frac{1}{a^{\gamma -2}}\Big] \tag{3}$$ $(3)$'deki ifade $N \to \infty$ için $0$'a gidiyor, Fakat eğer $\gamma < 2$ durumunda $\frac{1}{N^{\gamma-2}}$ terimi patlıyor ve $\langle q \rangle$ sonsuza gidiyor: $$\langle q \rangle \to \infty$$ Kısacası $\gamma < 2$ için ortalama ıraksıyor yani belirli bir ortalama değeri yok. Benzer hesabı $\sigma^2$ için yaptığımızda, hesaplarken gelen $\langle q^2 \rangle $ terimi için de benzer bir ıraksaklık problemi ile karşılaşıyoruz. $$\langle q^2 \rangle = \int_{0}^N q^{- \gamma} q^2 dq = \frac{q^{-\gamma +3}}{-\gamma + 3}\Big|_0^N $$ Eğer $\gamma <3$ ise $\langle q^2 \rangle$ ıraksıyor: $$\langle q^2 \rangle \to \infty$$Dolayısıyla varyans $\sigma^2 = \langle q^2 \rangle - \langle q \rangle^2$ da ıraksıyor. Böylece $P(q) \sim q^{-\gamma}$ şeklinde derece dağılımına sahip çizgelerin belirli bir ölçeğe sahip olmadığını göstermiş olduk.

Ölçeksiz çizgelerin, içinde bulundurdukları yüksek dereceli düğümler sayesinde örneğin E-R çizgelerine göre daha dayanıklı (robust) olarak tanımlanıyorlar (R. Albert, H. Jeong, A. Barabassi, Error and attack tolerance of complex networks, Nature, 2000). Burada bahsi geçen dayanıklılık, çizgeden yavaş yavaş kenarlar koparmaya başlandığında çizge yapısının, birbirine sıkı bağlarla bağlı merkezi bir yapıyı sürekli koruyarak, dağılmaya karşı ne kadar dirençli olduğunu ifade ediyor. E-R çizgeleri bunun tam tersi, küçük sayıda kenar koparılmasıyla birbirinden tamamen bağlantısız küçük parçalara ayrılabiliyorlar. Koparma sıklığı/olasılığı şeklinde bir $f$ parametresi belirlediğimizde E-R çizgelerinde bu $f$ bir kritik değere ($f_{critical}$) ulaştığında çizge tamamen kopmuş oluyor. Bu davranış aslında bir tip 'faz geçişi' şeklinde modellenebiliyorlar (dolayısıyla aslında bunun istatistiksel fizikteki 'percolation' davranışına denk geldiği belirtiliyor).

Bu bölümde Erdös-Renyi çizgesini tanımlayıp, bunların ilk bölümdeki Gilbert çizgesi ile eşdeğer olduklarını gösterdik. Ardından kuvvet yasası dağılımı gösteren çizgeleri inceleyerek belirli $\gamma$ parametreleri için derece ortalama ve varyanslarının ıraksadığını görüp buradan yola çıkıp ölçeksiz çizgeleri tanımladık. Bir sonraki bölümde çizgelerdeki düğümler arası ortalama uzaklıkları inceleyip 'ağaçsı çizgeler' üzerinden 'küçük dünya'(small world) fenomenini inceleyeceğiz.



1 Ağustos 2015 Cumartesi

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 'ı) 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.