Geri Dön

Influence maximization based on partial network structure information: A comparative analysis on seed selection heuristics

Ağ yapısı üzerinde kısmi bilgi kullanarak etki eniyilemesi: Çekirdek küme seçimi sezgiselleri üzerine karşılaştırmalı bir çözümleme

  1. Tez No: 459439
  2. Yazar: ŞİRAG ERKOL
  3. Danışmanlar: DOÇ. DR. GÖNENÇ YÜCEL
  4. Tez Türü: Yüksek Lisans
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2016
  8. Dil: İngilizce
  9. Üniversite: Boğaziçi Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 92

Özet

Bu çalışmada çekirdek küme seçimi problemi incelendi. Bu probleme temel olarak eniyileme yaklaşımı uygulanmıştır ve bu yaklaşımın NP-zor olduğu kanıtlanmıştır. Birçok kaynak bu probleme algoritmik sezgisellerle yaklaşmıştır. Bu yaklaşımlardaki temel amaç hesaplama karışıklığını azaltırken çözümlerin hata payının artışını en düşük seviyede tutmaktır. Algoritmik sezgisellerin hata payı düşük, hesaplama karmaşıklıkları yüksektir. Ayrıca kaynakların çoğunda ağların yapısı ve özellikleri hakkında tüm bilgiye sahip olunduğu varsayılmıştır ancak durum genelde bu şekilde değildir. Bu çalışma için bir benzetim modeli kuruldu. Kurulan model, ağları oluşturma, çekirdek küme seçimini yapabilme ve yayılım modellerinin benzetimini gerçekleştirebilmektedir. Ağ üzerine kısmi bilgi kullanan yeni ve ölçüt temelli sezgiseller oluşturuldu ve benzetim modeli kullanılarak test edildi. Bu sezgiseller, sentetik olarak üretilmiş ağlardaki elemanları ve onlarda var olan yerel bilgileri kullandı. Sezgisellerin performansları üç farklı ağ tipi ve iki farklı yayılım modeli, yani altı kombinasyon üzerinde karşılaştırmalı olarak analiz edildi. Sonuçlar, sezgisellerin performanslarının ağ yapılarına bağlı olduğunu göstermektedir. Bir ağ üzerinde kullanılacak sezgisel, ağın özellikleri incelendikten sonra seçilmelidir. Ayrıca, kısmi bilgi yaklaşımıyla umut verici sonuçlar elde edildi. Kısmi bilgi kullanan sezgiseller, birçok yerde tam bilgi kullanan sezgisellerin performanslarına yakınsadılar.

Özet (Çeviri)

In this study, the problem of seed selection is investigated. This problem is mainly treated as an optimization problem, which is proved to be NP-hard. There are several heuristic approaches in the literature which mostly use algorithmic heuristics. These approaches mainly focus on the trade-off between computational complexity and accuracy. Although the accuracy of algorithmic heuristics are high, they also have a high computational complexity. Furthermore, in the literature it is generally assumed that complete information on the structure and features of a network is available, which is not the case in most of the times. For the study, a simulation model is constructed, which is capable of creating networks, performing seed selection heuristics, and simulating diffusion models. Novel metric-based seed selection heuristics that rely on partial information are proposed and tested using the simulation model. These heuristics use local information available from nodes in the synthetically created networks. The performances of heuristics are comparatively analyzed on three different networks and two different diffusion models, i.e. six combinations. The results suggest that the performance of a heuristic depends on the structure of a network. A heuristic to be used should be selected after investigating the properties of the network at hand. Also, the approach of partial information provided promising results. It has approximated to the performances of heuristics relying on complete information in most of the cases.

Benzer Tezler

  1. Kömür ve biyokütle karışımlarının gazlaştırılması ve aspen HYSYS programı ile simulasyonu

    Coal and biomass gasification and simulation of gasification systems using aspen HYSYS program

    TANJU NAYIR

    Yüksek Lisans

    Türkçe

    Türkçe

    2012

    Enerjiİstanbul Teknik Üniversitesi

    Makine Mühendisliği Ana Bilim Dalı

    DOÇ. DR. ERHAN BÖKE

  2. Kaynak kısıtlı proje programlama problemlerinin çözümü için yeni yöntem ve algoritmalar

    New methods and algorithms for solving the resource-constrained project scheduling problem

    İHSAN UĞUR

    Doktora

    Türkçe

    Türkçe

    1987

    İşletmeİstanbul Teknik Üniversitesi

    PROF.DR. ATAÇ SOYSAL

  3. Targeted and budgeted influence maximization in social networks under deterministic linear threshold model

    Sosyal ağlarda belirlenimci doğrusal eşik modeli altında hedefli ve bütçeli etki enbüyükleme

    FURKAN GÜRSOY

    Yüksek Lisans

    İngilizce

    İngilizce

    2017

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Şehir Üniversitesi

    Veri Bilimi Ana Bilim Dalı

    YRD. DOÇ. DR. DİLEK GÜNNEÇ DANIŞ

  4. Karasal, hava ve uzay tabanlı haberleşme sistemleri arasındaki girişimin minimizasyonu

    Minimization of the interference between terrestrial, air and space based communication systems

    CİHAN AYDIN

    Yüksek Lisans

    Türkçe

    Türkçe

    2014

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    İletişim Sistemleri Ana Bilim Dalı

    PROF. DR. MURAT TAYFUN GÜNEL

  5. Longitudinal and survival statistical methods with applications in renal medicine

    Böbek tıbbı uygulamaları ile boylamsal ve sağkalım istatistiksel yöntemler

    ÖZGÜR ASAR

    Doktora

    İngilizce

    İngilizce

    2015

    BiyoistatistikLancaster University

    Tıp Bilimleri Ana Bilim Dalı

    PROF. PETER JOHN DIGGLE