BİLDİRİ DETAY

Zeynep Nihan BERBERLER
AĞ ZEDELENEBİLİRLİK ÖLÇÜMLERİNİN KARMAŞIKLIK ANALİZİ
 
Giriş: Karmaşık ağlar, doğada ve toplumda bulunan çeşitli sistemleri modellemek için kullanılır. Sosyal ağlar, iletişim ağları, internet, biyolojik ağlar, yapay sinir ağları, kimyasal ağlar karmaşık ağlar için birer örnektir. Karmaşık ağların çalışılması, bilgisayar bilimleri, fizik, matematik, biyoloji, sosyal bilimler, enformatik ve diğer teorik ve uygulamalı bilimleri içeren çok disiplinli araştırmanın önemli bir alanıdır. Merkezler ve bu merkezleri birbirine bağlayan hatlardan oluşan bir ağın dayanıklılığı ağ tasarımcıları için oldukça önemlidir. Zedelenebilirlik ölçümleri ağ dayanıklılığının belirlenmesi için oldukça önemlidir. Bir ağın zedelenebilirliği, ağa temel teşkil eden çizgenin genel sağlamlığının bir ölçümüdür. Ağların dayanıklılığının ölçülmesi için çok sayıda farklı zedelenebilirlik ölçümü tanımlanmıştır. Connectivity (bağlantılılık sayısı), bilinen en eski zedelenebilirlik ölçümü olup hem tepe hem de ayrıt versiyonu mevcuttur. Bir çizgenin bağlantılılık sayısı polinom zamanda hesaplanabilen bir değerdir. Bu parametre ağın bozulması için minimum maliyeti verir ancak bozulmadan sonra geriye kalan yapının durumunu dikkate almaması bu parametreyle ilgili önemli bir dezavantajdır. Bu dezavantaj dikkate alınarak sonrasında integrity, toughness, tenacity, scattering sayısı, rupture derecesi gibi çeşitli zedelenebilirlik ölçümleri tanımlanmıştır. Bu ölçümlerin de tepe ve ayrıt versiyonları mevcuttur. Connectivity (bağlantılılık sayısı) parametresinin aksine, bu ölçümler hem ağdaki bozulmanın maliyetini hem de ağda meydana gelen hasarın boyutunu analiz eder. Tüm bu parametreler, ağa temel teşkil eden çizgenin bağlantısız kalması durumunda ölçüme uygundur. Algoritmik hesaplama açısından ele alındığında, genel çizgelerin bu parametreler kullanılarak zedelenebilirlik değerlerinin belirlenmesi NP-tam sınıftandır. Dolayısıyla, bu durum tüm bu ölçümlerin karmaşık ağlar için kullanılmasının etkin olmadığının bir göstergesidir. Aynı tepe sayısına fakat farklı ayrıt sayısına sahip olan veya benzer şekilde aynı ayrıt sayısına fakat farklı tepe sayısına sahip olan farklı çizgelerin bilinen bu ölçümlerle zedelenebilirlik değerleri ölçülmüş ve bazı çizgelerde aynı değerlerin elde edildiği görülmüştür. Dolayısıyla, iki farklı çizgenin zedelenebilirliğinin ölçülerek hangisinin daha dayanıklı bir ağ topolojisi olduğunu belirlemek için mevcut ölçümlerden daha hassas bir ölçüme ihtiyaç duyulmuş ve çizgelerde uzaklık kavramı temel alınarak residual closeness parametresi tanımlanmıştır. Residual closeness, çizgedeki her bir tepeyi veya her bir ayrıtı diğerlerinden bağımsız olarak ele alarak geriye kalan yapının bağlantısız olma şartı olmaksızın ölçüm yapan bir parametredir. Residual closeness, tüm çizgeler için polinom zamanda hesaplanabilen bir parametredir. Dolayısıyla, bu parametre karmaşık ağlar için etkin bir kullanım sağlar. Residual closeness parametresinin hem tepe hem de ayrıt versiyonunun hesaplanması için Floyd-Warshall algoritması kullanılarak tasarlanmış polinom zamanlı algoritmalar mevcuttur. Amaç: Residual closeness parametresinin ağırlıksız, yönlendirilmemiş, bukle ve katlı ayrıt içermeyen basit çizgeler için tanımlanan bir ölçüm olduğu göz önüne alınarak, bu parametrenin hem tepe hem de ayrıt versiyonu için iki yeni polinom zamanlı algoritma tasarlanmıştır. Kapsam: Algoritmalar, tüm basit çizgeler üzerinde sonuç verecek şekilde tasarlanmıştır. Yöntem: Bu algoritmaların tasarımı için karmaşıklık mertebeleri Floyd-Warshall algoritmasından daha düşük olan çizge üzerinde dolaşma algoritmalarından yararlanılmıştır. Araştırmanın Problemi: Çizge üzerinde dolaşma yöntemlerinden yararlanılarak, literatürde mevcut olan polinom zamanlı algoritmalardan daha etkin olarak çalışan yeni algoritma tasarımları üzerinde çalışılmıştır. Araştırmanın Kısıtları: Üzerinde çalışılan çizge sınıfı, ağırlıksız, yönlendirilmemiş, bukle ve katlı ayrıt içermeyen basit çizgelere aittir. Bulgular: Tasarlanan yeni algoritmaların zaman karmaşıklıklarının O asimptotik notasyonu cinsinden mevcut algoritmaların karmaşıklıklarından daha az olduğu belirlenmiştir. Sonuç: Residual closeness parametresinin tasarlanan yeni algoritmalarla ölçümünün, bu parametrenin karmaşık ağların zedelenebilirliğinin belirlenmesinde, hem ağlar arasında ayırt edicilik özelliği hem de polinom zamanlı düşük karmaşıklık mertebesi ile oldukça etkin bir kullanım sağladığı belirtilmiştir.

Anahtar Kelimeler: Karmaşık Ağlar, Zedelenebilirlik, Algoritma Tasarımı, Çizge Algoritmaları



 


Keywords: