Sosyal ağlarda etki maksimizasyonu
Yükleniyor...
Dosyalar
Tarih
2018
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Düzce Üniversitesi
Erişim Hakkı
info:eu-repo/semantics/openAccess
Özet
İnsanlar fikirlerini yaymak, yenilikler hakkında bilgi edinebilmek için çevrimiçi sosyal ağları kullanırlar. Bu bağlamda, bilginin sosyal ağlar üzerinde nasıl yayıldığını bilmek önemlidir. Bir sosyal ağ aracılığıyla daha fazla sayıda kişiye bir bilgiyi (örneğin ürün reklamı) yaymak mümkündür. Burada kilit nokta, sosyal ağdaki en etkili bireyleri tespit edebilmektir. Bu problem Etki Maksimizasyonu (EM) problemi olarak adlandırılmıştır. EM problemi, belirli bir birey grubunu etkileyen, az sayıdaki çekirdek bireyi bulmaya odaklanır. Literatürde, EM problemi için açgözlü algoritmalar, stokastik ve evrimsel optimizasyon algoritmaları önerilmiştir. Ancak, bu yöntemler hız veya çözüm kalitesi açısından istenen seviyede değildir. Öte yandan, literatürde hızlı ve optimal çözümler üreten birçok sürü zekâsı algoritması bulunsa da, bu algoritmalar EM problemine doğrudan uygulanamazlar. Bu tezde, sürü zekâsı algoritmalarının EM problemine uygulanabilmesini sağlamak için problemin yapısı değiştirilmiştir. Bir sosyal ağıdaki bireyleri düğümler olarak ele alırsak; yapılan işlem, bazı ağ ölçütlerine göre düğümlerin büyükten küçüğe doğru sıralanması ve bu sıraya göre yeniden numaralandırılması olarak tarif edilebilir. Önerilen yaklaşım işaretli ve işaretsiz gerçek graflar ve sentetik graflarla test edilmiştir. Denemelerde, sürü zekâsı algoritmaları olarak Bozkurt Optimizasyonu (Gray Wolf Optimizer, GWO) ve Balina Optimizasyon Algoritması (Whale Optimization Algorithm, WOA); kıyaslama yöntemleri olarak PageRank ve Kempe'nin Açgözlü Algoritması kullanılmıştır. Deneysel sonuçlar önerilen yaklaşımın iyi çalıştığını göstermiştir.
People use online social networks to spread ideas, learn about innovations, etc. In this context, it is important to know how information spreads through social networks. It is possible to spread information (e.g., product advertisement) to a larger number of individuals via a social network. The key point is to identify the most influential individuals on the social network. This problem is named as Influence Maximization (IM) problem. The IM problem focuses on finding the small subset of individuals in a social environment who influence a certain group of individuals. In the literature, greedy, stochastic, and evolutionary optimization algorithms have been proposed to solve this problem. However, these methods are not at the desired level in terms of speed or solution quality. On the other hand, although many Swarm Intelligence (SI) algorithms can be found in the literature, these algorithms cannot be directly applied to the IM problem. In this thesis, a change in the structure of the IM problem is suggested in order to tailor it to SI algorithms. If a social network is envisioned as a graph and individuals as nodes, the proposed method means sorting the nodes in descending order according to some graph metrics and renumbering the nodes according to this order. The proposed approach was tested with signed and unsigned real and synthetic graphs. The experiments employed Grey Wolf Optimizer (GWO) and Whale Optimization Algorithm (WOA) SI algorithms and PageRank and Kempe et. al.'s Greedy Algorithm as benchmark methods. Experimental results showed that this approach worked well.
People use online social networks to spread ideas, learn about innovations, etc. In this context, it is important to know how information spreads through social networks. It is possible to spread information (e.g., product advertisement) to a larger number of individuals via a social network. The key point is to identify the most influential individuals on the social network. This problem is named as Influence Maximization (IM) problem. The IM problem focuses on finding the small subset of individuals in a social environment who influence a certain group of individuals. In the literature, greedy, stochastic, and evolutionary optimization algorithms have been proposed to solve this problem. However, these methods are not at the desired level in terms of speed or solution quality. On the other hand, although many Swarm Intelligence (SI) algorithms can be found in the literature, these algorithms cannot be directly applied to the IM problem. In this thesis, a change in the structure of the IM problem is suggested in order to tailor it to SI algorithms. If a social network is envisioned as a graph and individuals as nodes, the proposed method means sorting the nodes in descending order according to some graph metrics and renumbering the nodes according to this order. The proposed approach was tested with signed and unsigned real and synthetic graphs. The experiments employed Grey Wolf Optimizer (GWO) and Whale Optimization Algorithm (WOA) SI algorithms and PageRank and Kempe et. al.'s Greedy Algorithm as benchmark methods. Experimental results showed that this approach worked well.
Açıklama
YÖK Tez No: 523476
Anahtar Kelimeler
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
