Büyük ölçekli ağlar için polinom zamanlı kritik düğüm tespiti algoritması

Authors : Onur Uğurlu, Yeşim Aygül

Pages : 516-532

Doi:10.17714/gumusfenbil.1569247

View : 66 | Download : 37

Publication Date : 2025-06-15

Article Type : Research Paper

Abstract :Ağlar, karmaşık sistemlerin modellenmesinde ve analiz edilmesinde kritik bir rol oynar; bu nedenle ağ analizleri hem sosyal hem de teknolojik sistemlerde önemli veriler sağlar. Bu çalışmada, ağlardaki kritik düğümleri tespit etmeyi amaçlayan Kritik Düğüm Problemi (KDP) ele alınmıştır. KDP, bir ağdaki ikili bağlantılılığı minimize eden düğümlerin bulunmasını amaçlayan bir problemdir. Başka bir deyişle, KDP, silinmesiyle ağı benzer boyutlarda çok sayıda segmente bölen düğüm kümesini bulmayı hedefler. Bu problem, sosyal ağlardan biyolojik sistemlere, telekomünikasyon ağlarından kablosuz çok sekmeli ağlara kadar birçok alanda önemli uygulamalara sahiptir. KDP, NP-Zor bir problem olduğundan büyük ölçekli ağlarda optimale yakın etkin çözümlerin bulunması için polinom zamanlı algoritmalara ihtiyaç duyulmaktadır. Bu çalışmanın temel motivasyonu, özellikle büyük ölçekli ağlar üzerinde optimale yakın çözümler bulabilecek polinom zamanlı bir algoritma geliştirmektir. Çalışmada önerilen TrimCut algoritması, ağın dayanıklılığını azaltan kritik düğümleri belirlemek için üç aşamalı bir süreç kullanmaktadır. İlk aşamada, ağdan yüksek dereceli düğümler çıkarılarak ağ seyreltilir, ardından ikinci aşamada Derinlik Öncelikli Arama ağacı ile kesim düğümleri tespit edilir. Son aşamada ise ağdaki kritik düğümler tespit edilir. Önerilen algoritmanın performansı, literatürdeki mevcut algoritmalarla karşılaştırılmıştır. Hesaplamalı deneyler, TrimCut algoritmasının mevcut kütüphane örnekleri üzerindeki hata oranının %6’nın altında olduğunu ve büyük ölçekli ağlarda kaliteli çözümler bulabildiğini göstermektedir.
Keywords : Ağ analizi, Kritik düğümler, Polinom zamanlı algoritmalar

ORIGINAL ARTICLE URL