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

Abstract

Orijinal etki enbüyükleme problemini, düğümlerin farklı fayda değerleri taşıyabildiği hedefli ve düğümlerin tohum düğüm olmak için farklı maliyet değerleri taşıyabildiği bütçeli bir problem versiyonuna genişleterek, yeni Belirlenimci Doğrusal Esik Modeli altında Hedefli ve Bütçeli Etki Enbüyükleme problemini tanımlıyoruz. Çözüm olarak, çeşitli işlemler için alternatif yöntemler barındıran, özgün ve ölçeklenebilir bir genel algoritma geliştiriyoruz: Hedefli ve Bütçeli Potansiyel Açgözlü (TABU-PG) Algoritma. TABU-PG döngülü ve açgözlü bir biçimde çalışır. Her döngüde düğümler karşılaştırılır ve en iyisi/iyileri tohum düğüm olarak seçilir. TABU-PG'nin ana fikri, sonraki döngülerde somutlaştırılabilecek potansiyel kazançlara yatırım yapmaktır. Potansiyel kazançları hesaplamak ve düğümleri karşılaştırmak için alternatif yöntemler sağlanmıştır. Kimi yöntemler literatürden alınmışken, diğer yöntemler bizim tarafımızdan önerilen özgün yöntemlerdir. Düğümleri karşılaştırırken hem kazancı hem verimliliği dikkate alan melez bir yöntem öneriyoruz. Potansiyel kazançları hesaplarken, potansiyel kazançlar için uygun ağırlıkları, kalan bütçe miktarından yola çıkarak dinamik biçimde atayan özgün yöntemler öneriyoruz. Aynı zamanda, parametreyle kontrol edilen bir değerin altında kalan kısmi etki oranlarından kaynaklanan potansiyel kazançları yoklayacak bir yöntem de öneriyoruz. Ayrıca, tohum düğüm aday havuzunu daraltarak veya her bir döngüde daha fazla düğüm seçerek, TABU-PG'nin çalışma süresini önemli ölçüde düşüren özgün ölçekleme yöntemleri sunuyoruz. Bu ölçekleme yöntemleri, çalışma süresi ve yayılma performansı arasında ödünleşerek çalışır. Ek olarak, bağlar üzerindeki etki ağırlıkları ve düğümler üzerindeki esik, fayda ve maliyet değerleri için gerçek hayat dinamiklerini daha iyi yansıttığını düşündüğümüz yeni veri türettim yöntemleri öne sürüyoruz. Gerçek hayattaki 4 sosyal ağ baz alınarak oluşturduğumuz 8 farklı veri setinde kapsamlı sayısal deneyler gerçekleştiriyoruz.

We define the new Targeted and Budgeted Influence Maximization under Deterministic Linear Threshold Model problem by extending the original influence maximization problem to a targeted and a budgeted version. As a solution, we develop a novel and scalable general algorithm which utilizes a set of alternative methods for different operations: TArgeted and Budgeted Potential Greedy (TABU-PG) algorithm. TABU-PG works in an iterative and greedy fashion where nodes are compared at each iteration and the best one(s) are chosen as seed. The main idea behind TABU-PG is to invest in potential future gains which are hoped to be materialized at later iterations. Alternative methods are provided for calculating potential gain, and for comparing nodes. Some methods are taken from the literature while others are novel methods introduced by us. In comparing nodes, we propose a hybrid model which considers both gain and efficiency. In calculating potential gains, we propose methods which dynamically assign suitable weights to potential gains based on remaining budget. We propose a new method which ignores the potential gains which are results of partial influences under a parameterized ratio. We equip TABU-PG with novel scalability methods which reduces runtime by limiting the seed node candidate pool, or by selecting more nodes at each iteration; trading-off between runtime and spread performance. We suggest new data generation methods for influence weights on links; and threshold, profit, and cost values for nodes which better mimics the real-world dynamics. We perform extensive computational experiments with 8 different datasets on 4 real-life networks.