Geri Dön

Ağlarda kritik tepe tespiti problemleri üzerine

On the critical node detection problems in networks

  1. Tez No: 828211
  2. Yazar: YEŞİM AYGÜL
  3. Danışmanlar: PROF. DR. URFAT NURİYEV, DR. ÖĞR. ÜYESİ ONUR UĞURLU
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Matematik, Computer Engineering and Computer Science and Control, Mathematics
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2023
  8. Dil: Türkçe
  9. Üniversite: Ege Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Matematik Ana Bilim Dalı
  12. Bilim Dalı: Bilgisayar Bilimleri Bilim Dalı
  13. Sayfa Sayısı: 83

Özet

Doğadaki çok sayıda sistem, bağlantılar (ayrıtlar) aracılığıyla birbirleri ile etkileşime giren elemanlardan (tepeler) oluşan ağ yapıları ile tanımlanabilmektedir. Ağlardaki bazı tepeler diğerlerinden daha büyük öneme sahiptir. Özellikle ağ bağlantılılığı için önemli olan tepelerin bulunması ağ analizinde en çok çalışılan problemlerdir. Bu tepeler Graf Teorisi literatüründe“Kritik Tepeler”olarak bilinmektedir. Kritik Tepe Tespiti Problemleri, ön tanımlı bazı bağlantılılık metriklere göre silinmesiyle ağın bağlantılılığına en çok zarar veren tepelerin kümesini bulmayı hedefleyen optimizasyon problemleridir. Problemin ele alınan farklı bağlantılılık metriklerine göre birçok varyantı mevcuttur. Bu tezde, NP-Zor karmaşıklık sınıfında yer alan kritik tepe tespiti problemi varyantlarından“Bağlantılı Bileşenlerin Sayısının Enbüyüklenmesi (MaxNum)”ve“En Büyük Bağlantılı Bileşenin Enküçüklenmesi (MinMaxC)”problemleri çalışılmıştır. Tez kapsamında, MaxNum ve MinMaxC problemleri için birer algoritma geliştirilip C programlama dilinde kodlanmıştır. Geliştirilen algoritmaların performansları literatürdeki veri setleri üzerinde geleneksel merkeziyet ölçütleri ile kıyaslanarak test edilmiştir. Tezde elde edilen hesapsal sonuçlar geliştirilen algoritmaların özellikle gerçek hayat ağları üzerinde merkeziyet ölçütlerine göre daha iyi performans sergiledikleri göstermektedir.

Özet (Çeviri)

Numerous systems in nature can be described by network structures consisting of elements (vertices/nodes) interacting with each other through connections (edges). Some nodes in networks are of greater importance than others. Finding the nodes that are essential for network connectivity is one of the most studied problems in network analysis. These nodes are called“Critical Nodes”in the Graph Theory literature. Critical Node Detection Problems are optimization problems that aim to find the nodes whose removal cause the most damage to network connectivity according to predefined connectivity metrics. The problem has many variants according to the considered connectivity metrics. In this thesis, two critical node detection variants, the“Maximization of the Number of Connected Components (MaxNum)”and“Minimization of the Largest Connected Component (MinMaxC)”problems, which are NP-Hard, are studied. Within the scope of the thesis, new algorithms for MaxNum and MinMaxC problems were developed and coded in C programming language. The performances of the developed algorithms were tested on the data sets in the literature by comparing them with traditional centrality measures. The computational results show that the developed algorithms perform better than the centrality measures, especially on real-life networks.

Benzer Tezler

  1. Age of information-oriented comparative evaluation of channel access mechanisms in multi-rate wireless lans

    Çoklu-hızlı kablosuz yerel ağlarda kanal erişim mekanizmalarının bilginin yaşı odaklı karşılaştırılmasının değerlendirilmesi

    UMUT UTKU ERDEM

    Yüksek Lisans

    İngilizce

    İngilizce

    2023

    Elektrik ve Elektronik Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

    Elektrik ve Elektronik Mühendisliği Ana Bilim Dalı

    PROF. DR. EZHAN KARAŞAN

    PROF. DR. NAİL AKAR

  2. Bilişim sistemlerindeki gelişmelerin işletme yönetimine etkileri, yönetim bilişim sistemleri geliştirme ve bir uygulama örneği

    Effects of the evoluation of information systems on management, management information systems development and an example of its application

    ZUHAL TANRIKULU

    Doktora

    Türkçe

    Türkçe

    1999

    İşletmeİstanbul Üniversitesi

    Organizasyon ve İşletme Politikaları Ana Bilim Dalı

    PROF. DR. EROL EREN

  3. Gizli anahtar şifrelemesi kullanan sualtı akustik algılayıcı ağlarda kritik düğümlerin ağ yaşam süresine etkilerinin özgün bir eniyileme çerçevesi tasarlanarak irdelenmesi

    Design of a novel optimization framework for the analysis of the impact of critical nodes on network lifetime of underwater acoustic sensor networks utilizing private key cryptography

    BURAK EMRE ÜN

    Yüksek Lisans

    Türkçe

    Türkçe

    2022

    Elektrik ve Elektronik MühendisliğiTOBB Ekonomi ve Teknoloji Üniversitesi

    Elektrik ve Elektronik Mühendisliği Ana Bilim Dalı

    PROF. DR. BÜLENT TAVLI

    DOÇ. DR. HÜSEYİN UĞUR YILDIZ

  4. RSS based indoor localization in a reconfigurable intelligent surface assisted system

    Yeniden yapılandırılabilir akıllı yüzey destekli sistemde RSS tabanlı iç mekan konumlandırma

    KÜBRA KİBAR DOĞAN

    Yüksek Lisans

    İngilizce

    İngilizce

    2023

    Elektrik ve Elektronik MühendisliğiGazi Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ ÖZGÜR ERGÜL

  5. Kablosuz algılayıcı ağlarda ağ yaşam süresinin matematiksel programlama ile incelenmesi

    Analyzing network lifetime of wireless sensor networks with mathematical programming

    HÜSEYİN ÇOTUK

    Doktora

    Türkçe

    Türkçe

    2013

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolTOBB Ekonomi ve Teknoloji Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. KEMAL BIÇAKCI

    DOÇ. DR. BÜLENT TAVLI