کشف گره‌های تاثیرگذار در شبکه‌های اجتماعی براساس مدل انتشار آبشار مستقل اصلاح شده و الگوریتم ژنتیک چندهدفه فازی

در سال‌های اخیر، شبکه‌های اجتماعی بخش جدایی‌ناپذیر زندگی مردم شده‌است و نقش پر رنگی در دنیای واقعی ایفا می‌کند. مسئله بیشینه‌سازی نفوذ، یافتن یک مجموعه از گره‌ها در شبکه است که اگر فرایند انتشار از آن‌ها آغاز شود، می‌تواند تاثیرگذاری در شبکه را بیشینه کند؛ اگرچه تاکنون مدل‌های مختلفی برای این مسئله و الگوریتم‌های متنوعی برای کشف گره‌های تاثیرگذار در شبکه‌های اجتماعی ارائه شده‌است، اما توجه به ماهیت چندهدفه این مسئله و نیز بهبود عملکرد الگوریتم‌های بهینه‌سازی مطرح‌شده یک چالش جدی پژوهشی در این حوزه‌اند. در این مقاله به منظور مرتفع‌کردن چالش‌ها ضمن درنظرگرفتن نسخه چندهدفه مسئله بیشینه‌سازی نفوذ با سه هدف بیشینه‌سازی تعداد گره‌های موثر مدل انتشار، کمینه‌سازی تعداد کاربران اولیه و مدت زمان مورد نیاز برای انتشار، یک نسخه فازی الگوریتم ژنتیک چندهدفه بر اساس مرتب‌سازی نامغلوب (fnsga) که پارامترهای نرخ جهش و بازترکیب آن به‌وسیله نظام فازی پیشنهادی تنظیم می‌شوند ارائه شده‌است. برای ارزیابی نتایج روش پیشنهادی (fnsga) علاوه‌بر مقایسه با نسخه غیرفازی، با روش‌های ابتکاری مرسوم بیشینه‌سازی نفوذ و نیز با سایر الگوریتم‌های بهینه‌سازی چندهدفه فراابتکاری جدید که تاکنون برای این مسئله ارائه شده‌اند، بر روی پنج مجموعه‌داده مقایسه شده‌است. این مقایسه بر اساس چهار معیار، معیار edv، هزینه (تعداد گره‌های انتخابی به‌عنوان seed)، معیار گسترش نفوذ s)σ) یعنی تعداد گره‌های فعال با مدل انتشار متوالی مستقل (ic) و زمان اجرای روش بر حسب ثانیه صورت گرفته‌است. نتایج به‌دست‌آمده نشان از برتری روش پیشنهادی نسبت به روش‌های دیگر دارد.

discovering influential nodes in social networks based on modified independent cascade model and fuzzy multi-objective genetic algorithm

in recent years, social networks have become an integral part of people’s lives and play a significant role in the real world. the primary aim of influence maximization problem is finding a set of nodes in the network which can maximize the influence if the diffusion process starts from them. therefore, the problem’s goal is to find influential people in large scale real social networks. the penetration phenomenon is carried out according to an influence model in the network. two independent cascade and linear threshold influence models, the most common of which is the independent cascade model, are utilized for broadcasting in the network. theoreticaly, optimizing the selection influential nodes problem is np-hard in both models.the problem will start by considering the social network’s graph, a specific influence model and a given number k. the problem’s goal is to select k nodes (users) from the graph (network) as influential nodes, so that the number of active nodes is maximized at the end of the diffusion process. due to the influence maximization problem and finding influential people is an np-hard optimization problem in the social network, meta-heuristic algorithms can be used to solve the problem. with regard to the privous researches, there is just one objective function as the problem’s goal and it is maximizing the number of effective nodes of the diffusion model. while other objective functions such as maximizing the number of effective nodes in the diffusion model and minimizing the budget value k (the number of initial nodes as seed) are not considered, minimizing the time required for effective diffusion can be achieved by having k initial nodes. although various models for the problem and various optimization algorithms have been presented to discover influential nodes in social networks, paying attention to the multi-objective nature of the problem and improving the performance of the proposed optimization algorithms are a serious research challenge in this field.in this paper. a fuzzy version of the nsga-ii as a multi-objective genetic algorithm, whose mutation and crossover rates are adjusted by fuzzy inference system, is utilized to simultaneously optimize the three objectives of maximizing the number of effective nodes, minimizing the number of initial nodes and minimizing the required diffusion time. in the proposed method, the expected diffusion value (edv) of the diffusion model is replaced instead the simulation of the independent cascade diffusion model with heavy calculations to calculate the diffusion spread (the number of effective nodes of the diffusion model). therefore, the edv function is satisfied as the thied objective (minimizing the required diffusion time).