Büyük ölçekli ağlar için polinom zamanlı kritik düğüm tespiti algoritması
A polynomial-time algorithm for critical node detection in large-scale networks
Yazar: Uğurlu, Onur; Aygül, Yeşim
Dergi: Gümüşhane Üniversitesi Fen Bilimleri Dergisi, Vol. 15 No. 2, 2024
Anahtar kelimeler: Algorithms and Calculation Theory ; Algoritmalar ve Hesaplama Kuramı ; Network analysis,Critical nodes,Polynomial-time algorithms ; Ağ analizi,Kritik düğümler,Polinom zamanlı algoritmalar

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.

Networks play a crucial role in modeling and analyzing complex systems, providing valuable data in both social and technological systems. This study addresses the Critical Node Problem (CNP), which aims to identify critical nodes within networks. CNP seeks to find the nodes whose removal minimizes pairwise connectivity in the network. In other words, CNP aims to identify a set of nodes whose deletion fragments the network into several segments of similar size. This problem has significant applications in various fields, ranging from social networks to biological systems, from telecommunication networks to wireless multi-hop networks. As CNP is an NP-Hard problem, developing polynomial-time algorithms is essential to find efficient solutions for large-scale networks. The primary motivation of this study is to develop a polynomial-time algorithm capable of finding near-optimal solutions, particularly for large-scale networks. The proposed TrimCut algorithm employs a three-stage process to identify critical nodes that reduce network resilience. In the first stage, the network is sparsified by removing high-degree nodes. Then, in the second stage, a Depth-First Search (DFS) tree is used to detect cut nodes. Finally, in the last stage, the critical nodes in the network are identified. The performance of the proposed algorithm has been compared with existing algorithms in the literature. Computational experiments demonstrate that the TrimCut algorithm achieves an error rate below 6% on standard benchmark networks and provides high-quality solutions for large-scale networks.