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
- Tez No: 459439
- Danışmanlar: DOÇ. DR. GÖNENÇ YÜCEL
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2016
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- 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
- 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
2012
Enerjiİstanbul Teknik ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
DOÇ. DR. ERHAN BÖKE
- 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
- 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
2017
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Şehir ÜniversitesiVeri Bilimi Ana Bilim Dalı
YRD. DOÇ. DR. DİLEK GÜNNEÇ DANIŞ
- 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
2014
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesiİletişim Sistemleri Ana Bilim Dalı
PROF. DR. MURAT TAYFUN GÜNEL
- 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
2015
BiyoistatistikLancaster UniversityTıp Bilimleri Ana Bilim Dalı
PROF. PETER JOHN DIGGLE