11 Mayıs 2021 Salı

Karmaşıklık (Bölüm 12) (Ateşan Aybars, 11 Mayıs 2021)

 

Düğümlerin kümelenmesi (clustering)

Kümelenme, daha büyük bir ağ sisteminin düğüm ve bağlantılarından oluşan alt kümesi ya da alt hiyerarşisidir, sistem bütününün ne kadar entegre veya parçalı olmasıyla ilgilidir. Alt kümeyi değerlendirmek üzere yapılacak modellemeye bir düğüm ile başlanır. Seçilen düğümün bağlı olduğu komşu düğümlerin aralarındaki bağlantısallık alt kümenin birçok özelliğini barındıran derece dağılımı konusunda fikir verir. Örneğin, Facebook’ta kaç arkadaşınızın diğer arkadaşlarınızı tanıdığı sorusu önemli bilgi olabilir. Arkadaşlarınızın çok sayıda bağlantısallığı, güçlü bir alt kümeleşmeyi ortaya çıkarır. Sosyal ağlardaki bu kümelenmeye “klik” denir.  Klik, birbirleriyle aynı ortamda diğerlerinden daha düzenli ve yoğun bir şekilde etkileşime giren bir grup insan topluluğudur.

Ağ içinde kümeleşmeye neden olan farklı yerel özelliklerin anlaşılması, ortaya çıkan topolojinin değerlendirilmesi için önemlidir. Ağ içinde herhangi bir tehdidin yayılmasını önlemek, buna çare olacak tedbirlerin tasarlanıp uygulanmasını sağlayabilmek için alt kümenin topolojisinin anlaşılması gerekir. Örnek olarak, bir bilgisayar ağında farklı işletim sistemleri olan bilgisayar alt kümeleri, farklı özelliklerinden dolayı herhangi bir virüse karşı farklı tepki göstereceklerdir. Yerel kümelenmelerin anlaşılması, gerektiğinde alt kümenin bilgisayar ağına entegre edilebilmesi için düğümün kümelenme katsayısı, kümelenme derecesini ölçmek için bir metot olarak kullanılabilir. Herhangi bir ağ sistemi için yüksek kümelenme katsayısı o ağ sisteminde small world fenomeni için bir göstergedir.   

Small world ağ sistemleri. Herkesin bildiği basit bir sosyal olay ile başlayayım. Birçok insan hayran olduğu ünlü bir kişiye ulaşmak ister ve bu kişi ile temas kurabilmek için örneğin, ünlü kişi ile yakınlığı olan potansiyel arkadaşlarından yardım ister. Ünlü kişi ile bağlantı kurabilecek arkadaşlarına ulaşmak zaman ve maliyet açısından değerlendirildiğinde elbette farklılıklar olacaktır. Bazı arkadaşlarına ulaşması kolaydır, bazılarına ulaşmak yorucu olabilir veya bazıları başka bağlantıları (arkadaşının arkadaşı) tavsiye edebilir. Sonuçta, ünlü kişi ile bağlantı kurmak maliyetli ve yorucu olabilir. Oysaki ünlü kişiye ulaşmanın çok daha kolay olduğu, matematik olarak ağ teorisi ile gösterildi. İki uygulamalı matematikçi Duncan Watts (aynı zamanda sosyolog) ve Steven Strogatz 1998 yılında yayınladıkları makalede, birbiriyle ilgisi olmayan üç ayrı gerçek dünya örneği ile bir deney tasarladılar.

  1. Film aktörleri: Her bir aktör düğüm olsun. İki düğüm arası bağlantı olması için iki aktörün birlikte aynı filmde rol alması gerekir.
  2. Elektrik şebekesi: Her bir eleman (jeneratör, trafo, ara istasyon) düğüm olsun. İki düğüm arasında bağlantı olması için, herhangi iki düğümün transmisyon hattı ile bağlı olması gerekir.
  3. C. Elegans: Bilim insanlarının nöronlarını haritaladığı ilkel bir solucan. Her bir nöron düğüm olsun. İki düğüm arası bağlantı için iki nöronun sinapslarla bağlantılı olması gerekir.

Watts ve Strogatz, birbiriyle ilgisi olmayan bu örneklerin ortak yanı olup olmadığını araştırdıklarında small world denilen ortak bir özelliğin olduğunu keşfettiler, en kısa yol özelliği. Şekil 1’de soldaki daire üzerinde dizili düğümlerin her biri iki komşu düğüm ile bağlantılıdır. Çeşitli bağlantılar sonunda yapılan hesaplamaya göre hem düğümler arası en kısa yol hem de yerel kümeleşme yüksek şekilde gözlendi. 

 


Şekil 1. Watt-Strogatz modeli. Soldaki yapı YL YC, ortadaki yapı “small world” DL YC, sağdaki yapı DL DC  (Y, yüksek; D, düşük; C, kümelenme, L, en kısa yol).

Sağdaki yapı düğümlerinin her biri rastgele seçilen iki düğüm ile bağlantılıdır. Çeşitli bağlantılar sonunda yapılan hesaplamaya göre hem düğümler arası en kısa yol (shortest path length) hem de local kümeleşme (clustering) çok düşük. Ortadaki yapı ise Watts-Strogatz’ın üç ayrı gerçek dünya örneği ile elde edilen sonuçlar. Bu sonuçlara göre gerçek dünya fenomenleri her zaman en kısa yol ve yüksek yerel kümelenme özellikleri taşıyarak evreni daha gerçekçi açıklıyor. Watts ve Strogatz’ın deneyinden sonra “small world” fenomeni sayesinde bilim insanları araştırmalarına inter-disipliner yaklaşmaya başladılar. 

Üstellik yasası ağ yapıları. Şekil 2, düğümleri rastgele bağlantılı, yani düğüm derecesi birbirine yakın olan düğümlerden oluşan benzeşik (random) bağlantılı bir ağ sistemi gösteriyor. Rastgele düğüm bağlantıları olan bu tür sistemlerin davranışı normal (gauss) dağılımı ile gösterilir. Düğümlerin çoğunun derece dağılımı ortalama olduğundan çan eğrisinin ortalarında yer alırlar. Sağ ya da sol eteklere doğru (standart sapma arttığından) düşük dereceli dağılımlar gözlenir. Şekil 3.

 


Şekil 2. Normal dağılım gösteren bir başka ağ dağılımı.


 


Şekil 3. Düşük dereceli düğüm bağlantıları eteklerde gözlenir.


Şekil.4.’de nüfus dağılımını gösteren farklı bir ağ yapısı görülmektedir. Birçok düğüm bağlantılı ama düşük dereceli olan ortadaki küme (hub) daha az düğüm bağlantılı olmasına rağmen daha yüksek dereceli birçok popülasyon grubuna (küçük hub) bağlıdır ve her bir bağlantı daha küçük kümeleşmelerle ilişki sağlar. Bu ağ yapısının davranışı Şekil 5.’de gösterildiği gibi uzun kuyruk (long tail) dağılımı şeklindedir. Bu dağılımın enteresan özellikleri vardır. Yatay eksen ile gösterilen düğüm derecesinin kuyruğuna doğru azalan değerlerin küçük bir kısmı tekrar ölçeklendiğinde elde edilen yeni dağılım şekil olarak benzerdir. Ölçeklendirmeye tekrar tekrar devam edilirse dağılımın kuyruğu sonsuza kadar devam eder. Bu özelliğe sahip ağ sistemleri long tail ağ sistemleri olarak da adlandırılırlar. Ayrıca, hatırlayınız, fraktal yapıların küçük bir bölümü ele alınıp büyütüldüğünde, boyut simetrisi nedeniyle, kendine benzeyen orijinal yapıyla karşılaşırız. Bu anlamda boyut dönüşümüne simetrik olan bu tür (scale-free) ağ yapılarında derece dağılımı ölçekten bağımsızdır, üstellik yasasına tabi olan ağ yapılarıdır. Şekil 4’de scale-free ağ sisteminini yapısı fraktal görünüşlüdür. Ortadaki merkezi düğüm, gelen ve giden birçok bağlantı ile daha küçük, uzak merkezli düğümlerde farklı derecede tekrarlanıyor. Gerçek dünya fenomenleri scale-free sistemlere çok benzer davranırlar. Scale-free sistemler aynı zamanda small world özelliği gösterirler, yani yapılarında en kısa yol uzunluğu ve yüksek kümelenme gözlenir.  

 


Şekil 4. Üstellik yasası özelliği gösteren ağ yapısı.



    











Şekil 5. Uzun kuyruk  (long tail) dağılımı.


1999 yılında Albert Barabasi ve Reka Albert’in yayınladıkları “Emergence of Scaling in Random Networks” başlıklı makale bilim çevresinde çok ses getirmişti. Makalenin özünde, scale-free derece dağılımının gerçek dünya fenomenlerinde çok yaygın olduğu anlatılıyordu. Bu makalenin içeriği birçok olumsuz değerlendirmeye muhatap olmakla birlikte genel olarak gerçek dünya fenomenlerin çoğu normal dağılımdan ziyade scale-free (long tail) dağılımı gösterir (x-ekseninin sol tarafında çok sayıda bağlantılı ama düşük frekanslı sağ tarafında ise az bağlantılı ama yüksek frekanslı düğüm vardır). 

Google arama motoru üstellik yasasına göre davranan sistemler için iyi bir örnektir. Google, arama penceresindeki her soruya açıklayıcı bir cevap sergiler. Bunun için internet üzerindeki her bir web sayfasını kriterlere göre (web sayfasının yaşı, anahtar kelimenin sayfa içinde tekrarı gibi) algoritma aracılığı ile sıralandırır. Bu sıralanmada üste çıkmak için en önemli ölçüt web sayfasının tıklanma sıklığıdır. Google’ın ağ yapısı rastgelelik, yani çan eğrisinin normal dağılım özelliğini gösterseydi sayfaların derecelendirilmesi mümkün olmazdı. Web sayfasının tıklanması için merkezi bir kontrol olmadığını biliyoruz, her şey kendiliğinden yapılanır ve ortaya scale-free sistem özelliği çıkar. Google, yakın tarihte anlaşılan bu özelliği çok başarılı şekilde kullanıyor. 

Sistemin üstellik yasası özelliğinin kendiliğinden nasıl ortaya çıktığı merak edilebilir. Gerçekten, web bağlantıları birisi tarafından tasarlanmadıysa nasıl bu günkü durumuna erişti? Birçok hipotez ileri sürülüyor ama en fazla kabul göreni tercihli bağlantı diyebileceğim preferential attachment kavramı. Yeni oluşturulan bir web sitesi ya da sayfasının diğer bir siteye bağlantısında çok bağlantılı popüler siteler tercih edilir. Ünlü kişilere ait popüler siteler yeni bağlantılar anlamında bağlantısı düşük sitelere göre daha avantajlıdır, “zengini daha zengin” yapan politik sistemler gibi, büyümeleri daha kolay ve hızlı olacaktır, Web sitesinin tasarımı gibi basit bir modelleme ile oluşan karmaşık yapıları gerçek dünya fenomenlerinde her zaman görüyoruz. 

Ateşan Aybars (11 Mayıs 2021)

___________________________

1 https://youtu.be/r7uY4HZghFQ . Introduction to Complexity: Network Terminology Part 2


2Complexity A Guided Tour, Kindle edition s. 236, 237, 238. Melanie Mitchell.  


3 https://youtu.be/cOKaqzk1iBM. Introduction to Complexity: Small-World Networks Part 1


Hiç yorum yok:

Yorum Gönder