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

سال انتشار: 1401
محل انتشار: مجله مهندسی کامپیوتر و دانش، دوره: 5، شماره: 1
کد COI اختصاصی: JR_CKE-5-1_004
زبان مقاله: انگلیسی
تعداد مشاهده: 218

نویسندگان

Department of Computer Engineering, Ferdowsi University of Mashhad, Mashhad, Iran.

چکیده

The problem of influence maximization is selecting 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 any polynomial-time algorithm to solve the problem unless P = NP. Many heuristics are proposed for finding a nearly good solution in a shorter time. This study proposes two heuristic algorithms for finding good solutions. The heuristics are based on two ideas: ۱) vertices of high degree have more influence in the network, and ۲) 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 ۱۵% in the influence spread) for this problem in a shorter time (up to ۸۵% improvement in the running time).

کلیدواژه ها

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

اطلاعات بیشتر در مورد COI

COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.

کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.