Ünite 3: Ağların Türleri

Giriş

Sosyal ağlarda düğümler arası bağların nasıl oluştuğu önemli bir konudur. Bir ağda bulunan düğümler arasında rassal bağ kurulup kurulmadığı, amaçlanan bir durum için birbirini izleyen ortalama kaç bağa gerek olduğu ve iki düğümün sahip olduğu ortak kuvvetli bağların düğümler arasında bağ kurulmasına zemin hazırlama durumu hakkında çalışılmaktadır. Aynı tür düğümler arasında bağlantı kurulup kurulmamasına göre ağların farklı türleri bulunmaktadır. Bir ağın dirençli veya dirençsiz oluşu, yani etkilenme hızı veya olumsuz olarak ele alındığında tehlike ve saldırılara ne kadar açık olduğu önemli bir konudur.

Rassal Ağlar

Rassal ağ düşüncesi, Paul Erdos ile Alfréd Rényi’ye dayanmaktadır. Erdos-Rényi rassal ağ modelinde (Erdos ve Rényi, 1959) iki düğümün birbirleri ile bağlantılı olmaları, sabit bir olasılıkla gerçekleşmektedir. Sabit bir olasılıkla rassal bir şekilde düğüm çiftleri arasında bağlantılar oluşturulursa, sonuçta elde edilen ağ rassal ağ olmaktadır.

Sayfa 45’te verilen Şekil 3.1’de üç rassal ağ çizgesinde, artan üç olasılıkla üretilen rassal ağlar görülmektedir. Sabit olasılık arttıkça rassal ağlardaki bağlantı sayısı da artmaktadır.

Bir çizgede N düğüm varsa ve her bir düğüm ortalama z bağlantıya sahipse, her bağlantının gerçekleşme olasılıkları birbirinden bağımsız ve p ise, p = z/(N-1) olmakta ve N büyüdüğünde bu değer yaklaşık olarak z/N değerine eşit olmaktadır. Belirli bir düğümün sahip olduğu bağlantı sayısı olan k’nın dağılımına “derece dağılımı” denilmektedir. İlk şekli ile binom dağılımı olan bu dağılım, ağın büyük olması varsayımıyla poisson dağılımına yaklaşmaktadır. Sayfa 46’da verilen Şekil 3.2’de 200 düğüm ve p=0,01 olasılığı için bir binom ve ?=2 için bir poisson dağılımı görülmektedir.

Sayfa 47’de verilen Şekil 3.3’te 100 düğüm için üç farklı p düzeyinde çizilen üç rassal ağ, bu ağların gerçek derece dağılımları ve ağların derece dağılımlarının teorik olarak binom dağılımı ile belirlenmesi görülmektedir.

Rassal ağdan farklı ağ türleri olabileceği ve bu ağların derece dağılımlarının rassal ağdan farklı olabileceği bilinmelidir. Sayfa 48’de bulunan Şekil 3.4, Şekil 3.5, ve Şekil 3.6 ile Sayfa 49’da bulunan Şekil 3.7’de Barabasi ve Watss-Strogatz ağları görülmektedir.

Ağda iki kişinin birbirlerine ne kadar uzaklıkta oldukları “patika” kavramı ile belirlenmektedir. Patika “bir düğümle başlayıp bir düğümle biten bir bağlantı dizisi” olarak tanımlanmaktadır. Komşu olmayan iki kişi arasındaki uzaklık, birinden diğerine en küçük sıçrama sayısı ile ölçülmektedir.

Ağdaki uzaklıkları bulmak için genişlik öncelikli arama algoritması (breadth first algorithm) ile ilgili bir örnek Sayfa 49’da verilen Şekil 3.8’de verilmiştir.

İki kişi arasındaki en kısa patikaya, jeodezik uzaklık (geodesic distance) denilmektedir. Yarıçap (diameter) ise, bağlantılı bir ağda bulunan en büyük jeodezik uzaklıktır. Sayfa 50’de bulunan Şekil 3.9’da ortalama jeodezik uzaklığın hesaplanması görülmektedir.

Kümelenme katsayısı (clustering coefficent) basit bir örnekle açıklanabilmektedir: Eğer bir sosyal ağda arkadaşlarınız da birbirleri ile arkadaşlarsa ve birbirlerini tanıyorlarsa, kümelenme katsayınız yüksektir. Eğer arkadaşlarınız birbirini tanımıyorsa kümelenme katsayınız düşüktür. Kümelenme katsayısı arkadaşlarınızın birbirleriyle ne kadar arkadaş olduklarını ölçmektedir. Bir yönsüz ağın kümelenme katsayısı ağdaki üçgen sayıdır. Bir ağın genel kümelenme katsayısı, her düğümün lokal kümelenme katsayısına dayanmaktadır. Sayfa 51’de bulunan Şekil 3.10, Şekil 3.11 ve Şekil 3.12’de kümelenme katsayısı hesaplanması verilmiştir.

Altı Adım Hipotezi

Sosyoloji ve ağ kuramında “altı adım hipotezi” sosyal psikolog Steve Milgram’ın (S:52, Şekil 3.13) 1967 yılında 60 mektup yollayarak gerçekleştirdiği deneye dayanmaktadır. Mektuplar Cambridge, Massachusetts’de bulunan bir konuma gönderilmiş ve deneye katılanlardan bu mektupları arkadaşlarının arkadaşlarına ulaştırarak istenilen kişiye göndermeleri istenmiştir. İlk anda deneye katılım az olsa da sonraları Milgram katılımı çeşitli yollar ile artırarak, mektupların ortalama altı adımda istenilen yere ulaştığını belirlemiştir.

2001 yılında Duncan Watts, Milgram’ın deneyini bu kez internet ortamında, 166 ülkeden 61168 kişinin oluşturduğu 24163 farklı e-posta zinciri ile denemiş ve ortalama adım sayısını tekrar altı olarak bulmuştur.

Küreselleşme olgusu ile dünyanın küçük bir köy haline geldiği çok sık tekrarlanan bir cümledir. Ulaşım ve haberleşme olanaklarının yetersiz olduğu dönemlerde bile dünyanın küçük olduğunu Steve Milgram kanıtlamıştır. Teknolojinin etkisi ile dünya küçük bir köy haline gelmeye devam etmektedir. 2011 yılında Facebook veri takımının vardığı bir sonuca göre, Facebook’ta altı derecelik ayrılık dört dereceye düşmüştür. Kısaca günümüzde Facebook’ta, birbirini hiç tanımayan iki kişi arasındaki uzaklık dört adıma düşmüş bulunmaktadır.

Küçük Dünya Ağları

Watts–Strogatz modeli olarak da bilinen küçük dünya ağları modeli (Watts ve Strogatz, 1998) küçük dünya özelliklerine sahip rassal ağ üretme modelidir. Bu tür çizgelerin, kısa ortalama patika uzunluklarına ve yüksek kümelenme katsayılarına sahip oldukları belirlenmiştir.

Üçlü kapanma olgusuna göre eğer iki kişi aynı kişi ile kuvvetli arkadaşlık bağları içindeyse ve arkadaş değillerse, zaman içinde onlar da arkadaş olmakta ve üçlü kapanma gerçekleşerek bir arkadaşlık üçgeni ortaya çıkmaktadır. Sayfa 53’te verilen Şekil 3.14 ve 3.15’te üçlü kapanma kavramı şekilsel olarak ifade edilmiştir.

Küçük dünya ağları iki ilke ile oluşturulabilmektedir:

• Birinci ilke üçlü kapanmalar ve üçgenlerden oluşmaktadır. •
• İkinci ilke bir dallanma yapısı oluşturarak düğümlere birkaç adımda erişilmesinden oluşmaktadır.

Sayfa 55’te verilen Şekil 3.16’da küçük dünya ağı oluşumu grafiksel olarak verilmiştir.

Bir ağın küçük dünya ağı olup olmadığını anlamak için o ağın ortalama patika uzunluğu ile aynı büyüklükteki rassal ağın ortalama patika uzunlukları ve ağların kümelenme katsayıları karşılaştırılmaktadır. Rassal ağların ortalama patika uzunlukları ve kümelenme katsayıları çok küçük olduğu için aşağıdaki koşullarda ağ küçük dünya ağı özelliklerine o kadar yakındır:

• Ağın ortalama patika uzunluğu/Aynı büyüklükteki rassal ağın ortalama patika büyüklüğünün 1 değerine yakın olması.
• Ağın kümelenme katsayısı/Aynı büyüklükteki ağın kümelenme katsayısının 1’den büyük olması.
• Küçük dünya katsayısı olan Ağın kümelenme katsayısı/Ortalama patika uzunluğunun büyük olması.

Küçük dünya ağları, kısa global patika uzunlukları ve yüksek yerel kümelenme katsayıları ile özetlenmektedir.

Sınıflayıcı ve Sınıflayıcı Olmayan Ağlar

Ağlar şu şekilde sınıflandırılabilmektedir:

• Bir ağda düğümler derecelerine bakılmaksızın başka düğümlerle rassal bağlantılar kuruyorsa bu ağlar nötral ağlardır.
• Eğer merkezi düğümler merkezi düğümlere ekleniyorsa, bu ağlar sınıflandırıcı (assortative) ağlardır.
• Çok bağlantısı olan düğümler zayıf bağlantısı olan düğümlerle bağlantı kuruyorlarsa bu ağlar sınıflandırıcı olmayan (dissassortive) ağlardır.

Sosyal ağlar sınıflandırıcı, teknolojik ve biyolojik ağlar ise sınıflandırıcı olmayan ağlardır.

Sayfa 56’da bulunan Şekil 3.17’de sınıflandırıcı ağ örneği ve Tablo 3.1’de farklı alanlardaki ağların sınıflandırıcılık ölçüsü açısından ne durumda oldukları verilmiştir.

Dirençli ve Dirençsiz Ağlar

Toplum sağlığı ve güvenliği açısından ağlar çok önemli bir konumdadır. Virüsler yada yenilikler insandan insana bulaşarak ağlarda yayılabilmektedir. Microsoft Sözlüğü (Microsoft, 1997) bulaşmayı şu şekilde tanımlamaktadır: “Bir hastalığın, bir insan veya nesne ile doğrudan temas ile geçmesi; bir hastalığın veya zehrin bu yolla aktarılması; duygusal durumun, heyecanın, zararlı bir etkinin aktarılması”.

Virüsler ilk karşılaşmada bulaşabilirken (basit bulaşma), yenilikler ancak birkaç karşılaşmadan sonra ve karşılaşma sayısında belirli bir eşik aşıldığında bulaşmaktadır (karmaşık bulaşma).

Saldırılarla karşılaştığında bile iyi performans gösteren bir ağ dirençli bir ağdır. Rassal ağlar dirençli ağlardır rassal ağlarda bütün düğümler belirli bir olasılıkla başka düğümlere bağlanmaktadır. Merkezi düğümlerin olduğu ağlar, bu düğümlerin hedef alınması koşuluyla dirençsiz ağlardır. Sayfa 57’de verilen Şekil 3.18’de ağlara hastalık bulaşmasını temsil eden görüntü verilmiştir.

Sayfa 58’de bulunan Şekil 3.19’da bir online siber saldırı haritası verilmiştir.