Minimum hakim küme problemi için yeni bir yaklaşım: Malatya merkezilik metrikleri ile üç aşamalı bir çözüm

Abstract

Minimum Hâkim Küme (MDS) problemi, çeşitli alanlara yayılan uygulamalarla graf teorisinde temel bir zorluktur. Bu çalışma, sürecin her aşamasında çözümler üreten MDS problemini çözmek için yeni bir üç aşamalı yaklaşım sunmaktadır. Üç temel birbirine bağlı Malatya merkezilik metodolojisinden yararlanan yaklaşım, bir dizi problem ölçeğinde MDS'yi ele almanın etkili bir yolunu sunar. Bu merkezilik metrikleri, hedef düğümün komşularıyla olan merkeziliğini yakalar. Algoritma, ilk yinelemelerde yüksek baskınlığa ve kümelenmeye sahip düğümlere öncelik verir ve daha düşük kümelenmeye sahip olanları sonraki aşamalarda kademeli olarak baskın kümeye dahil eder. Dikkat çekici bir şekilde, işlem maliyeti erken yinelemelerde daha yüksekken sonraki yinelemelerde azalır. Ampirik değerlendirme, belirli bir yaklaşımla oluşturulan sentetik veri kümelerini, Erdös-Renyi modeli kullanılarak hazırlanmış örnekleri ve ağ bilimi uygulamalarından alınan otantik veri kümelerini kapsayan çeşitli problem senaryolarını kapsar. İnceleme sonucunda önerilen algoritmanın çeşitli kısıtlamalar arasında tutarlı bir şekilde sağlam çözümler ürettiği ortaya çıkar. Çoğu durumda, önerilen yöntemlerin performansı mevcut ilgili algoritmaların performansını aşar. Bu çalışmanın bulguları, MDS problem çözme tekniklerinin gelişen manzarasına katkıda bulunarak, ağ tasarımı, kaynak tahsisi ve ötesinde gelecekteki araştırmalar ve pratik uygulamalar için umut verici yollara dair içgörüler sunar.