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.

Hiç yorum yok:

Yorum Gönder