Rassal Ağlar
Rassal ağlar, ağ teorisinin bir dalı olarak, düğümler (noktalar) ve aralarındaki kenarlar (bağlantılar) tarafından oluşturulan karmaşık yapıları inceleyen bir alandır. Bu ağlar, düğümler ve kenarlar arasındaki bağlantıların rastgele oluştuğu modeller üzerine kuruludur. Rassal ağların temel özellikleri ve teorik yönleri şu şekildedir:
Tanım ve Temel Kavramlar
Rassal ağ, düğümler arasındaki bağlantıların rastgele oluşturulduğu bir grafik yapısını ifade eder. Bu yapılar, birçok gerçek dünya sisteminin, örneğin sosyal ağların, biyolojik ağların veya iletişim ağlarının soyut temsilleri olarak kullanılır.
Model Tipleri
Rassal ağlar, farklı modellerle temsil edilebilir. En bilinen rassal ağ modellerinden biri Erdös-Rényi modelidir. Bu modelde, her düğüm çifti arasında sabit bir olasılıkla bağlantı oluşturulur. Başka bir popüler model, Barabási-Albert modelidir, bu model tercihli bağlanma prensibiyle büyüyen ağları temsil eder.
Derece Dağılımı
Rassal ağlarda, düğümlerin derecesi (bir düğümün bağlantı sayısı) önemli bir özelliktir. Erdös-Rényi modelinde, derece dağılımı genellikle *Poisson dağılımına uyar. Diğer modellerde, özellikle tercihli bağlanma ile büyüyen ağlarda, derece dağılımı genellikle bir güç yasasını takip eder.
*Poisson dağılımı, olasılık kuramı ve istatistik bilim kollarında bir ayrık olasılık dağılımı olup belli bir sabit zaman birim aralığında meydana gelme sayısının olasılığını ifade eder. Bu zaman aralığında ortalama olay meydana gelme sayısının bilindiği ve herhangi bir olayla onu hemen takip eden olay arasındaki zaman farkının, önceki zaman farklarından bağımsız oluştuğu kabul edilir. (Vikipedi)
Kümeleme Katsayısı ve Ağ Yapısı
Rassal ağlarda kümeleme katsayısı, bir düğümün komşularının birbirine ne kadar sık bağlandığını gösterir. Erdös-Rényi gibi bazı rassal ağ modellerinde, kümeleme katsayısı genellikle düşüktür.
Yol Uzunlukları ve Küçük Dünya Fenomeni
Rassal ağlarda, düğümler arası ortalama en kısa yol uzunluğu sıklıkla incelenir. Bazı rassal ağlar, “küçük dünya” özelliğine sahiptir, yani düğümler arasındaki ortalama mesafe, ağın büyüklüğüne kıyasla oldukça küçüktür.
Dev Bileşen ve Ağ Bağlantılılığı
Bir rassal ağda, belirli bir bağlantı olasılığından sonra, ağın büyük bir kısmını kapsayan bir dev bileşenin ortaya çıktığı gözlemlenir. Bu, ağın bağlantılılığı ile ilgili önemli bir özelliktir.
Matematiksel ve İstatistiksel Analizler
Rassal ağların analizi genellikle olasılık teorisi ve istatistiksel metodlar kullanılarak yapılır. Bu analizler, ağın yapısal özelliklerini ve davranışını anlamak için önemlidir.
Uygulamalar ve Gerçek Dünya Bağlantıları
Rassal ağ modelleri, gerçek dünya ağlarının özelliklerini anlamak ve tahmin etmek için kullanılır. Bu modeller, epidemiyoloji, sosyoloji, bilgisayar bilimi ve biyoloji gibi birçok alanda uygulanabilir.
Erdös-Renyi Rassal Ağ Modeli
Erdös-Renyi Rassal Ağ Modeli (ER Modeli), rastgele graf teorisi kapsamında önemli bir yer tutan bir modeldir. Bu model, Paul Erdös ve Alfred Rényi tarafından 1959 yılında tanıtılmıştır ve ağ teorisindeki en temel modellerden biridir. Modelin temel özelliği, grafların rastgele oluşturulmasıdır. Şimdi bu modeli detaylı bir şekilde anlatalım:
Modelin Tanımı
Erdös-Renyi modeli, düğümler arasındaki bağlantıların rastgele oluşturulduğu bir ağ modelidir. Bu modelde, her düğüm çifti arasında bağlantı oluşturma olasılığı sabittir ve bu olasılık tüm düğüm çiftleri için aynıdır.
Düğüm ve Kenarlar
Modelde, N sayıda düğüm bulunur. Her bir düğüm çifti arasında, önceden belirlenmiş bir p olasılığı ile kenar (bağlantı) oluşturulur. Bu işlem, tüm düğüm çiftleri için bağımsız olarak gerçekleştirilir.
Grafların Oluşumu
Bir Erdös-Renyi grafiği oluşturmak için, başlangıçta N düğümü olan ve aralarında hiç kenar olmayan bir ağ alınır. Daha sonra, her düğüm çifti için, p olasılığı ile bir kenar eklenir ya da eklenmez.
Parametreler
Bu modelde iki temel parametre vardır: N (düğüm sayısı) ve p (kenar oluşturma olasılığı). N’nin büyük, p’nin küçük olduğu durumlarda, ağ seyrek (sparse) bir yapıya sahip olur.
Bağlantıların Dağılımı
Erdös-Renyi modelinde, düğümlerin dereceleri (yani kaç tane kenara sahip oldukları) genellikle Poisson dağılımına uyar. Bu, çoğu düğümün yaklaşık olarak ortalama derecede bağlantıya sahip olduğu anlamına gelir.
Dev Bileşenin Oluşumu
Erdös-Renyi modelinde, belirli bir p değeri (kritik eşik) üzerinde, ağın büyük bir kısmını kaplayan bir ‘dev bileşen’ oluşur. Bu dev bileşen, ağdaki çoğu düğümün birbiriyle dolaylı olarak bağlantılı olduğu büyük bir alt grafdır.
Kümeleme Katsayısı
Erdös-Renyi modelinde, kümeleme katsayısı genellikle düşüktür. Bu, düğümlerin komşularının birbiriyle bağlantılı olma olasılığının düşük olduğu anlamına gelir.
Yol Uzunluğu
Ağın ortalama yol uzunluğu, genellikle log(N)/log(ortalama derece) ile orantılıdır. Bu, düğümler arasındaki ortalama mesafenin ağın büyüklüğü ile logaritmik olarak arttığı anlamına gelir.
Bağlantısızlık
p çok düşükse, ağ büyük oranda bağlantısız parçalardan oluşur. Her düğüm, yalnızca birkaç diğer düğüm ile bağlantılıdır ve geniş ölçekli bağlantılar yoktur.
Kritik Eşikler
Erdös-Renyi modelinde, belirli kritik eşikler vardır. Bu eşiklerin altında ağ parçalı, üstünde ise birleşik bir yapıdadır. Bu eşik değeri, genellikle 1/N civarındadır.
Erdös-Renyi Makale İncelemeleri
- A study on properties of random interval graphs and Erdős Rényi graph g(n, 2/3) – Iliopoulos, V. – Journal of Discrete Mathematical Sciences and Cryptography, 20(8), pp. 1697–1720 – 2017
- On random walks and random sampling to find max degree nodes in assortative erdos renyi graphs – Stokes, J., Weber, S. – 2016 IEEE Global Communications Conference, GLOBECOM 2016 – Proceedings, 7842044 – 2016
- Numerical simulations of the phase transition property of the explosive percolation model on Erdös Rényi random network – Li, Y., Tang, G., Song, L.-J., …Xia, H., Hao, D.-P. – Wuli Xuebao/Acta Physica Sinica, 62(4), 046401 – 2013
Makale 1) A study on properties of random interval graphs and Erdős Rényi graph g(n, 2/3)
Makale, rastgele aralık grafikleri ve Erdős-Rényi graf G(n,2/3) üzerindeki çalışmaları detaylı bir şekilde inceliyor. Ana odak, bu graf türlerinin kenar sayıları ve düğüm derecelerinin dağılımı gibi özelliklerinin tahmin edilmesi üzerinedir. Yazar, rastgele aralık grafiklerinde kenar sayısının n^(2/3) civarında olduğunu ve düğüm derecelerinin Erdős-Rényi modeline göre çok daha geniş bir aralıkta dağıldığını belirtiyor. Ayrıca, rastgele aralık grafiklerinde düğüm derecelerinin Erdős-Rényi modeline kıyasla daha dağıtık olduğu ve bazı durumlarda maksimum derecenin n−1 olduğu gösteriliyor. Bu sonuçlar, rastgele grafik teorisinde önemli bir katkı sağlıyor ve bu graf türlerinin yapısal özelliklerine dair daha derin anlayışlar sunuyor.
Makale 2) On random walks and random sampling to find max degree nodes in assortative erdos renyi graphs
Makale, Erdős-Rényi grafiklerinde maksimum derece düğümleri bulmak için rastgele yürüyüşler ve rastgele örnekleme yöntemlerini inceliyor. Araştırmada, bu grafiklerde maksimum derece düğümlerinin sayısı ve bunları bulmak için en etkili yöntemin ne olduğu soruları ele alınıyor. Makalede, büyük Erdős-Rényi grafiklerinde ortalama olarak tek bir maksimum derece düğümü olduğu ve rastgele yürüyüş ile rastgele örnekleme yöntemlerinin performansının grafiğin düzenliliğine (assortativity) bağlı olduğu sonuçlarına varılıyor. Ayrıca, rastgele yürüyüş yönteminin yüksek düzenli grafiklerde daha etkili olduğu gösteriliyor. Bu bulgular, sosyal ağlarda popüler kullanıcıları veya önemli düğümleri bulma konusunda faydalı olabilir.
Makale 3) Numerical simulations of the phase transition property of the explosive percolation model on Erdös Rényi random network
Bu makale, Erdős-Rényi rastgele ağlarında patlayıcı perkolasyon modelinin faz geçiş özelliklerine yönelik sayısal simülasyonları inceliyor. Çalışma, Achlioptas süreci tarafından tetiklenen patlayıcı perkolasyon modelinin Erdős-Rényi rastgele ağlar üzerindeki faz geçiş özelliklerini, düzen parametresi, ortalama kümelenme boyutu, anlar, standart sapma ve kümelenme heterojenliği gibi temel perkolasyon niceliklerini sayısal simülasyonlarla analiz ediyor. Sonuç olarak, bu niceliklerin hepsi, perkolasyon eşiğinde sürekli faz geçişlerinin tipik bir özelliği olan güç yasası ölçeklenme davranışını sergiliyor, ancak düzen parametresi aynı anda kesikli bir geçiş özelliği gösteriyor. Bu nedenle, Erdős-Rényi rastgele ağlarındaki patlayıcı perkolasyon geçişi ne standart bir kesikli faz geçişi ne de düzenli rastgele perkolasyon modelindeki sürekli geçiş olarak kabul edilebilir. Bu, perkolasyon modelinin kendine özgü bir “tekil” faz geçişi olduğunu göstermektedir.
Kaynakça
- Kun, J. (2013). The Erdős-Rényi Random Graph. Retrieved from Jeremy Kun’s Blog.
- Li Yan, Tang Gang, Song Li-Jiang, Xun Zhi-Peng, Xia Hui, Hao Da-Peng. (2013). Numerical simulations of the phase transition property of the explosive percolation model on Erdös Rényi random network. Acta Physica Sinica, 62(4). DOI: 10.7498/aps.62.046401.
- Iliopoulos, V. (2016). A study on properties of random interval graphs and Erdős Rényi graph 𝒢(n, 2/3). Journal of Discrete Mathematical Sciences & Cryptography. DOI: 10.1080/09720529.2016.1184453.
- Stokes, J., Weber, S. (2016). On random walks and random sampling to find max degree nodes in assortative erdos renyi graphs . IEEE Xplore. DOI: 10.1109/XXX.2016.7842044.
- Scopus Database. Retrieved from Scopus.
- Python Igraph Tutorial on Erdős-Rényi Graphs. Retrieved from Python Igraph Documentation.
- Wikipedia. Poisson Dağılımı. Retrieved from Turkish Wikipedia.
