یک روش جدید حریصانه مبتنی بر مدل آبشاری برای محاسبه‌ی حداکثر سازی نفوذ در شبکه‌های اجتماعی
محورهای موضوعی : عمومیعسگرعلی بویر 1 , حمید احمدی بنی 2
1 - گروه مهندسی کامپیوتر، دانشكده فناوری اطلاعات و مهندسي كامپيوتر، دانشگاه شهید مدنی آذربایجان، تبریز
2 - گروه مهندسی کامپیوتر، دانشكده فناوری اطلاعات و مهندسي كامپيوتر، دانشگاه شهید مدنی آذربایجان، تبریز
کلید واژه: مدل آبشاری مستقل, حداکثر سازی نفوذ, انتشار, شبکه اجتماعی,
چکیده مقاله :
در مسئله حداکثر سازی نفوذ، هدف یافتن حداقل تعدادی گره هست که بیشترین انتشار و نفوذ را در شبکه داشته باشند. مطالعات راجع به حداکثر سازی نفوذ و انتشار به‌صورت گسترده ای در حال گسترش است. در سال های اخیر الگوریتم‌های زیادی درزمینهٔ مسئله حداکثر سازی نفوذ در شبکه های اجتماعی ارائه‌شده است. این مطالعات شامل بازار یابی ویروسی، گسترش شایعات، اتخاذ نوآوری و شیوع بیماری‌های همه گیر و ... است. هر یک از مطالعات پیشین دارای کاستی‌هایی دریافتن گره‌های مناسب و یا پیچیدگی زمانی بالا هستند. در این مقاله، روشی جدید با عنوان ICIM-GREEDY برای حل مسئله حداکثر سازی نفوذ ارائه کرده ایم. در الگوریتم ICIM-GREEDY دو معیار مهم که در کارهای انجام‌شده قبلی در نظر گرفته نشده اند را در نظر می گیریم، یکی قدرت نفوذ و دیگری حساسیت به نفوذ. این دو معیار همیشه در زندگی اجتماعی انسان‌ها وجود دارد. روش پیشنهادی روی دیتاست‌های استاندارد مورد ارزیابی قرارگرفته‌شده است. نتایج به‌دست‌آمده نشان می‌دهد که روش مذکور نسبت به دیگر الگوریتم‌های مقایسه شده از کیفیت بهتری در پیدا کردن نودهای بانفوذ در 30 گره Seed برخوردار است. همچنین این روش از لحاظ زمانی نیز نسبت به الگوریتم‌های مقایسه شده به لحاظ همگرایی نسبتاً سریع، بهتر عمل می‌کند.
In the case of penetration maximization, the goal is to find the minimum number of nodes that have the most propagation and penetration in the network. Studies on maximizing penetration and dissemination are becoming more widespread. In recent years, many algorithms have been proposed to maximize the penetration of social networks. These studies include viral marketing, spreading rumors, innovating and spreading epidemics, and so on. Each of the previous studies has shortcomings in finding suitable nodes or high time complexity. In this article, we present a new method called ICIM-GREEDY to solve the problem of maximizing penetration. In the ICIM-GREEDY algorithm, we consider two important criteria that have not been considered in the previous work, one is penetration power and the other is penetration sensitivity. These two criteria are always present in human social life. The proposed method is evaluated on standard datasets. The obtained results show that this method has a better quality in finding penetrating nodes in 30 seed nodes than other compared algorithms. This method also performs better in terms of time compared to the comparative algorithms in terms of relatively fast convergence.