Ünite 4: Ölçekten Bağımsızlık ve Kuvvet Yasası

Giriş

Rassal ağ modeli, uzun bir süre ağlar konusundaki paradigmayı belirlemiştir. Bu modele göre, bir ağda her bir düğümün başka bir düğümle bağ kurma olasılığı eşittir ve bağlar rassal bir süreç ile oluşmaktadır. Ancak her ağ rassal ağ özelliği taşımamaktadır. Barabasi’nin ‘karmaşık ağların belli kurallara ya da ilkelere göre organize edilmiş olma fikri’ üzerine çalışmaları bu konuda başlangıç noktasıdır. Barabasi, internet ağının ölçülmesi, haritalanması ve modellenmesiyle ilgilenmiştir. İnternetin haritasından yola çıkarak merkezi düğümlerden ve ağların ölçekten bağımsız oluşu ortaya çıkmaktadır. Kuvvet yasası ile bir ağın ölçekten bağımsızlığının incelenmesinin ardından ağların büyümesi, ağın yapısı ve özellikleri belirlenebilmektedir.

İnternetin Haritası

1998 yılına kadar www’nun yaklaşık olarak rassal bir ağ olduğu düşünülmekteydi. Web’deki her dokümanın kişisel veya profesyonel tercihlerle ortaya çıktığı ve kişiler ve kurumların ilgilendikleri alanlar çok çeşitli olduğu için bu dokümanlar üzerindeki bağlantıların da rassal olarak ortaya çıktığı kabul edilmiştir. 2000’li yılların başına kadar bilim dünyasının www’nun yapısını yeterli şekilde anlamadığı kabul edilmektedir. Günümüzdeki gelişmeler web’i büyük ölçekli, insan özneli deneklerle deney yapılan sanal bir laboratuvar haline getirmiştir.

Sayfa 64’te bulunan Şekil 4.1’de internetin haritası verilmiştir. İnternetin haritası incelendiğinde görülmektedir ki, çok bağlantıya sahip olan (derecesi yüksek) merkezi düğümlerin sayısı az, az bağlantıya sahip olan (derecesi düşük) düğümlerin sayısı ise çoktur. İnternetteki sayfaların % 80’inden fazlası 4 bağlantıdan azına sahiptir ve bu sayfaların % 1’inden azı 1000’den fazla bağlantıya sahiptir. Bu verilerden internetin rassal bir ağ olmadığı anlaşılmaktadır.

Eğer internet bir rassal ağ olsaydı, az ve çok sayıda bağlantıya sahip olan düğümlerin sayısı az; buna karşılık ortalama sayıda bağlantıya sahip olan düğümlerin sayısı çok olmalıydı.

Merkezi düğümlerin ortaya çıkmasının nedeni, ağların büyümesidir. Aynı zamanda ağlar büyürken düğümler ‘tercihli bağlantı’ yaptıkları için bağlantı açısından zengin düğümler daha da zengin olmakta ve bu sürecin sonucunda merkezi düğümler oluşmaktadır.

Merkezi düğümlerin ortaya çıkmasında ilk düşüncelerden biri İtalyan ekonomist ve sosyolog Vilfredo Pareto tarafından “Pareto İlkesi” şeklinde ortaya konmuştur. Kuvvet yasasının gerçek hayattan yapılan ilk gözlemi de Pareto tarafından 1800’lü yılların sonunda İtalya’da gelir dağılımı konusunda yapılmıştır.

Kuvvet yasası oluşumunun bir başka kanıtı günümüzde Benford yasası olarak anılan yasa ile verilmektedir. Bu yasa ilk kez 1881 yılında Simon Newcomb tarafından ortaya atılmıştır. Ancak konunun popülerlik kazanması, Fizikçi Frank Benford ile olmuştur. “İlk Sayı Savı” olarak da adlandırılan bu yasaya göre, çok çeşitli alanlardaki verilerde kullanılan ilk sayılar ele alındığında, en sık kullanılan sayı 1’dir ve diğer kullanılan tam sayı değerlerinin olasılığı sol yukarıdan sağ aşağıya bir eğri olarak azalmaktadır. Benford yasası grafiksel olarak Sayfa 67’de bulunan Şekil 4.5’te verilmiştir.

Ölçekten Bağımsızlık

Kentlerin nüfusları, depremlerin yoğunlukları, elektrik kesintilerinin büyüklükleri gibi değişkenlerin dağılımları kuvvet yasası dağılımına uymaktadır, bu tür değerler bir ortalama değer ile karakterize edilemezler (Clauset vd., 2009). Matematiksel olarak ? üs veya ölçekleme parametresi olduğunda eğer x değerinin dağılımı,

P(x) ? x ^-a

dağılımına uygunsa x, kuvvet yasasına göre dağılmaktadır. Burada 2 < ? < 3 aralığında değişmektedir. Her iki tarafın logaritması alındığında: ln P(x) ? -? + ln x

elde edilmektedir. Uygulamada x’in tüm değerleri kuvvet yasasına uymamaktadır. Genelde belirli bir x _Min değerinden büyük olan x değerleri için kuvvet yasası geçerli olmaktadır.

Bir rassal ağın derece dağılımı, ortalaması < k > ve standart sapması < k > ^1/2 olan bir Poisson dağılımıdır. Standart sapma ortalamanın karekökü olduğu için her zaman ortalamadan daha küçüktür. Sözü edilen bu ağın dereceleri, ortalamaya standart sapmanın belirli katları eklenip çıkarılarak elde edilen aralıkta bulunmaktadır. Bu nedenle, rassal ağda düğümlerin dereceleri birbirleriyle karşılaştırılabilmekte ve bu karşılaştırmalarda < k > ile gösterilen ortalama derece bir ölçek (scale) görevi yapmaktadır.

Ölçekten bağımsız ağlarda üs olan ? < 3 ise, dağılımın birinci momenti sonlu ama ikinci momenti sonsuzdur. Bu nedenle, ? < 3 olduğunda ağın kendi içinde bir ölçeği yoktur ve ağ ölçekten bağımsızdır.

Ağlar, yeni düğümlerin ağa eklenmesiyle büyümektedirler. Ağlarda “popüler olmanın çekiciliği” konusu tercihli bağlantı ile ilgilidir. Eğer daha popüler düğümlerle bağlantı yapılıyorsa, bunun sonucunda gerçek bir çok ağda gözlendiği gibi derece dağılımı, kuvvet yasasına uygun olmaktadır. Gerçek ağlar büyürler, ağa yeni düğümler katılır ve yeni düğümler daha fazla bağlantıya sahip olan düğümlere bağlanırlar. Bu süreç, tercihli bağlantı (preferential attachment) olarak adlandırılmaktadır. Sayfa 68’de verilen Şekil 4.6’da tercihli bağlantı nedeniyle ölçekten bağımsız ağın belirmesi görülmektedir.

Kuvvet Yasası

Gerçek hayatta birçok ölçüm değeri tipik bir değerin etrafında kümelenmektedir. Bir otoyoldaki otomobillerin hızları, bir alışveriş merkezindeki karpuzların tartıları, belirli bir günde İstanbul’daki sıcaklık değerleri hep ortalama bir değerin etrafında kümelenerek bu değeri temsili bir değer haline getirmektedir. Buna karşılık, her değer bu şekilde dağılmak zorunda değildir. Kuvvet yasası dağılımları sık sık kalın kuyruklu dağılımlar, Pareto dağılımları ve Zipf dağılımları adlarını almaktadırlar. Ölçekten bağımsız bir ağda derece dağılımı kuvvet yasasına uymaktadır.

Sayfa 70’te bulunan Şekil 4.7’de farklı üs değerlerine göre kuvvet yasası derece dağılımları verilmiştir. Kuvvet yasası eğrilerinin çok sayıda türü vardır ve bunlar farklı kuyruklara sahiptirler. Kuyruğun şekli dağılımdaki üs (?) tarafından belirlenmektedir. ?’nın değeri büyüdükçe eğri daha yüksek hızla düşmekte ve daha ince bir kuyruğa sahip olmaktadır.

Birçok gerçek sistemde ? > 2 değerine sahiptir. Kuvvet yasasında üs değeri olan ?’nın değerinin değişmesi, beraberinde sistemin özelliklerinin değişmesini getirmektedir (Barabási, 2013).

• Anomali durumu (? < 2): ? > 2 olması durumunda, N limit durumunda sonsuza yaklaştığında (ağdaki düğüm sayısı çok büyüdüğünde), ortalama derece olan < k > ıraksamaktadır. En merkezi düğümün bağlantı sayısının ağdaki düğüm sayısından fazla olması gerekeceği için bu koşullara sahip ölçekten bağımsız bir ağ olamaz.
• Ölçekten bağımsızlık durumu (2 < ? < 3): Bu durumda derece dağılımının birinci momenti sonlu ama ikinci ve daha yüksek mertebeden momentleri N›? için ıraksamaktadır.
• ? > 3 olması durumu: Bu durumda ölçekten bağımsız bir ağı rassal bir ağdan ayırmak zorlaşmaktadır.

Ağların Büyümesi

Ağlar zaman içinde ele alındığında ağların büyüdüğü ve ağlara yeni düğümlerle yeni bağlantıların eklendiği görülmektedir. Ağların gelişip büyümesi hakkında çok sayıda soru ortaya çıkmaktadır (McGlohon, 2011):

• Ağlar büyüdükçe yapıları değişir mi?
• Ağlar büyüdükçe belirli özelliklere sahip olurlar mı?
• Ağlarda davranışın aniden değiştiği bir evde geçişi (phase transition) var mıdır?
• Ağlar büyüdükçe zayıf bağlantılı bileşenler sonunda dev bileşen içinde absorbe edilirler mi?

Son sorunun yanıtı olarak gerçek ağlarda zaman içinde dev bir bileşenin oluştuğu söylenebilir. Ağlarda üçlü sayıları ve üçgenlere katılan düğüm sayıları bir kuvvet yasasına uygun olarak dağılmaktadır (Leskovec, 2008). Ağlarda bileşenlerin dağılımı kuvvet yasasına göredir. Ağlar büyüdükçe bir jölelenme noktasına ulaşmakta ve bu noktada küçük, çok sayıda bağlantısız bileşen birleşerek çizgede en büyük bağlantılı bileşen olan dev bileşeni oluşturmaktadır. Bu nokta yarıçapın en büyük olduğu noktadır ve daha sonra yarıçap küçülerek bir denge değerine ulaşmaktadır. Leskovec ve diğerleri gerçek çizgelerin yarıçaplarının zaman içinde küçülüp stabilize olduğunu göstermişlerdir (Leskovec, 2008). Bu noktadan önce çizge, oluşma dönemindedir ve küçük bağlantısız bileşenlerden oluşmaktadır.

Statik bir çizge için yarıçap, herhangi iki düğüm arasındaki maksimum uzaklıktır. Uzaklık, yönü hesaba katmadan iki düğüm arasındaki minimum sıçrama sayısıdır. Etkin yarıçap, bütün olası düğüm çiftleri arasındaki uzaklıkların 90. persantilidir. Etkin yarıçap, yarıçapa göre daha dirençli bir ölçüdür ve aykırı, uç değerlerden (sapan değerlerden) etkilenmemektedir. Yarıçap veya etkin yarıçap bir çizgenin ne kadar küçük dünya özelliği taşıdığını, çizgenin bir ucundan diğerine ne kadar hızlı bir şekilde gidilebileceğini göstermektedir.

Gerçek dünyadaki neredeyse tüm ağlar zaman içinde düğüm ve bağlantı ekleyip çıkararak gelişmektedirler. Gerçek ağların analizi yoluyla elde edilen amprik gözlemler ağların kuvvet yasasına uygun şekilde yoğunlaştığını göstermektedir. Ağların zaman içinde ortalama derecesi çok büyük hızla artarken yarıçap ve etkin yarıçap azalmakta, aynı zamanda seyrek ağlardan yarıçapları kısa yoğun ağlara bir evre geçişi (phase transition) gerçekleşmektedir (Leskovec, 2007).

Ağların statik özellikleri şu şekilde sıralanmaktadır:

• Ağlarda kalın kuyruklu dağılımlar söz konusudur. Az sayıda merkezi düğüm, çok sayıda az bağlantıya sahip düğüm bulunmaktadır.
• Ağların yarıçapları küçüktür ve topluluk yapılarına sahiptirler.
• Çeşitli kuvvet yasaları geçerlidir. Üçlülerin kuvvet yasası, yoğunlaşma kuvvet yasası vb.

Ağların dinamik özellikleri şu şekilde sıralanmaktadır:

• Ağlar büyüdükçe yarıçapları küçülür ve ağlar yoğunlaşır.
• Sabit büyüklükteki küçük bileşenler, dev bileşen ile birleşene kadar belirli bir noktanın ötesine büyüyemezler.
• Diğer kuvvet yasaları geçerlidir.