Leader-follower games for influence spread in social networks
Sosyal ağlarda etki yayılımına yönelik öncü-izleyici oyunları
- Tez No: 643179
- Danışmanlar: PROF. DR. MUSTAFA NECATİ ARAS, PROF. DR. İSMAİL KUBAN ALTINEL
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2020
- 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ı: Endüstri Mühendisliği Bilim Dalı
- Sayfa Sayısı: 200
Özet
Etki Enbüyükleme Problemi, bir sosyal ağ üzerinde etki/bilgi yayılımını başlattık-larında mümkün olan en yüksek sayıda kişinin etkilenmesine yol açacak bir dizi kişinin, yani bir çekirdek kümesinin bulunmasını içerir. Bu tezde, iki oyuncunun bir Stackelberg oyunu biçiminde sırayla karar verdiği, Etki Enbüyükleme probleminin iki rekabetçi türü tanıtılmıştır. Etkisizleştirme Durumunda Etki Enbüyükleme probleminde öncünün ve izleyicinin amaçları, sırasıyla yayılımın enbüyüklenmesi ve enküçüklenmesidir. Yanlış Bilgi Yayılımı Enküçükleme problemi tam tersi bir durumu ele alırken, her iki problemde de öncü kendi kararında izleyicinin eniyi karşılığını hesaba katar. Her iki problem de, yaygın olarak kullanılan Doğrusal Eşik modelinden kaynaklanan yayılım senaryoları numaralandırılarak, alt düzeyi iki aşamalı stokastik program olan bir iki düzeyli karışık tamsayılı doğrusal program olarak gösterimlenmiştir. Çözüm aşamasında ilk olarak, izleyicinin eniyi kararlarının Örneklem Ortalaması Yaklaştırma yöntemi ile bulunduğu matsezgisel yöntemler önerilmiştir. Yanlış Bilgi Yayılımı Enküçüklemesi için, geliştirilen algoritmalarla gelişmiş bir etki enbüyükleme yöntemi bütünleştirilmiştir. Önerilen yöntemler, tam birerleme yoluyla eniyi çözümün bulunabileceği küçük örnekle-rin yanı sıra algoritmaların birbirleriyle karşılaştırıldığı daha büyük örnekler yardımıyla da değerlendirilmiştir. Daha sonra, iki düzeyli karışık tamsayılı doğrusal programlama problemleri için bir dal-kesme algoritması, Etkisizleştirme Durumunda Etki Enbüyükle-mesi için bilgisayısal etkinliği arttırdığı gösterilen değişken sınır güncelleme yaklaşımıyla zenginleştirilmiştir. İki düzeyli saldırı problemleri için kesin (eniyi) çözüm veren bir algoritma önemli ölçüde geliştirilmiş ve Yanlış Bilgi Yayılımı Enküçükleme problemini de içeren çeşitli problem türleri üzerinde denenerek daha iyi sonuçlar verdiği gösterilmiştir.
Özet (Çeviri)
Influence Maximization Problem involves finding a set of individuals in a social network to trigger an influence/information spread, i.e., a seed set, such that the maximum possible number of individuals are influenced. In this thesis, two competitive variants of the Influence Maximization Problem where two players make decisions sequentially in the form of a Stackelberg game are introduced. In the Influence Maximization with Deactivation the objectives of the leader and the follower are maximization and minimization of the spread, respectively. While the Misinformation Spread Minimization Problem has a reverse situation, in both problems the leader takes the follower's optimal response into account. Both problems are formulated as mixed-integer bilevel linear programs with a two-stage stochastic program in the lower level, by enumerating the diffusion scenarios due to the well known Linear Threshold model. In the solution phase, firstly several matheuristic methods are proposed where the follower's optimal decisions are approximated via Sample Average Approximation method. For the MSMP, additionally a state-of-the art influence maximization method is integrated into the developed algorithms. The proposed methods are evaluated on small instances where an optimal solution can be found via complete enumeration as well as larger instances where the algorithms are compared to each other. Then, a branch-and-cut algorithm for mixed-integer bilevel problems is enriched with a variable bound update procedure for the Influence Maximization with Deactivation which is shown to increase the time efficiency. An exact algorithm for bilevel interdiction problems is improved substantially, tested on various problem types including the Misinformation Spread Minimization Problem and yields significantly better results.
Benzer Tezler
- Toplum ve moda etkileşimi
Başlık çevirisi yok
MAKBULE SEMA ÜŞENMEZ
Doktora
Türkçe
1992
SosyolojiMimar Sinan Güzel Sanatlar ÜniversitesiSosyoloji Ana Bilim Dalı
PROF. DR. M. NEVRES TURHAN
- The Participatory Theater Framework of Leadership
Liderlik için Katılımcı Tiyatro Modeli
AYBİKE MUTLUER MERGEN
- Avrupa Birliği'nde ve Türkiye'de Laisizmin değerlendirilmesi
The evaluation of Laisizm in European Union and in Turkey
HALUK DEMİRBULAK
Yüksek Lisans
Türkçe
2007
Siyasal Bilimlerİstanbul ÜniversitesiAvrupa Birliği Ana Bilim Dalı
PROF. DR. HÜLYA BAYKAL
- Type-2 fuzzy logic based linguistic pursuing strategy design with a real world application
Gerçek zamanlı bir uygulama ile tip-2 bulanık mantık tabanlı dilsel kovalama strateji tasarımı
AYKUT BEKE
Yüksek Lisans
İngilizce
2018
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiKontrol ve Otomasyon Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ TUFAN KUMBASAR
- Eyüp Semtinde 18. ve 19. yüzyıl Osmanlı devri anıtsal mimarisi
18 Th. and 19 Th. century Ottoman monumental architecture in Eyüp
KEREM TÜZÜN
Yüksek Lisans
Türkçe
1997
Mimarlıkİstanbul Teknik ÜniversitesiMimarlık Tarihi Ana Bilim Dalı
PROF. DR. FİLİZ ÖZER