Geri Dön

Leader-follower games for influence spread in social networks

Sosyal ağlarda etki yayılımına yönelik öncü-izleyici oyunları

  1. Tez No: 643179
  2. Yazar: KÜBRA TANINMIŞ ERSÜS
  3. Danışmanlar: PROF. DR. MUSTAFA NECATİ ARAS, PROF. DR. İSMAİL KUBAN ALTINEL
  4. Tez Türü: Doktora
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2020
  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ı: Endüstri Mühendisliği Bilim Dalı
  13. 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

  1. Toplum ve moda etkileşimi

    Başlık çevirisi yok

    MAKBULE SEMA ÜŞENMEZ

    Doktora

    Türkçe

    Türkçe

    1992

    SosyolojiMimar Sinan Güzel Sanatlar Üniversitesi

    Sosyoloji Ana Bilim Dalı

    PROF. DR. M. NEVRES TURHAN

  2. The Participatory Theater Framework of Leadership

    Liderlik için Katılımcı Tiyatro Modeli

    AYBİKE MUTLUER MERGEN

    Doktora

    İngilizce

    İngilizce

    2022

    İşletmeKoç Üniversitesi

    Yönetim ve Strateji Ana Bilim Dalı

    PROF. DR. ZEYNEP AYCAN

  3. 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

    Türkçe

    2007

    Siyasal Bilimlerİstanbul Üniversitesi

    Avrupa Birliği Ana Bilim Dalı

    PROF. DR. HÜLYA BAYKAL

  4. 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

    İngilizce

    2018

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

    Kontrol ve Otomasyon Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ TUFAN KUMBASAR

  5. 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

    Türkçe

    1997

    Mimarlıkİstanbul Teknik Üniversitesi

    Mimarlık Tarihi Ana Bilim Dalı

    PROF. DR. FİLİZ ÖZER