Ağ Bilimi: Ağ Modelleri Nelerdir?

Asena Ağustos 16, 2023

0 22 4 dakika okuma süresi

Ağ bilimi literatüründe birçok farklı ağ topolojisi bulunur. Ancak bu yaklaşımlar temelde birkaç temel ağ modellerine dayanmaktadır. Ağ modellerini oluşturan temel topolojiler yüzük örgü (İng: “ring lattice”), küçük dünya (İng: “small world”), Erdös rassal, çekirdek çevresi (İng: “core periphery”), ölçekten bağımsız (İng: “scale-free”) ve gözeli (İng:”cellular”) şeklindedir. Bu temel topolojiler aşağıda gösterilmiştir:

Yüzük örgü topolojisinde her düğüm, kendi komşusuna bağlıdır. Küçük dünya topolojisinde ise her düğüm birçok komşu düğümüne ve birkaç uzak düğüme bağlıdır. Erdös rassal topolojide her düğüm diğer düğümlere rastgele şekilde bağlıdır. Çekirdek çevresi topolojide düğümler yalnızca merkezi düğümlere, merkezi düğümler de birbirine bağlıdır. Ölçekten bağımsız topolojide birkaç merkezi düğüm diğer düğümlere bağlıdır. Gözeli topolojide ise ağ komünitelere ayrılmıştır; diğer bir deyişle düğüm grupları vardır ve her grup kendi içerisinde sıkı, diğer gruplarla seyrek bağlanmıştır.

Ağ biliminin tarihsel gelişimi göz önünde bulundurulduğunda üç adet teorik modelin temel modeller olduğu ve literatürdeki makale ve kitaplarda ağırlıklı olarak geçtiği görülmektedir. Bunlar Rassal ağlar (Erdös rassal), ölçekten bağımsız ağlar ve küçük dünya ağlarıdır.

İçindekiler

Ağ Modelleri

Rassal Ağ Modeli

Rassal ağlar (İng: “random networks”); düğüm sayısının belli, diğer tüm parametrelerin rastgele olduğu ağlardır. Diğer bir deyişle $N$ adet düğümün arasındaki $E$ adet bağlantı rastgele yerleşmiştir. Yani her iki düğüm arasında belli bir $p$ bağlanma olasılığı vardır ve $E$ sayısı da buna göre belirlenir.

Bağlanma olasılığından ötürü rassal ağlarda hiçbir düğüm arasında bağlantı olmayabilir veya her düğüm arasında bağlantı da olabilir. Bu nedenle daha doğru bir tanımlama yapılırsa, tek bir ağ üzerinden rastgeleliğin konuşulması doğru değildir. Bunun yerine $G (N, p)$ şeklinde bir ağlar kümesinin tanımlanması ve içindeki her elemanın (her bir $G$ ağı)

$p^{E}(1-p)^{\binom{N}{2}-E}$

olasılığına göre elde edilmesi gereklidir. Görüldüğü üzere rassal ağlarda sadece iki düğüm arasındaki bağlantı olasılığı sabitlenir. Bağlantı sayısı da başlangıçta sabit olmamakla birlikte beklenen değeri hesaplanabilir. $E$ adet bağlantıya sahip bir ağın kümeden seçilme olasılığı

$=\dbinom{\binom{N}{2}}{E} p^{E}(1-p)^{\binom{N}{2}-E}$

şeklindedir ki bu da Binom dağılımıdır. Ancak ağın büyüklüğü yani düğüm sayısı çok arttığı zaman derece dağılımı Poisson dağılımını verir. Bir rassal ağda $E$ sayısı belli ise ortalama derece ve kümelenme katsayısı için sırasıyla şunlar yazılabilir:

$\frac{2E}{N}\space, \space C=\frac{}{N-1}$

Bu ağ topolojisine Erdös-Renyi modeli de denmektedir.

Küçük Dünya Ağ Modeli

Bu modelde, bir ağdaki düğümler komşu olmadıkları düğümlere bile az sayıda adımda ulaşabilmektedir. Ortalama yol uzunluğunun küçük, kümelenme katsayısının büyük olduğu ağlardır. Watts-Strogatz modeli olarak da bilinen küçük dünya ağları düzenli bir ağ (örneğin yüzük örgü topolojisi) ile rassal ağ arasında kalan bir yapıya sahiptir. Watts tarafından 2003 yılında tanımlanan ve 0 ile 1 arasında değerler alabilen $β$ parametresi sıfır durumunda düzenli, bir durumunda rassal ağ oluşturur. Küçük dünya ağları bu $β$ aralığının ortalarında yer almaktadır.

$β$ parametresinin sıfır ve bir değerlerine göre ortalama yol uzunluğu $l (β)$ ve kümelenme katsayısı $C (β)$ aşağıdaki gibidir:

}\space,\space l(1) = \frac{\ln N}{\ln()} \\
C(0)=\frac{3}{4}\space,\space C(1) =\frac{}{4}”> $\frac{N}{2}\space,\space l(1) = \frac{\ln N}{\ln()} \\ C(0)=\frac{3}{4}\space,\space C(1) =\frac{}{4}$

Derece dağılımı da $β$ ‘ya ve kümelenme katsayısına bağlı olarak da formülize edilebilir ve $β = 1$ durumunda Poisson dağılımını verir.

Ölçekten Bağımsız Ağ Modeli

Doğal ve yapay tüm sistemlere rassal ve küçük dünya ağ modellerinden daha fazla uyan, ölçekten bağımsız ağ modeli adı altında bir model vardır. Derece dağılımları kuvvet yasası formundadır. Şöyle ki, bir düğümün k adet bağlantısı olma olasılığı şöyle belirlenir:

$\sim k^{-\gamma}$

Burada $γ\gamma$ derece üstelidir. Bu tip ağlarda bir düğümün çok fazla bağlantısının olma olasılığı rassal ağlardan daha yüksektir. Bu da merkez düğümlerin ağın özelliklerinden biri olduğunu göstermektedir.

Ağın büyümeye müsait ve öncelikli bağlantı (İng: “preferential attachment”) içeren yapıları ölçekten bağımsız ağları oluşturan iki temel bileşendir. Büyüme, ağdaki düğüm sayısının zamanla artması demektir. Öncelikli bağlantı ise ağa eklenecek yeni bağlantıların, bağlantı sayısı fazla olan düğümler ile olmasının daha yüksek olasılıkta olduğuna işaret etmektedir. Matematiksel olarak bağlanma olasılığı şu şekildedir:

$P(ki)=ki∑i=1NkiP(k_i) = \frac{k_i}{\sum\limits_{i=1}^Nk_i}$

Great Expectations (Charles Dickens)

Great Expectations is the thirteenth novel by Charles Dickens and his penultimate completed novel. It depicts the education of an orphan nicknamed Pip (the book is a bildungsroman, a coming-of-age story). It is Dickens’s second novel, after David Copperfield, to be fully narrated in the first person. The novel was first published as a serial in Dickens’s weekly periodical All the Year Round, from 1 December 1860 to August 1861. In October 1861, Chapman and Hall published the novel in three volumes. The novel is set in Kent and London in the early to mid-19th century and contains some of Dickens’s most celebrated scenes, starting in a graveyard, where the young Pip is accosted by the escaped convict Abel Magwitch. Great Expectations is full of extreme imagery – poverty, prison ships and chains, and fights to the death – and has a colourful cast of characters who have entered popular culture. These include the eccentric Miss Havisham, the beautiful but cold Estella, and Joe, the unsophisticated and kind blacksmith. Dickens’s themes include wealth and poverty, love and rejection, and the eventual triumph of good over evil. Great Expectations, which is popular both with readers and literary critics, has been translated into many languages and adapted numerous times into various media.

Warning: Unlike most of the books in our store, this book is in English.
Uyarı: Agora Bilim Pazarı’ndaki diğer birçok kitabın aksine, bu kitap İngilizcedir.

₺130.00

Bu model Barabasi ve Albert tarafından 1998 yılında geliştirilmiştir. Modeldeki ortalama yol uzunluğu olan

$\frac{\ln N} {\ln(\ln N)}$

paydadaki çift logaritmik düzeltme ile hesaplanabilir ve düğüm sayısı ile logaritmik şekilde artmaktadır. Bu modelin ortalama yol uzunluğu rassal ağlara göre küçüktür. Ölçekten bağımsız ağ heterojen, rassal ağlar homojen topolojide sayılabileceğinden ötürü ölçekten bağımsız ağ yapısı düğümleri birbirine daha fazla yaklaştırmaktadır. Kümelenme katsayısı da rassal ağlara göre daha büyüktür. Bu katsayı bir kuvvet yasası izleyerek, düğüm sayısının artmasıyla azalmaktadır.

Ölçekten bağımsız ağların derece dağılımı hiyerarşik şekilde olduğu için rastgele bir düğümü hedef alan ataklara karşı rassal ağlardan daha savunmasızdır. Merkez düğüm devreden çıktığı zaman ağın bütünlüğü bozulacaktır. Rassal ağlarda ise bağlantılar genellikle homojen bir dağılım gösterdiği için düğüm eksilmelerine daha dayanıklıdır. Diğer düğümler aralarındaki bağlantıları koruyabilir.

Buraya kadar değinilen üç temel ağ modeli ile ilgili derece dağılımı, kümelenme katsayısı ve ortalama yol uzunluğunun özeti aşağıdaki çizelgede verilmiştir.