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.
Hiç yorum yok:
Yorum Gönder