N-hop influence maximization problem under deterministic linear threshold model

Abstract

The Influence Maximization Problem (IMP) finds a set of highly influential nodes within a social network in order to maximize the spread of influence. We consider that people can have influence on their direct (1-hop), 2-hop and 3-hop neighbors. IMP with extended influence transitivity is called n-hop IMP. In this paper, we study the problem under the deterministic linear threshold model and propose a heuristic solution. In our proposed heuristic model, there are two parts, extended seed set algorithm and local search. Main purpose of extended seed set algorithm is creating a node set and send it to local search which is based on trying to improve it via replacing the nodes in the given set. We used two different features for selecting the candidate nodes. We propose an equation to estimate the value of a node set without actually computing. We used real-life and synthetic networks to test our solution method and generated weight and threshold values in three different methods.

Etki Enbüyükleme Problemi, bir sosyal ağ içinde etkinin yayılmasını en üst düzeye çıkarmak için bir dizi son derece etkili düğüm bulur. İnsanların doğrudan (1-adım), 2-adım ve 3-adım komşuları üzerinde etkileri olabileceğini düşünüyoruz. Genişletilmiş etki geçişliliğine sahip Etki Enbüyükleme Problemi, n-adım Etki Enbüyükleme Problemi olarak adlandırılır. Bu yazıda, bahsedilen problemi belirlenmiş doğrusal eşik modeli altında inceliyoruz ve sezgisel bir çözüm buluyoruz. Önerdiğimiz sezgisel modelimizde, genişletilmiş çekirdek küme algoritması ve yerel arama olmak üzere iki bölüm var. Genişletilmiş çekirdek küme algoritmasının temel amacı, bir düğüm kümesi oluşturmak ve onu verilen kümedeki düğümleri değiştirerek iyileştirmeye dayanan yerel aramaya göndermektir. Aday düğümleri seçmek için iki farklı özellik kullandık. Gerçekte hesaplama yapmadan bir düğüm kümesinin değerini tahmin etmek için bir denklem buluyoruz. Çözüm yöntemimizi test etmek için gerçek hayat ve sentetik ağları kullandık ve üç farklı yöntemde ağırlık ve eşik değerleri oluşturduk.