Proximity-Aware Degree-Based Heuristics for the Influence Maximization Problem

Computer and Knowledge Engineering

مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 27 دی 1400  

نوع مقاله: Semantic Technology-Kahani

شناسه دیجیتال (DOI): 10.22067/cke.2022.63265.0

نویسندگان

Maryam Adineh؛ Mostafa Nouri Baygi

Ferdowsi Univerity of Mashhad

چکیده

The problem of influence maximization is to select the most influential individuals in a social network. With the popularity of social network sites and the development of viral marketing, the importance of the problem has increased. The influence maximization problem is NP-hard, and therefore, there will not exist a polynomial-time algorithm to solve the problem unless P=NP. Many heuristics are proposed to find a nearly good solution in a shorter time.



In this paper, we propose two heuristic algorithms to find good solutions. The heuristics are based on two ideas: (1) vertices of high degree have more influence in the network, and (2) nearby vertices influence on almost analogous sets of vertices. We evaluate our algorithms on several well-known data sets and show that our heuristics achieve better results (up to 15% in the influence spread) for this problem in a shorter time (up to 85% improvement in the running time).

کلیدواژه‌ها

Degree centrality؛ Heuristic algorithm؛ Independent cascade model؛ Influence maximization