بيشينه سازي تأثير در شبكه هاي اجتماعي با الگوريتم قورباغه جهنده بهبود يافته

A novel evolutionary algorithm based on Shuffled Frog-Leaping method for influence maximization in social networks

يك شبكه اجتماعي ساختاري اجتماعي از گروه هاي فردي يا سازماني تشكيل شده است كه توسط يك يا چند نوع خاص از وابستگي‌ها مانند دوستان، خويشاوندان به هم وصل هستند. در سال‌هاي اخير، با محبوبيت شبكه‌هاي اجتماعي مشكل بيشينه سازي تأثير به يكي از موضوعات داغ در اين زمينه تبديل شده است. بيشينه سازي تأثير، مسئله پيدا كردن زير مجموعه‌ي محدودي از گره‌ها در يك شبكه اجتماعي است كه تعداد گره‌هاي تحت تأثير را به حداكثر برساند. براي رسيدن به تأثير بيشينه روش‌‌هاي بسياري ارائه شده از جمله روش‌هاي حريصانه كه راه حل خوبي براي مشكل فوق ايجاد مي كنند، اما عمدتا محاسبات زيادي دارند. به دليل اين محدوديت ها، كارايي اين الگوريتم ها براي شبكه اجتماعي بزرگ ناچيز است. روش ديگر براي پيدا كردن اين گره‌ها روش‌هاي اكتشافي است كه معمولا سرعت بهتري دارند. در اين تحقيق روشي ارائه شده است كه شامل تشخيص جامعه، انتخاب گره با بيشترين درجه و استفاده از الگوريتم قورباغه جهنده براي به حداكثر رساندن گسترش تأثير تحت مدل آبشاري مستقل است. آزمايش‌هاي انجام شده بر روي هشت مجموعه داده هاي دنياي واقعي نشان داده‌ اند روش ما در مقايسه با الگوريتم‌هاي به روز دقت بالاتري دارد ضمن اينكه از نظر پيچيدگي محاسباتي از بقيه سريعتر است.

A social network is a social structure consisting of individual or organizational groups connected by specific types of relationships, such as friendships or family ties. In recent years, with the popularity of social networks, the problem of influence maximization has emerged as a prominent topic in this field. Influence maximization involves identifying a limited subset of nodes in a social network that can maximize the number of influenced nodes. Various methods have been proposed to achieve this goal, including greedy approaches like CELF, which, despite yielding good results, suffer from high computational costs. Consequently, these algorithms are inefficient for large-scale social networks. An alternative approach is to employ exploratory methods, which often offer faster execution but yield weaker outcomes. In this research, we present a method that incorporates community detection, selection of high-degree nodes, and the utilization of the shuffled frog algorithm to maximize the propagation of influence under the independent cascade model. Experimental evaluations conducted on eight real-world datasets demonstrate that our method outperforms state-of-the-art algorithms in terms of accuracy, while also exhibiting faster computational time