مروری جامع بر مسئله بیشینه‌سازی تأثیر در شبکه‌های اجتماعی
محورهای موضوعی : فناوری اطلاعات و ارتباطاتمحسن طاهری نیا 1 , مهدی اسماعیلی 2 , بهروز مینایی 3
1 - دانشکده کامپیوتر، دانشگاه آزاد اسلامی واحد کاشان، کاشان، ایران
2 - دانشکده کامپیوتر، دانشگاه آزاد اسلامی واحد کاشان، کاشان، ایران
3 - دانشکده مهندسی کامپیوتر ، دانشگاه علم و صنعت ایران، تهران، ایران
کلید واژه: بیشینه‌سازی تأثیر, تجزیه‌وتحلیل شبکه‌های اجتماعی, افراد تأثیرگذار, شبکه‌های اجتماعی, شناسایی اجتماعات, مدلهای انتشار.,
چکیده مقاله :
با توسعه روزافزون شبکه‌های اجتماعی، بسیاری از بازاریابان از این فرصت استفاده کرده و سعی در یافتن افراد تأثیرگذار در شبکه‌های اجتماعی آنلاین دارند. این مسئله که به عنوان مسئله بیشینه‌سازی تأثیر شناخته می‌شود. کارایی زمانی و اثربخشی دو معیار مهم در تولید الگوریتم‌های برجسته در حوزه مسئله بیشینه‌سازی تأثیر محسوب می‌شوند. برخی از محققان با بهره‌گیری از ساختار اجتماعات به‌عنوان ویژگی بسیار مفید شبکه‌های اجتماعی، این دو موضوع را به‌طور مشهودی بهبود بخشیده‌اند. هدف این مقاله بررسی جامع الگوریتم‌های برجسته پیشنهادشده در حوزه مسئله بیشینه‌سازی تأثیر در شبکه‌های اجتماعی با تأکید ویژه بر رویکردهای مبتنی بر شناسایی اجتماعات است.
With the incredible development of social networks, many marketers have exploited the opportunities, and attempt to find influential people within online social networks to influence other people. This problem is known as the Influence Maximization Problem. Efficiency and effectiveness are two important criteria in the production and analysis of influence maximization algorithms. Some of researchers improved these two issues by exploiting the communities’ structure as a very useful feature of social networks. This paper aims to provide a comprehensive review of the state of the art algorithms of the influence maximization problem with special emphasis on the community detection-based approaches
With the incredible development of social networks, many marketers have exploited the opportunities, and attempt to find influential people within online social networks to influence other people. This problem is known as the Influence Maximization Problem. Efficiency and effectiveness are two important criteria in the production and analysis of influence maximization algorithms. Some of researchers improved these two issues by exploiting the communities’ structure as a very useful feature of social networks. This paper aims to provide a comprehensive review of the state of the art algorithms of the influence maximization problem with special emphasis on the community detection-based approaches
دو فصلنامه علمي فناوري اطلاعات و ارتباطات ایران | سال چهاردهم، شماره‌هاي 53 و 54، پاییز زمستان 1401 صفحات:267 تا 292
|
|
A Comprehensive Review on the Influence Maximization Problem in Social Networks with Focusing on the Community
Detection Methods
Mohsen Taheri Nia، *Mehdi Ismaili، *Behrouz Minai Bidgoli**
* Faculty of Computer Science, Islamic Azad University, Kashan branch, Kashan, Iran.
** Faculty of Computer Science, Islamic Azad University, Kashan branch, Kashan, Iran.
Abstract:
With the incredible development of online social networks, many marketers have exploited the opportunity to find influential people within online social networks to influence other people. The finding of influential users is known as the Influence Maximization problem, which is a key algorithmic problem in influence analysis. This problem aims to select a limited set of most influential users to maximize the number of influenced users in an online social network. This problem has been studied in recent years extensively due to its significant role in various applications, such as viral marketing, advertising, recommender systems, social media analysis, etc. The non-stop growth of social networks has intensified the time efficiency (scalability) and effectiveness challenges of this NP-Hard problem. Researchers have been controlled these challenges by exploiting the communities’ structure as a useful feature of social networks. Inspired by these points, this paper provides a comprehensive review of the state-of-the-art algorithms in the influence maximization problem, focusing on the community-based models. At first, the outstanding greedy and heuristics algorithms are surveyed in addressing these challenges. Then, existing community-based algorithms especially are reviewed and compared. In the end, several directions are suggested for future researches in the influence maximization problem.
Keywords: Influence Maximization, Social Networks Analysts, Influencer, Social Networks, Community Detection, Diffusion Models.
مروری جامع بر مسئله‌ی بیشینه‌سازی تأثیر در شبکه‌های اجتماعی با تمرکز بر روش‌های مبتنی بر شناسایی اجتماعات
محسن‌طاهری‌نیا*، مهدی‌اسماعیلی* و بهروز مینایی‌بیدگلی**
* دانشکده کامپیوتر، دانشگاه آزاد اسلامی واحد کاشان، کاشان، ایران.
** دانشکده مهندسی کامپیوتر، دانشگاه علم و صنعت ایران، تهران، ایران.
تاریخ دریافت:22/05/1400 تاریخ پذیرش:23/08/1400
نوع مقاله : پژوهشی
چکیده
با توسعه روزافزون شبکه‌های اجتماعی، بسیاری از بازاریابان از این فرصت استفاده کرده و سعی در یافتن افراد تأثیرگذار در شبکه‌های اجتماعی آنلاین دارند. این مسئله که به عنوان مسئله‌ی بیشینه‌سازی تأثیر شناخته می‌شود، یک مسئله الگوریتمی در تجزیه و تحلیل شبکه‌های اجتماعی است. هدف از مسئله‌ی بیشینه‌سازی تأثیر، یافتن تعداد محدودی از کاربران تأثیرگذار در یک شبکه اجتماعی است به‌طوری‌که بیشترین تعداد ممکن از کاربران دیگر را تحت تأثیر خود قرار دهند. این مسئله در زمینه‌های مختلف مانند بازاریابی ویروسی، تبلیغات، سیستم‌های پیشنهاددهنده، تجزیه و تحلیل رسانه‌های اجتماعی در سال‌های اخیر به طور گسترده مورد مطالعه قرار گرفته است. بنابراین، نیاز به یک مروری سازمان‌یافته و جامع در رابطه با این موضوع وجود دارد.
کارایی زمانی و اثربخشی دو معیار مهم در تولید الگوریتم‌های برجسته در حوزه مسئله‌ی بیشینه‌سازی تأثیر محسوب می‌شوند. برخی از محققان با بهره‌گیری از ساختار اجتماعات به‌عنوان ویژگی بسیار مفید شبکه‌های اجتماعی، این دو موضوع را به‌طور مشهودی بهبود بخشیده‌اند. اکثر مقالات مروری موجود، مطالعاتی را که تأثیر اجتماعی را بر اساس ساختار اجتماعات تحلیل کرده‌اند، نادیده گرفته‌اند. هدف این مقاله بررسی جامع الگوریتم‌های برجسته پیشنهادشده در حوزه مسئله‌ی بیشینه‌سازی تأثیر در شبکه‌های اجتماعی با تأکید ویژه بر رویکردهای مبتنی بر شناسایی اجتماعات است.
واژه‌گان کلیدی: بیشینه‌سازی تأثیر، تجزیه‌وتحلیل شبکه‌های اجتماعی، افراد تأثیرگذار، شبکه‌های اجتماعی، شناسایی اجتماعات، مدلهای انتشار.
1. مقدمه
در دو دهه گذشته، طیف وسیعی از شبکه‌های اجتماعی ظهور کرده‌اند که در آنها حجم زیادی از اطلاعات و ایده‌ها از طریق تعاملات بین مردم منتشر می‌شود. تأثیر اجتماعی پدیده‌ای است که در آن افراد یک شبکه اجتماعی از طریق پیروی از دوستان، آشنایان، همکاران خود تحت تأثیر آنها قرار می‌گیرند. یکی از مهم‌ترین موضوعات مطرح در تحلیل شبکه‌های اجتماعی، مسئله‌ی بیشینه‌سازی تأثیر است. هدف از مسئله‌ی بیشینه‌سازی تأثیر، شناسایی مجموعه‌ای از تأثیرگذارترین افراد در شبکه‌های اجتماعی است به‌طوری‌که اگر فرآیند انتشار اطلاعات (تأثیر) از این مجموعه آغاز شود، در نهایت بیشترین تعداد افر1اد شبکه تحت تأثیر قرار بگیرند [1]. این مسئله در بسیاری از زمینه‌های محبوب مانند بازاریابی، تبلیغات، سیستم‌های پیشنهاددهنده و غیره کاربردی شده است [2]. بسیاری از بازاریاب‌ها با بهره‌گیری از گسترش شبکه‌های اجتماعی آنلاین، به‌جای اینکه استراتژی‌های بازاریابی سنتی را دنبال کنند، سعی می‌کنند از طریق اثر «دهان‌به‌دهان» یا رویکردهای بازاریابی ویروسی، بر کاربران رسانه‌های اجتماعی آنلاین تأثیر بگذارند. شایستگی قابل توجه اثر «دهان‌به‌دهان» و رویکردهای بازاریابی ویروسی این است که آنها سهم شرکت‌های کوچک با منابع محدود را از بازار افزایش می‌دهند. برای توضیح بیشتر، شرکتی را در نظر بگیرید که قصد دارد محصول جدیدی را با کمترین بودجه به‌صورت آنلاین در بازار تبلیغ کند. به دلیل منابع محدود، شرکت باید تعداد محدودی از کاربران تأثیرگذار را در داخل شبکه اجتماعی برای تجربه (رایگان یا با اندکی تخفیف) این محصول انتخاب کند. پیش‌بینی می‌شود که این کاربران تأثیرگذار در مکانیسمی آبشاری، محصول جدید را به سایر کاربران متصل به خود توصیه کنند (تبلیغ کنند). در نهایت، این محصول به تعداد زیادی از کاربران در دسترس معرفی شده و پذیرفته خواهد شد؛ بنابراین، به شرطی که کاربران تأثیرگذار اولیه به‌درستی انتخاب شوند، میزان تأثیرگذاری در شبکه حداکثر خواهد بود.
مسئله‌ی بیشینه‌سازی تأثیر ابتدا توسط دومینگوس و همکاران در بازاریابی ویروسی معرفی شد [3]. سپس کمپ و همکاران این مسئله را به عنوان یک مسئله بهینه‌سازی گسسته فرموله کردند و دو مدل انتشار را برای شبیه‌سازی فرآیند انتشار اطلاعات در شبکه پیشنهاد کردند: مدل آستانه خطی2 و مدل آبشاری مستقل3 [4]. آنها ثابت کردند که یافتن راه حل بهینه تحت این دو مدل انتشار NP-hard است و یک الگوریتم حریصانه4 با تقریب 63٪ از راه حل بهینه ارائه دادند. افزایش اندازه شبکه‌های اجتماعی باعث کاهش کارایی زمانی این الگوریتم حریصانه شد [5]. برای مقابله با این چالش کارایی زمانی، طیف وسیعی از الگوریتم‌ها در سال‌های اخیر ارائه شده است.
مسئله بیشینه‌سازی تأثیر در شبکه‌های اجتماعی، از مسائل مهم کاربردی در بسیاري از زمینه‌ها مثل بازاریابی، تبلیغات و سیستم‌های پیشنهاددهنده است. جذابیت و فراگیری روزافزون شبکه های اجتماعی باعث شده که محققان زیادي تحقیقات متنوعی را پیرامون مسئله بیشینه‌سازی تأثیر در شبکه‌های اجتماعی انجام دهند. از آنجایی که این حوزه تحقیقاتی، هنوز یک موضوع چالش‌برانگیز به‌حساب می‌آید، همواره روش‌ها و الگوریتم های متنوعی در حـال معرفی و بهبود کارایی هستند. بر این اساس، مقاله حاضر در تلاش است که با مرور روش‌های موجود برای شناسایی گره‌های تاثیرگذار در شبکه‌های‌اجتماعی دید جامعی در رابطه با این موضوع پدید آورد.
یکی از نقاط قوت برجسته این مقاله‌ی مروری، تمرکز بر الگوریتم‌های مبتنی بر شناسایی اجتماعات5 در مسئله‌ی بیشینه‌سازی تأثیر است. ساختار اجتماعات یکی از حیاتی‌ترین ویژگیهای شبکه‌های اجتماعی است. در دنیای واقعی، مردم تمایل دارند با افرادی که از نظر اندیشه، رفتار و علاقه مشابه هستند تعامل داشته باشند. این موضوع منجر به تشکیل اجتماعات می‌شود. در مسئله‌ی بیشینه‌سازی تأثیر که هدف آن افزایش میزان تأثیرگذاری در شبکه است، استفاده از ساختار اجتماعات منجر به افزایش اثربخشی خواهد شد. از سوی دیگر، رشد نمایی اندازه شبکه‌های اجتماعی چالشی بزرگ در کارایی زمانی و مقیاس‌پذیری6 مسئله‌ی بیشینه‌سازی تأثیر است. یک راه حل بسیار مفید برای غیال بر این چالش، تبدیل یک گراف (شبکه اجتماعی) عظیم به زیرگراف‌های کوچکتر (اجتماعات) به عنوان یک استراتژی تقسیم و غیال است. از این‌رو محققان به‌طور گسترده از ساختار اجتماعات برای بهبود کارایی زمانی و اثربخشی الگوریتم‌های خود در مسئله‌ی بیشینه‌سازی تأثیر استفاده کرده‌اند. ازآنجاکه هیچ مقاله مروری که الگوریتم‌های مبتنی بر شناسایی اجتماعات را پوشش دهد وجود نداشت[1,2,5–11]، این مقاله به بررسی جامع الگوریتم‌های برجسته پیشنهادشده در حوزه مسئله‌ی بیشینه‌سازی تأثیر با تمرکز ویژه بر رویکردهای مبتنی بر شناسایی اجتماعات می‌پردازد. ادامه این مقاله به شرح زیر است: در بخش 2 مسئله‌ی بیشینه‌سازی تأثیر، مدلهای انتشار اطلاعات و فرآیند شناسایی اجتماعات شرح داده می‌شود. بخش 3 مرور ادبیات جامع از الگوریتم‌های افزایش تأثیر را ارائه می‌دهد. سرانجام، بخش 4 به جمع‌بندی و ارائه مسیری برای تحقیقات آتی می‌پردازد. در شکل 1 چارچوب کلی مقاله نشان داده شده است.
شکل 1. قالب کلی مقاله
2. مسئله‌ی بیشینه‌سازی تأثیر
جدول 1 نمادهای پرتکرار این مقاله را نشان می‌دهد.
جدول 1 . نمادهای پرتکرار
2.1. بیشینه‌سازی تأثیر
به‌طورکلی، تأثیر اجتماعی به توانایی تلقین یا تغییر ایده‌ها، باورها، افکار یا اعمال یک فرد یا یک اجتماع اشاره دارد. بر اساس موارد ذکرشده، مسئله‌ی بیشینه‌سازی تأثیر، مسئله یافتن مجموعه کوچکی از افراد شبکه اجتماعی است که میزان تأثیر اجتماعی را در شبکه‌های اجتماعی حداکثر کنند [5]. مسئله‌ی بیشینه‌سازی تأثیر به شرح زیر فرموله می‌شود:
فرض کنید که گراف 
داده شده است که در آن هر گره 
نشان‌دهنده‌ی یک کاربر و هر یال 
نشان‌دهنده رابطه بین کاربر 
و 
است. همچنین عدد صحیح مثبت 
به عنوان تعداد افراد مجموعه سبد7 
داده شده باشد. در ضمن مدل 
یک مدل انتشار تصادفی است که فرآیند پخش اطلاعات را از افراد مجموعه سبد در گراف 
شبیه‌سازی می‌کند. میزان گسترش تأثیر مجموعه سبد با 
گره برابر با تعداد گره‌های تحت تأثیرقرارگرفته توسط مجموعه تحت مدل انتشار است که با 
نشان داده می‌شود. هدف از مسئله‌ی بیشینه‌سازی تأثیر، یافتن زیرمجموعه‌ی 
با عنصراست که
نامیده می‌شود، به‌طوری‌که میزان تأثیر بر گراف با توجه به قوانین احتمالی مشخص شده توسط مدل ، بیشینه باشد [4]، یعنی،
(1)
لازم به ذکر است که میزان گسترش تأثیر به‌طور مستقیم به مدل انتشار احتمالی بستگی دارد. در شکل 2 چارچوب کلی مسئله بیشینه‌سازی تاثیر نشان داده شده است.
شکل 2. چارچوب کلی مسئله بیشینه‌سازی تاثیر
2.2. مدلهای انتشار8
مدلهای انتشار، مدلهای تصادفی هستند که فرآیند انتشار اطلاعات را در شبکه‌های اجتماعی شبیه‌سازی می‌کنند [4]. هدف همه مدلهای انتشار، انعکاس ارتباطات بین افراد در شبکه‌های اجتماعی واقعی است. در مدلهای انتشار، هر گره دارای وضعیت فعال یا غیرفعال است. وضعیت فعال گره بدین معنی است که گره تحت تأثیرقرار گرفته است و همچنین قابلیت فعال‌سازی و تأثیرگذاری روی همسایگان خود را دارد. وضعیت غیرفعال به معنای آن است که تحت تأثیرقرار نگرفته است و قابلیت فعال‌سازی همسایگان خود را ندارد. مدل آستانه خطی و مدل آبشاری مستقل از پرکاربردترین مدلهای انتشار در این مسئله هستند. در این مدل‌ها، وضعیت یک گره می‌تواند از حالت غیرفعال به وضعیت فعال تبدیل شود اما نمی‌توان وضعیت گره را از حالت فعال به غیرفعال تغییر داد.
وضعیت همه گره‌ها در ابتدا غیرفعال است. پس از انتخاب گره اولیه و ساخت مجموعه سبد ()، وضعیت گره‌های مجموعه سبد به وضعیت فعال تغییر می‌یابد. روند انتشار اطلاعات از گره‌های فعال سبد آغاز می‌شود. آنها می‌توانند همسایگان خود را در گام‌های زمانی جداگانه فعال کنند. گره‌هایی که اخیراً فعال شده‌اند می‌توانند همسایگان خود را فعال کنند و این روال همین‌طور ادامه پیدا می‌کند. این فرآیند انتشار هنگامی‌که گره جدیدی فعال نشده باشد، به پایان خواهد رسید. مدلهای مختلف انتشار دارای استراتژی‌های متنوعی برای تبدیل حالت گره از غیرفعال به فعال هستند. مدلهای آستانه خطی و آبشاری مستقل به‌عنوان متداول‌ترین مدلهای انتشار در شبکه‌های اجتماعی دارای استراتژی‌های مختلف برای شبیه‌سازی فرآیند انتشار اطلاعات هستند [4].
2.2.1. مدل آستانه خطی
فعال شدن گره v در مدل آستانه خطی بستگی به فعال‌بودن همسایگان آن دارد. در این مدل، یک عدد تصادفی
از توزیع یکنواخت در بازه [0،1] به هر گره v به‌عنوان آستانه فعال‌سازی آن گره اختصاص داده شده است. همچنین به هر یال جهتدار از گره u به گره v، یک وزن
به‌عنوان مقدار تأثیر گره u روی گره v اختصاص داده می‌شود، به‌طوری‌که شرط
(2)
برقرار باشد [4]. گره v در گام زمانی بعدی فعال خواهد شد، اگر مجموع وزن همسایگان فعال گره v حداقل برابر باشد [4]، به‌عبارت‌دیگر
(3)
در نهایت هنگامی که هیچ گره جدیدی فعال نشده باشد، فرآیند انتشار خاتمه می‌یابد.
2.2.2. مدل آبشاری مستقل
استراتژی فعال‌سازی در مدل آبشاری مستقل به شرح زیر است. فرض کنید که مجموعه
شامل گره‌های فعال‌شده در گام زمانی 
باشد. در گام زمانی 
، هر گره 
فقط یک شانس برای فعال کردن هر همسایه غیرفعال v با احتمال فعال‌سازی 
دارد. اگر گره u موفق شود، آنگاه گره v در گام زمانی 
فعال شده و در تمام گام‌های زمانی بعدی فعال باقی می‌ماند، در غیر این صورت غیرفعال خواهد ماند. صرف‌نظر از نتیجه فعال‌سازی گره u روی همسایگان خود، گره u هرگز نمی‌تواند گرهای را در گام زمانی بعدی فعال کند. این روند گسترش تا زمانی که امکان فعال‌سازی بیشتر وجود نداشته باشد، ادامه می‌یابد. توجه داشته باشید که در مواردی که چندین گره فعال سعی در فعال‌سازی یک گره غیرفعال دارند، تلاش‌ها مستقل از یکدیگر خواهند بود. مدل آبشاری وزندار9 توسعه‌ای از مدل آبشاری مستقل است که تابع احتمالی فعال‌سازی آن بر اساس درجه هر گره است [4] :
(4)
2.3. شناسایی اجتماعات
اجتماعات ساختارهای پنهان و یکی از ویژگیهای مفید شبکه‌های اجتماعی هستند [12]. در سال‌های اخیر موضوع شناسایی اجتماعات توجه زیادی را در تجزیه‌وتحلیل شبکه‌های اجتماعی به خود جلب کرده است [13]. از روش شناسایی اجتماعات می‌توان برای استخراج خواص مفیدی از شبکه‌ها استفاده کرد. اجتماع به گروهی از گره‌ها گفته می‌شود که دارای بیشترین تراکم یالها بین گره‌های گروهشان و کمترین تراکم یالها با گره‌های گروههای دیگر هستند. در شکل 3 یک شبکه اجتماعی که دارای 5 اجتماع ناهمپوشان10 است، رسم شده است.
شکل 3. یک گراف با پنج اجتماع ناهمپوشان
2.3.1. روش‌های تشخیص اجتماع
تاکنون، الگوریتم‌های زیادی برای یافتن اجتماعات در شبکه‌های پیچیده پیشنهاد شده است. در این بخش، یک مرور کلی بر چهار گروه مهم از الگوریتم‌های تشخیص اجتماعات ارائه شده‌است. شکل 4 نیز روش‌های کلی تشخیص اجتماعات را به تصویر کشیده است.
شکل 4. الگوریتم‌های شناسایی اجتماعات
2.3.1.1. الگوریتم‌های سنتی11
الف. تقسیم بندی گراف12
این روش گراف را به k خوشه با اندازه‌های ازپیش‌تعریف شده تقسیم می‌کند، به طوری که تعداد یال‌های داخل یک خوشه از تعداد یال‌های بین خوشه‌ها متراکم‌تر باشد. الگوریتم‌های مشهور تکنیک‌های تقسیم بندی گراف عبارتند از روش Spectral Bisection [14] و الگوریتم Kernighan-Lin [15].
ب. خوشه‌بندی سلسله مراتبی13
گراف‌ها ممکن است دارای ساختار سلسله مراتبی باشند، یعنی هر اجتماع ممکن است مجموعه‌ای از خوشه‌های کوچک در سطوح مختلف باشد. در مدل سلسله مراتبی نیاز به دانستن ماتریس شباهت و یا ماتریس الگو خواهیم داشت. هر چند این روش ما را از دانستن تعداد جوامع به عنوان ورودي بی نیاز می‌کند اما در عین حال تصمیم گیري براي اینکه درخت ایجاد شده در چه عمقی بهترین تقسیم شبکه را دارد قطعی نیست. ایجاد دسته‌هاي کوچک خوشه‌ها که معمولاً اطلاعات مهمی را نمی‌دهد از سایر معایب این روش به حساب می‌آید. الگوریتم‌های خوشه‌بندی سلسله مراتبی را می توان به دو دسته تقسیم کرد:
• الگوریتم‌های تجمعی: این یک تکنیک از پایین به بالا است زیرا در ابتدا هر گره را به عنوان یک خوشه جداگانه در نظر گرفته و به طور مکرر آنها را بر اساس بالاترین شباهت ادغام می‌کند و به اجتماع منحصر به فرد ختم می‌شود.
• الگوریتم‌های تقسیم کننده: این یک تکنیک از بالا به پایین است زیرا در ابتدا کل شبکه را به عنوان یک خوشه واحد در نظر می گیرد و با حذف یال‌های بین گره‌های کم‌شباهت، خوشه را به طور مکرر تقسیم می‌کند و به جوامع منحصر به فرد ختم می‌شود.
ج. خوشه‌بندی جزئی14
خوشه‌بندی جزئی یک گراف را به خوشه‌های غیر همپوشان از پیش تعیین شده تقسیم می‌کند. هدف این است که گره‌ها را به k خوشه تقسیم کنیم تا تابع هزینه را بر اساس اندازه‌گیری عدم شباهت بین گره‌ها حداکثر/حداقل کنیم. الگوریتم‌های k-mean [16] و fuzzy k-mean [16] نمونه‌هایی از تکنیک‌های خوشه‌بندی جزئی هستند.
د. خوشه‌بندی طیفی15
روش‌هاي طیفی نیز حجم زیادي از تحقیقات در این زمینه را شامل می شوند، چرا که اصولاً نتایج این دسته از الگوریتم‌ها در مقایسه با روش‌هاي مبتنی بر شباهت از کیفیت بالاتري برخوردار است. این روش‌هاي به عنوان پایه تئوریک براي طراحی الگوریتم‌هاي شناسایی اجتماع معرفی شده‌اند . در روش‌هاي تشخیص اجتماع مبتنی بر آنالیز طیف، یک الگوریتم خوشه‌بندي طیف نیمه نظارت شده با بررسی ماتریسی گره‌ها در شبکه و خوشه‌بندي طیف توسعه داده می‌شود. هر چند کیفیت این روش از روش‌هاي خوشه‌بندي محض بیشتر می باشد ولی غالبا سربار محاسباتی بالایی نیز دارد. الگوریتم Laplacian spectral partitioning [17] یک نمونه از تکنیک‌های خوشه‌بندی طیفی است.
ه. الگوریتم‌های تقسیم‌کننده16
این روش‌ها یال‌های بین‌خوشه‌ای را، بر اساس کمترین شباهت حذف می‌کند تا جوامع را از یکدیگر جدا کند. نمونه‌های اصلی این دسته شامل الگوریتم Girvan-Newman [18] است که در آن یالها به صورت تکراری بر اساس نمره میانگی یال17 حذف می شوند.
2.3.1.2. تکنیک‌های مبتنی بر بهینه‌سازی پیمانه‌ای18
پیمانگی19 یک تابع کیفیت برای تقریب جوامع است. هرچه مقدار پیمانگی بیشتر باشد، تقسیم‌بندی بهتر است. گریمان و نیومن معیار پیمانگی 
را بصورت زیر تعریف کردند [19]:
(5)
که در آن 
برابرتعداد یال‌های گراف، 
ماتریس مجاورتی گراف 
برابر درجه گره است. همچنین هرگاه دو گره و در یک اجتماع قرار داشته باشند، تابع 
مقدار 1 و درغیر اینصورت مقدار 0 را برمی‌گرداند. این دسته شامل سه تکنیک زیر است.
الف. تکنیک های حریصانه20
الگوریتم جستجوی حریصانه نیومن [20] اولین الگوریتم پیشنهادی برای بهینه‌سازی پیمانه‌ای بود. این یک تکنیک تجمعی است که در ابتدا، هر گره متعلق به یک پیمانه مجزا است، سپس آنها بر اساس افزایش مقدار پیمانگی به طور تکراری ادغام می شوند. الگوریتم CNM21 نسخه سریع الگوریتم حریص نیومن است که توسط ساختار داده های کارآمد اجرا می‌شود [21]. Louvain یک الگوریتم حریص مبتنی بر بهینه‌سازی پیمانه‌ای برای کشف جوامع در گرافهای وزنی پیچیده است [22]. این روش اجتماعات متفاونی را به هر گره اختصاص می‌دهد (هر گره یک اجتماع). سپس به طور مکرر گره‌ها را بر اساس افزایش مقدار پیمانگی ادغام می‌کند. در صورت عدم افزایش، گره در اجتماع خود باقی می‌ماند. این روش تا زمانی که امکان بهبود بیشتر وجود نداشته باشد، تکرار می‌شود.
ب. شبیه‌سازی تبریدی22
این یک رویکرد تصادفی گسسته است که از بهینه‌سازی پیمانه‌ای برای بهینه‌سازی جهانی23 تابع هدف استفاده می‌کند. در ابتدا، شبکه را به بخش‌های تصادفی تجزیه می‌کند. بهینه‌سازی بر اساس حرکات محلی24 و جهانی است. حرکتهای محلی، یک گره را به طور تصادفی از یک اجتماع به اجتماع دیگر بر اساس افزایش مقدار پیمانگی منتقل می‌کند. حرکتهای جهانی شامل تقسیم و ادغام اجتماعات است [23].
ج. الگوریتم‌های تکاملی25
الگوریتم‌های تکاملی یک کلاس از الگوریتم‌های بهینه‌سازی فرامکاشفه‌ای26 مبتنی بر هوش مصنوعی هستند. آنها به دلیل یادگیری موثر محلی و قابلیت های جستجوی جهانی معروف شده اند. الگوریتم‌های MLAMA-Net [24] و COMBO [25] نمونه‌هایی از تکنیک‌های خوشه‌بندی تکاملی هستند.
2.3.1.3. تکنیک های همپوشان27
تراكم كليك28 معروفترین روشي است كه براي شناسايي جوامع همپوشان در شبكه ها استفاده مي شود. ایده اصلی است که کلیک‌ها از یال‌های چگال داخل اجتماعات ساخته می‌شوند نه از یال‌های بین اجتماعات که پراکنده هستند. اجتماعاتی که از k کلیک ساخته شده باشند، به زیرگراف‌های کامل با k راس اشاره دارند. الگوریتم‌های CliquePercolation [26] ، انتشار برچسب [27]، SLPA29 [28] نمونه‌هایی از تکنیک‌های همپوشان هستند.
2.3.1.4. الگوریتم‌های پویا30
این بخش بر تکنیک‌های تشخیص اجتماع در شبکه‌های پویا، مانند توییتر، فیسبوک، لینکدین و غیره تمرکز می‌کند. این تکنیک‌ها تغییرات اجتماعات اعم از ایجاد یال‌های جدید و حذف آنها و همچنین اضافه یا حذف شدن گره‌ها را در طول به روزرسانی‌های زمانی در شبکه کنترل می‌کنند.
الف. پیاده‌روی تصادفی31
پیاده‌روی تصادفی [29] از محبوبترین الگوریتم‌هایی است که برای شناسایی جوامع مورد استفاده قرار گرفته‌است. در یک پیاده‌روی تصادفی، عابر شروع به قدم زدن در داخل یک اجتماع از یک گره می‌کند و در هر گام به طور تصادفی و یکنواخت به سمت گره مجاور انتخاب شده حرکت می‌کند. عابر به دلیل تراکم زیاد و مسیرهای متعدد مدت زیادی را در جوامع متراکم حرکت می‌کند. الگوریتم PageRank [30] و Infomap [31] نمونه‌هایی از محبوبترین الگوریتم‌ها بر اساس پیاده‌روی‌های تصادفی هستند.
ب. گسترش اجتماع32
یک گسترش اجتماع در یک شبکه مجموعه‌ای از گره‌ها است که با انتشار یک ویژگی، عمل یا اطلاعات مشابه در شبکه با هم گروه بندی می‌شوند. نمونه‌هایی از این دسته شامل الگوریتم‌های انتشار برچسب [27] و رنگ آمیزی گره پویا33 [32] است.
2.3.2. اجتماعات همپوشان34 و ناهمپوشان35
به دلیل ویژگیهای مفید ساختار اجتماعات در شبکه های اجتماعی، محققان در سال های اخیر به نقش اجتماعات در مسئله بیشینه‌سازی تأثیر توجه روزافزونی داشته اند. در مقایسه با روش‌های سنتی حریصانه/ابتکاری، روش‌های مبتنی بر اجتماعات می‌توانند زمان محاسبه را کاهش داده و اثربخشی را افزایش دهند [33]. روش‌های تشخیص اجتماعات به دو دسته تقسیم می‌شوند: تشخیص اجتماعات همپوشان و تشخیص اجتماعات بدون همپوشانی.
اجتماعات بدون همپوشانی: بعضی تحقیقات مبتنی بر اجتماعات هنگام تقسیم بندی یک گراف به اجتماعات، نقش گره‌های همپوشان (گره‌هایی که متعلق به بیش از یک اجتماع هستند) را در نظر نمی‌گیرند، یعنی آنها معمولاً تأثیر یک گره را صرفاً در محدوده اجتماع خودش ارزیابی می‌کنند. در واقع گره‌های همپوشان پیوندهایی هستند که جوامع مختلف را به هم متصل کرده و مسیرهای گسترش تأثیر بین آنها را ایجاد می‌کنند. نادیده گرفتن این گره‌های همپوشان، کیفیت مجموعه گره‌های تأثیرگذار انتخابی و میزان گسترش تأثیر را کاهش می‌دهد. از طرف دیگر از آنجایی که اجتماعات بدست آمده در این روش‌ها با یکدیگر همپوشانی ندارند، در نتیجه اندازه اجتماعات خروجی کوچکتر شده و باعث افزایش سرعت اجرای الگوریتم بیشینه‌سازی تأثیر خواهد شد.
اجتماعات همپوشان: در دنیای واقعی افراد ممکن است همزمان در چند اجتماع یک شبکه اجتماعی عضویت داشته باشند. به همین دلیل الگوریتم‌هایی پیشنهاد شدند که یک شبکه اجتماعی را به اجتماعات همپوشان بخش‌بندی کنند. از آنجا که گره‌های همپوشان اجتماعات مختلف را به هم متصل می کنند، هنگام فرایند گسترش تأثیر، اثربخشی الگوریتم را بهبود می بخشند [34]. ولی از آنجا که اجتماعات با یکدیگر همپوشانی دارند، ممکن است اندازه اجتماعات بدست‌آمده بزرگ شود که باعث کاهش کارایی زمانی الگوریتم انتخاب گره‌های تأثیرگذار خواهدشد.
بطورکلی در رویکردهای بیشینه‌سازی تأثیر مبتنی بر ساختار اجتماعات، انتخاب بین الگوریتم تشخیص اجتماعات همپوشان و ناهمپوشان منجر به یک تبادل بین کارایی زمانی و اثر بخشی الگوریتم بیشینه‌سازی تأثیر می‌شود.
2.3.3. شناسایی اجتماعات و مسئله بیشینه‌سازی تاثیر
مقوله شناسایی اجتماعات برای یافتن تأثیرگذارترین گره‌ها در شبکه‌های اجتماعی از دو جنبه حائز اهمیت است: 1. با افزایش اندازه شبکه‌های اجتماعی آنلاین، هزینه محاسباتی انتخاب تأثیرگذارترین گره‌ها به‌طور تصاعدی رشد می‌کند. در این شرایط، تقسیم شبکه به اجتماعات نقش اساسی در بهبود کارایی زمانی این مسئله دارد. 2. در دنیای واقعی، اطلاعات در بین افراد داخل اجتماع سریع‌تر و مؤثرتر منتشر می‌شود؛ بنابراین، با کشف اجتماعات و سپس انتشار اطلاعات در داخل آنها عملکرد بهتری از نظر میزان گسترش تأثیر حاصل خواهد شد. ازاین‌رو، تعدادی از محققان از ساختارهای اجتماعات برای افزایش کارایی زمانی و اثربخشی در مسئله‌ی بیشینه‌سازی تأثیر استفاده کرده‌اند که در بخش 3.3، مطالعات برجسته آنها مرور خواهد شد. در شکل 5، مثالی از انتخاب گره‌های تأثیرگذار یک شبکه ساده به کمک روش شناسایی اجتماعات نشان‌داده شده‌است. در گام 1 شبکه به سه اجتماع تقسیم‌بندی خواهد شد. سپس در گام 2، گره‌های تأثیرگذار هر اجتماع بدست خواهد آمد و مجموعه گره‌های نامزد را تشکیل خواهند داد. در گام آخر تأثیرگذارترین گره‌های شبکه صرفاً از میان مجموعه گره‌های نامزد انتخاب خواهند شد. در این شکل دایره های سیاه رنگ معرف گره‌های تأثیرگذار است.
شکل 5. شناسایی اجتماعات و بیشینه‌سازی تاثیر
2.4. مجموعه داده‌ها36
در این بخش برخی از مجموعه داده‌های معروف و پرکاربرد که برای تحقیق در حوزه بیشینه‌سازی تاثیر در شبکه‌های اجتماعی مناسب هستند معرفی شده و ویژگیهای آنها در جدول 2 لیست شده است.
NetHEPT یک شبکه از نوع همکاری در گروه آرشیو نظریه فیزیک انرژی بالا37 است. در این شبکه کوچک، اگر نویسنده‌ای حداقل در یک مقاله با نویسنده دیگر همکاری داشته باشد، بین آنها یک یال ایجاد می‌شود.
Epinions یک مجموعه داده جهتدار با اندازه متوسط از یک شبکه اجتماعی آنلاین است که در آن شخصی به شخص دیگر اعتماد38 می‌کند. در وب سایت این مجموعه داده، همه اعضا می‌توانند نظرات خود را در مورد محصولات ارسال کنند و سایر کاربران می‌توانند انتخاب کنند که به نظرات اعتماد کنند یا نه.
Digg-friend یک گراف دوستی جهتدار است. در این شبکه اجتماعی، کاربران با یکدیگر رابطه دوستی دارند.
Amazon این شبکه کالاهایی در آمازون است که بصورت زیر توسط آمازون ذکر شده است "مشتری که کالای A را خریداری کرده است کالای B را نیز خریداری کرده است". گره‌ها نمایانگر محصولات هستند و اگر محصول A اغلب با محصول B خریداری شود، گراف شامل یک یال جهتدار از محصول A به محصول B است.
Web-Google این مجموعه داده از گراف وب سایت شرکت گوگل گرفته شده است. در این مجموعه داده بزرگ، گره‌ها نشان‌دهنده صفحات هستند و یال‌های جهتدار نشان‌دهنده پیوندهای بین آنها است.
Youtube یک وبسایت اشتراک ویدیو هست که شامل شبکه اجتماعی کاربران یوتیوب و ارتباطات دوستی آنهاست.
Wikitopcats یک گراف از صفحات وب سایت ویکی‌پدیا است. این شبکه ابتدا با در اختیار گرفتن بزرگترین مولفه قویاً همبند از وب سایت ویکی‌پدیا ایجاد می‌شود. سپس به صفحات گروههای برتر این مولفه قویاً همبند (آنهایی که دارای حداقل 100 صفحه هستند) محدود می‌شود. در نهایت این مجموعه داده شامل بزرگترین مولفه قویاً همبند از این گراف محدود شده خواهد بود.
Pokec یک شبکه اجتماعی دوستی است. این شبکه یکی از مجموعه داده‌های بسیار بزرگ است که شامل 1.6 میلیون گره و 30.1 میلیون یال جهت دار است.
Flickr شبکه اجتماعی کاربران فلیکر و ارتباطات دوستی آنهاست. این شبکه با ایجاد یال‌هایی بین تصاویر به اشتراک گذاشته شده ساخته شده است.
LiveJournal یک شبکه اجتماعی رایگان نمونه‌گیری شده است. گره‌ها کاربران این شبکه هستند و یال‌های جهتدار نشان دهنده‌ی رابطه دوستی میان کاربرانند. این مجموعه داده شامل حدود 4.8 میلیون گره، با 34.5 میلیون جفت روابط دوستی (68.9 میلیون یال جهتدار) است.
3. سازمان‌دهی الگوریتم‌های بیشینه‌سازی تأثیر
مسئله‌ی بیشینه‌سازی تأثیر ابتدا توسط دومینگوس و ریچاردسون در سال 2001 به‌عنوان یک مسئله احتمالی مطرح [3] و سپس در سال 2003 توسط کمپ و همکاران [4] به‌عنوان یک مسئله بهینه‌سازی گسسته فرموله شد. بعد از آنها، نویسندگان به بررسی جنبه سختی مسئله و ارائه راه‌حل‌هایی پرداختند. ازآنجاکه یافتن راه‌حل بهینه در مسائل NP-Hard بسیار بغرنج است، رویکردهای تقریبی جایگزینی‌های بهتری هستند. به‌طورکلی در مسئله‌ی بیشینه‌سازی تأثیر، انتخاب افراد تأثیرگذار به‌وسیله روش‌های رتبه‌بندی مرکزیت درجه39، حریصانه40 و مکاشفه‌ای41 انجام می‌شود [10]. روش رتبه‌بندی درجه، افراد تأثیرگذار را بر اساس درجه آنها انتخاب می‌کند. به‌عبارت‌دیگر، همه گره‌های شبکه از بالاترین درجه به پایین‌ترین درجه به ترتیب نزولی رتبه‌بندی می‌شوند و افراد تأثیرگذار از بالای لیست انتخاب می‌شوند. الگوریتم حریصانه با انتخاب بهینه محلی در هر مرحله، افراد تأثیرگذار را انتخاب می‌کند. تکنیک‌های مکاشفه‌ای هر روش به‌کارگرفته شده برای یادگیری، کشف یا حل مسائل هستند. در این نوع روش‌ها علیرغم حرکت به سمت راه‌حل بهینه، هیچ تضمینی برای کیفیت پاسخ نهایی وجود ندارد.
نماد | شرح |
| گراف |
| به ترتیب برابر تعداد گره‌ها و یالها در گراف |
| مجموعه سبد گره‌های فعال |
| تعداد عناصر مجموعه |
| تعداد شبیه‌سازی مونت‌کارلو |
| مدل انتشار |
| تعداد گره‌های تحت تأثیرقرارگرفته توسط مجموعه S تحت مدل انتشار M در گراف G |
| حد آستانه فعال‌سازی گره v در مدل انتشار آستانه خطی |
| احتمال فعال‌سازی گره v در مدل انتشار آبشاری مستقل |
| وزن تأثیریال جهتدار (v,u) از گره v به سمت گره u |
| مجموعه همسایگان ورودی گره |
| مجموعه همسایگان خروجی گره |
| درجه گره |
| درجه ورودی گره |
| درجه خروجی گره |
جدول2. مجموعه داده‌های پرکاربرد در حوزه بیشینه‌سازی تاثیر در شبکه‌های اجتماعی
|
الگوریتم‌های حریصانه معمولاً از چارچوب حریصانه برای حل مسائل بهینه‌سازی استفاده می‌کنند. ازاین‌رو، این الگوریتم‌ها با در نظر گرفتن شرایط مسئله همیشه بهترین راه‌حل را انتخاب می‌کنند به امید آنکه ادامه این روند منجر به بهینه‌سازی شود. در برخی مسائل سخت که الگوریتم‌های حریصانه و کلاسیک زمان اجرای بسیار طولانی دارند، الگوریتم‌های مکاشفه‌ای مورد استفاده قرار می‌گیرند. الگوریتم‌های مکاشفه‌ای دسته‌ای از الگوریتم‌های تقریبی هستند که می‌توانند در مدت‌زمان کوتاهی راه‌حل‌های تقریبی نزدیک به راه‌حل بهینه پیدا کنند. در الگوریتم‌های مبتنی بر اجتماعات که نوعی استراتژی تقسیم و غیال هستند، ابتدا کل شبکه اجتماعی به اجتماعات کوچکتر تقسیم می‌شود و سپس یکی از الگوریتم‌های حریصانه یا مکاشفه‌ای یا ترکیبی از آنها برای یافتن تأثیرگذارترین افراد مورد استفاده قرار خواهند گرفت. در بخش‌های بعدی، رویکردهای موجود در مسئله‌ی بیشینه‌سازی تأثیر بررسی می‌شوند.
شکل 6. طبقه بندی الگوریتم‌های ارائه‌شده در بیشینه‌سازی تأثیر
کمپ و همکاران در سال 2003 مسئله‌ی بیشینه‌سازی تأثیر را به‌عنوان یک مسئله بهینه‌سازی ترکیبی تحت دو مدل انتشار متداول آبشاری مستقل و آستانه‌ی خطی فرموله کردند. آنها ثابت کردند که مسئله‌ی بیشینه‌سازی تأثیر تحت این دو مدل NP-Hard است و یک الگوریتم حریصانه با تقریب 63% از پاسخ بهینه ارائه دادند [4]. در هر تکرار از اجرای الگوریتم، یک گره با بیشترین سود حاشیه‌ای42 به مجموعه سبد S اضافه می‌شود تا اینکه تعداد گره‌های مجموعه S تأمین شود. محاسبه دقیق میزان گسترش تأثیر تحت این دو مدل #NP-Hard است؛ بنابراین این الگوریتم حریصانه مجبور است که شبیه‌سازی‌های مونت‌کارلو43 را حدود 10 هزار بار تکرار کند تا به یک تقریب بهتر برسد. این سربار محاسباتی زیاد، باعث کاهش کارایی زمان در شبکه‌های اجتماعی بزرگ خواهد شد [9]. تلاش‌های زیادی برای مقابله با چالش کارایی زمان این الگوریتم حریصانه انجام شده است.
لسکوویچ و همکاران در سال 2007 از خاصیت زیرپیمانه‌ای‌بودن تابع گسترش تأثیر استفاده کردند و الگوریتمی کارآمد به نام CELF44 پیشنهاد دادند [35]. ایده آنها این است که سود حاشیه‌ای هر گره در دور فعلی نمی‌تواند از سود حاشیه‌ای‌اش در دورهای قبلی بیشتر باشد. الگوریتم بدین‌صورت است که در تکرار اول، گسترش تأثیر همه گره‌ها محاسبه و سپس گره‌ها به ترتیب نزولی میزان گسترش تأثیرشان در یک صف مرتب می‌شوند. اولین گره صف برداشته شده و به مجموعه سبد S اضافه می‌شود. در بقیه تکرارها، مقدار گسترش تأثیر فقط برای گره جلویی صف محاسبه می‌شود. پس از مرتب کردن مجدد صف، اگر اولین گره در صف همچنان در جلوی صف باقی بماند، آنگاه آن گره دارای بیشترین سود حاشیه‌ای است که باید از صف حذف شده و به مجموعه سبد S اضافه شود. الگوریتم CELF با اجتناب از محاسبه میزان تأثیر در بسیاری از گره‌ها، پیچیدگی زمانی الگوریتم حریصانهی کمپ را کاهش می‌دهد و سرعت آن را 700 برابر بهبود می‌بخشد. زمان بالای اجرای دور اول الگوریتم چالش اصلی CELF است؛ زیرا مانند الگوریتم حریصانهی کمپ، باید تأثیر همه گره‌ها در دور اول محاسبه شود.
الگوریتم CELF++ که توسط گویال و همکاران در سال 2011 معرفی شد [36]، با اجتناب از شبیه‌سازی‌های غیرضروری مونت‌کارلو به 30-50٪ بهبود در زمان اجرا نسبت به الگوریتم CELF دست می‌یابد. در عمل و در مواجهه با شبکه های بزرگتر، افزایش سرعت قابل توجهی نسبت به CELF مشاهده نشد [37].
ژو و همکاران در سال 2015 روشی به نام UBLF45 را برای به دست آوردن کران بالای تابع گسترش تأثیر با استفاده از ماتریس‌ها پیشنهاد کند [38]. نتایج گزارش‌شده حاکی از کاهش بیش از 95 درصدی شبیه‌سازی مونت‌کارلو و البته بهبود کارایی زمانی 2 تا 10 برابر سریع‌تر از CELF بود. این روش همانند الگوریتم‌های CELF و CELF++ علیرغم تولید مجموعه سبد با کیفیت بالا، پیچیدگی بدترین زمان اجرا را بهبود نمی‌دهد. همچنین این الگوریتم فقط برای دو مدل انتشار آبشاری مستقل و آستانه خطی طراحی شده است.
الگوریتم NewGreedy نسخه بهبودیافته الگوریتم حریصانهی کمپ است که توسط چن و همکاران در سال 2009 ارائه شد [39]. ایده اصلی ایجاد گراف کوچکتر با حذف یال‌هایی است که نقشی در روند انتشار اطلاعات ندارند. با توجه به این ایده، فضای جستجو کاهش می‌یابد و سرعت افزایش می‌یابد. یکی از معضلات الگوریتم NewGreedy زمان طولانی ایجاد گراف کوچکتر در هر مرحله از تکرار اصلی الگوریتم حریصانه است که منجر به ناکارآمدی در گراف های بزرگ می‌شود. برای دستیابی به نتایج بهتر، نویسندگان الگوریتم MixedGreedy را پیشنهاد کردند که الگوریتم NewGreedy را در اولین تکرار و الگوریتم CELF را در بقیه تکرارها اجرا می‌کند. در عمل این الگوریتم نیز نسبت به NewGreedy افزایش سرعت قابل توجهی نداشت [37].
در الگوریتم staticGreedy که توسط چنگ و همکاران در سال 2013 معرفی شد [40]، در ابتدا چند تصویر لحظه‌ای46 از شبیه‌سازی مونت‌کارلو گرفته می‌شود. در مرحله بعد، k گره با بیشترین سود حاشیه‌ای در بین همه تصاویر نمونه‌برداری شده، به‌عنوان گره‌های مجموعه سبد انتخاب می‌شوند. به دلیل پیچیدگی زمانی اجتناب‌ناپذیر staticGreedy در بدترین حالت 
، از یک روش هرس برای کاهش زمان اجرای آن در الگوریتم staticGreedyDU استفاده می‌شود.
الگوریتم Pruned-MC47 که توسط اوزاکا و همکارانش در سال 2014 معرفی شد، یک روش نمونه‌گیری مبتنی بر تصویر لحظه‌ای است [41]. با استفاده از یک ساختار شاخص‌گذاری روی تصاویر لحظه‌ای به همراه تکنیک هرس کردن، کارایی الگوریتم staticGreedyDU بهبود یافته و زمان اجرا کاهش می‌یابد.
علیرغم بهبود اثربخشی و استخراج گره‌های تاثیرگذار با کیفیت بالا در هر سه الگوریتم staticGreedy، staticGreedyDU و Pruned-MC،، پیچیدگی زمانی بدترین حالت آنها بسیار پرهزینه است به‌خصوص در مواجهه با گراف‌هایی با میلیون‌ها گره و میلیارها یال.
تانگ و همکاران در سال 2014 الگوریتم دو فاز TIM48 را در حوزه مسئله‌ی بیشینه‌سازی تأثیر معرفی کردند [42]. در فاز اول به‌منظور تخمین پارامتر φ، یک کران پایین روی بیشترین مقدار گسترش تأثیر به دست می‌آید. در مرحله دوم، تعداد φ عدد دستیابی‌معکوس49 از گراف انتخاب می‌شود. سرانجام، k گره که بیشترین تعداد دستیابی‌معکوس را پوشش می‌دهد به‌عنوان گره‌های نهایی مجموعه سبد انتخاب می‌شوند. الگوریتم TIM+ نسخه بهبودیافته TIM است که برای سرعت بخشیدن به روش تخمین پارامتر φ پیشنهاد شده است. TIM دو برابر سریع‌تر از CELF++ و TIM+ دو برابر سریع‌تر از TIM است.
الگوریتم IMM50 که توسط تانگ و همکاران در سال 2015 معرفی شد [43]، یک روش دوفازی مشابه الگوریتم TIM است که از تکنیک‌های پیشرفته تخمین مانند روش مارتینگل51 استفاده می‌کند. مصرف زیاد حافظه یکی از مهم‌ترین اشکالات TIM، TIM+ و IMM است. زیرا اولاً آنها برای اطمینان از کران پایین مجبور به تولید تعداد زیادی نمونه (دستیابی‌معکوس) هستند. ثانیاً می‌بایست همه‌ی نمونه‌ها را بصورت همزمان در حافظه نگهداری کنند تا روش حریصانه k گره تاثیرگذار را انتخاب کند.
بیشتر الگوریتم‌های ذکرشده در این بخش، باوجود ارائه ضمانت تئوری نمی‌توانند شبکه‌های اجتماعی در مقیاس بزرگ را کنترل کنند.
با توجه به پیچیدگی زمانی بالای الگوریتم‌های حریصانه فوق و ناکارآمد بودن آنها در مواجهه با شبکه‌های اجتماعی بسیار بزرگ، طیف گسترده‌ای از الگوریتم‌های مکاشفه‌ای برای حل معضل کارایی در مسئله‌ی بیشینه‌سازی تأثیر ارائه شده است. یکی از متداول‌ترین ایده‌های مکاشفه‌ای، انتخاب گره‌های تأثیرگذار بر اساس درجه آنها است. مرکزیت درجه52، مرکزیت نزدیکی53، مرکزیت بینابینی54، مرکزیت بردار ویژه55، رتبه‌بندی صفحات56 و HITS57 از معروفترین رویکردهای مکاشفه‌ای بر اساس درجه‌ی گره‌ها هستند. دو عیب اصلی الگوریتم‌های مبتنی بر درجه‌ی گره به شرح زیر است: 1- درجه‌ی گره و انتشار اطلاعات دو مفهوم متفاوت و مجزا هستند. 2. ازآنجاکه این دسته از الگوریتم‌های مکاشفه‌ای، همپوشانی تأثیر بین سبدهای مختلف را در نظر نمی‌گیرند، پدیده تخمین بیش‌ازحد58 رخ می‌دهد.
چن و همکاران در سال 2009 الگوریتم DegreeDiscount را برای به‌حساب آوردن همپوشانی تأثیر گره‌ها پیشنهاد دادند [39]. در این الگوریتم پس از انتخاب یک گره با بیشترین درجه به‌عنوان گره تأثیرگذار، نمرات تأثیر همسایگان آن گره یک واحد کاهش می‌یابد. عیب اصلی این رویکرد این است که فقط تأثیر همسایگان مستقیم را در نظر می‌گیرد و تأثیر مسیرها و همسایگان غیرمستقیم را نادیده می‌گیرد.
ازآنجاکه محاسبه میزان تأثیر در گراف جهت دار بدون دور (DAG59) دقیق و کارآمد است، چن و همکارانش در سال 2010 مدل LDAG60 را پیشنهاد کردند [44]. در این مدل، برای هر گره DAG های محلی ساخته می‌شود. سپس، الگوریتم حریصانهی کمپ برای یافتن گره‌های تأثیرگذار بر روی هر DAG اعمال می‌شود. در شبکه‌های اجتماعی بزرگ، روند ساخت DAG ها ازنظر مصرف حافظه و زمان اجرا بسیار ناکارآمد است.
SP1M نام الگوریتمی است که توسط کیمورا و همکاران در سال 2010 معرفی شده است [45]. ایده اصلی آن در نظر گرفتن کوتاه‌ترین مسیر از گره u به گره v برای فعال‌سازی است. الگوریتم SP1M61 نیازی به اجرای سنگین شبیه‌سازی‌های مونت‌کارلو ندارد. البته از آنجایی که SP1M برای محاسبه میزان گسترش تأثیر صرفاً طول مسیر را درنظر گرفته و احتمالات را نادیده می‌گیرد قادر به تولید جواب تقریبی خوبی در همه‌ی گراف‌ها نیست.
با الهام از ایده SP1M، در سال 2010 چن و همکاران مدلهای MIA62 و PMIA63 را پیشنهاد دادند [46]. مدل MIA دامنه پخش اطلاعات را از کل گراف به یک ساختار درختی محلی، محدود می‌کند. ازآنجاکه محاسبه تأثیر در یک درخت با دقت و کارایی بیشتری انجام می‌شود، میزان گسترش تأثیر سریع‌تر تخمین زده می‌شود؛ بنابراین از شبیه‌سازی گران‌قیمت مونت‌کارلو اجتناب خواهد شد. به‌منظور اینکه مجموعه سبد فعلی تأثیرسبدهای بعدی را مسدود نکند، مدل PMIA تأثیر درون ساختار درخت را پس از افزودن گره به مجموعه سبد اصلاح می‌کند. اشکال اصلی این الگوریتم‌ها معضل مقیاس‌پذیری در گرافهای متراکم است. همچنین در جایی که اندازه ساختارهای درختان محلی خیلی بزرگ شوند، دقت تخمین میزان گسترش تأثیر کم خواهد شد.
ایده الگوریتم SimplePath که توسط گویال و همکاران در سال 2011 پیشنهاد شده است، محاسبه تأثیر مجموعه سبد تحت مدل آستانه خطی است [47]. این کار با شمارش تمام مسیرهای ساده از هر گره در مجموعه سبد انجام می‌شود. ازآنجاکه شمارش تمام مسیرهای ساده در گراف #P-Hard است، از تکنیک هرس‌کردن استفاده می‌شود. این الگوریتم، از بهینه‌سازی CELF[35] برای کارایی بیشتر بهره می‌برد. این الگوریتم بر خلاف الگوریتم LDAG[44]، میزان گسترش تأثیر را بدون شمارش همه‌ی مسیرهای ساده روی گراف اصلی تخمین می‌زند. از این رو زمان و حافظه بهتری نسبت به الگوریتم LDAG دارد [48]. نقطه ضعف الگوریتم SimplePath استفاده از خصوصیات مدل انتشار آستانه خطی برای تخمین میزان تأثیر است، از این رو قابل تعمیم به سایر مدلهای انتشار نیست.
در کل روش‌های مبتنی‌بر شمارش مسیر مانند LDAG، SP1M، MIA، PMIA و SimPath در مورادی که تعداد مسیرهای تأثیر گره‌ها یا محدوده تأثیر گره‌ها بزرگ باشد، نمی‌توانند توازنی بین کارایی و دقت برقرار کنند.
نارایانام و همکاران در سال 2011 الگوریتم SPIN64 را معرفی کردند که در آن گره‌ها نقش بازیکنان در بازی‌های ائتلافی را ایفا می‌کنند [49]. فرآیند انتشار اطلاعات در SPIN مشابه آنچه که در اتحاد ائتلاف اتفاق می‌افتد، انجام می‌شود. در این مدل، گره‌ها با توجه به مقدار شپلی آنها رتبه‌بندی می‌شوند و سپس k تا از بالاترین آنها به‌عنوان گره‌های مجموعه سبد انتخاب می‌شوند. این الگوریتم علیرغم داشتن زمان اجرای خوب نمی‌تواند هیچ ضمانتی روی کران بدترین حالت فراهم کند. همچنین از آنجا که این الگوریتم صرفاً برای مدل انتشار آستانه‌ی خطی طراحی شده است، برای سایر مدل های انتشار قابل استفاده نیست.
الگوریتم IRIE65 تعمیم الگوریتم PageRank[30] است که توسط یونگ و همکاران در سال 2012 پیشنهاد شده است [50]. الگوریتم IRIE از دو عملیات اصلی تشکیل شده است: رتبه‌بندی تأثیر(IR) و تخمین تأثیر(IE). روش کار بدین‌صورت است که یک دستگاه معادلاتی شامل n معادله خطی با n متغیر به‌منظور به دست آوردن لیست رتبه‌بندی تأثیرات گره‌ها ساخته و حل می‌شود. اگر k گره بالای لیست رتبه‌بندی تأثیر به‌دست‌آمده به‌عنوان مجموعه سبد نهایی انتخاب شوند، پدیده همپوشانی تأثیر66 رخ خواهد داد. برای جلوگیری از این امر، نویسندگان تکنیک تخمین تأثیر را برای محاسبه و تفریق تأثیر اضافی مجموعه سبد بر گره‌های دیگر معرفی کردند. برمبنای پیشنهاد نویسندگان، استفاده از الگوریتم‌های دیگر مانند Greedy یا PMIA به منظور محاسبه تأثیر اضافی مجموعه سبد باعث افزایش زمان اجرای این الگوریتم خواهد شد.
لئو و همکاران در سال 2014 یک چارچوب حریصانه به نام Group-PR ارائه کردند که بسطی از الگوریتم PageRank است [51]. این الگوریتم به‌جای استفاده از یک گره، از مجموعه‌ای از گره‌ها برای محاسبه میزان گسترش تأثیر استفاده می‌کند. در مرحله اول، امتیاز PageRank هر گره محاسبه می‌شود. در مرحله دوم، گرهای با بیشترین سود حاشیه‌ای به مجموعه سبد اضافه می‌شود. این فرآیند با اضافه شدن k گره به مجموعه سبد خاتمه می‌یابد.
چارچوب IMRank67 یک استراتژی مبتنی بر رتبه‌بندی است که توسط چنگ و همکاران در سال 2014 ارائه شده است [52]. ایده این چارچوب تکراری، کشف رتبه‌بندی خود-سازگار68 از هر رتبه‌بندی اولیه است. پس از کشف لیست رتبه‌بندی خود-سازگار، k گره بالایی آن لیست به‌عنوان اعضای تأثیرگذارتر به مجموعه سبد اضافه خواهند شد.
روش‌های مبتنی بر رتبه‌بندی مانند IMRank، PageRank، IRIE و Group-PR سربار محاسباتی را بسیار کاهش می‌دهند. اما از آنجا که نحوه سازوکار این الگوریتم‌ها با ماهیت مسئله‌ی بیشینه‌سازی‌تأثیر متفاوت است، گسترش تأثیر تخمین زده شده می‌تواند با گسترش تأثیر واقعی گره‌ها تحت مدلهای انتشار اختلاف جدی داشته باشد. بعلاوه خصوصیات مدلهای انتشار در این دسته از الگوریتم‌ها نادیده گرفته شده‌است.
IPA69 نام الگوریتم مبتنی بر مسیر است که توسط کیم و همکاران در سال 2013 ارائه شده است. فرض این الگوریتم بر این است که مسیرهای انتشار از یکدیگر مستقل هستند؛ بنابراین برای محاسبه گسترش تأثیر، از یک روش موازی‌سازی با کارایی بیشتر استفاده می‌کند. اشکالات الگوریتم PMIA [46] به این الگوریتم نیز وارد است.
گالوترا و همکاران در سال 2016 مدلی به نام EaSyIM ارائه دادند [53]. ایده اصلی آن شمارش مسیرهای ساده برای تخمین تأثیر هر گره بود. این مدل از روش IRIE[50] برای تخمین تأثیر سراسری گره‌ها و دستیابی به عملکرد بهتر استفاده می‌کند. نتایج تجربی گزارش‌شده در این تحقیق نشان‌دهنده گسترش تأثیر بهتر و زمان اجرای کمتر در مقایسه با الگوریتم‌های دیگر مانند CELF++[36] و TIM+[42] است.
گورسوی و همکاران در سال 2018 مسئله‌ی بیشینه‌سازی تاثیرهدفمند و بودجه دار را تحت مدل آستانه خطی قطعی تعریف و مدل مقیاس پذیر TABU–PG70 را طراحی کردند [54]. این مدل یک الگوریتم تکراری و حریصانه بر مبنای پیشنهادات بالقوه در زمان انتخاب گره‌های سبد است. این مدل با بهره‌گیری از تکنیک‌های مقیاس‌پذیری سعی در کاهش زمان اجرا با محدود کردن تعداد گره‌های نامزد یا با انتخالب چند گره در یک مرتبه دارد. این موارد منجر به تبادلی بین زمان اجرا و میزان اثربخشی الگوریتم خواهد شد.
TIFIM71 یک چارچوب تکراری دو مرحله‌ای برای بیشینه‌سازی تأثیر است که توسط هی و همکاران در سال 2019 پیشنهاد شد [55]. در مرحله اول به منظور حذف گره‌های کم‌اهمیت و کاهش پیچیدگی محاسبات، یک چارچوب تکراری به ترتیب نزولی برای انتخاب گره‌های نامزد پیشنهاد می‌شود. برای محاسبه سود گسترش هر گره، استراتژی تخصیص اولین و آخرین72 بر اساس نتایج آخرین تکرار و معیار اندازه گیری دو مرحله ای73 ارائه شده است. در مرحله دوم، مفهوم تسلط آپیکال74 را برای محاسبه پدیده همپوشانی گسترش در بین گره‌ها تعریف شده است. نویسندگان ادعا کردند که الگوریتم پیشنهادیشان قادر به تولید یک مجموعه سبد باکیفیت تر از الگوریتم IMM [43] در زمانی نزدیک به الگوریتم PageRank هست.
MLIM75 یک الگوریتم بر مبنای حداکثر احتمال است که توسط لیو و همکاران در سال 2020 برای مدل انتشار آبشاری مستقل پیشنهاد شده است [56]. در ابتدا با استفاده از معیار حداکثر احتمال مقدار L برای هر راس محاسبه خواهد شد. سپس یک الگوریتم حریصانه پیشنهاد شده است تا گره‌ها را به ترتیب کوچترین مقدار L به مجموعه سبد اضافه کند. نتایج گزارش شده نشان داده است که الگوریتم پیشنهادی توانسته اثربخشی بیشتری را در حین به دست آوردن زمان کمتر در مقایسه با الگوریتم‌های نه چندان مطرح ایجاد کند.
ونگ و همکاران در سال 2021، مساله بیشینه‌سازی نفوذ نامتجانس 76(DIM)را مورد بررسی قرار دادند که هدف آن انتخاب K گره به گونه‌ای است که هم تعداد گره‌های فعال شده و هم تنوع گره‌های فعال شده را بتوان به حداکثر رساند [57]. آنها با طراحی یک تابع تنوع برای مدل کردن توزیع گره‌های فعال در میان همه جوامع، مساله DIM را با به حداکثر رساندن یک ترکیب خطی پارامتری از تنوع و تعداد گره فعال مدل کردند. همچنین برای مقابله با NP-Hardness، یک الگوریتم بیشینه‌سازی نفوذ متنوع کارآمد از طریق مارتینگل را پیشنهاد کردند که جواب تقریبی 
را باز می‌گرداند.
الگوریتم‌های مکاشفه‌ای ذکرشده در این بخش زمان اجرای بهتری نسبت به الگوریتم‌های حریصانه در بخش قبلی دارند. بااین‌وجود، این الگوریتم‌ها نمی‌توانند کران بدترین حالت را فراهم کنند و ازلحاظ نظری ضعیف هستند. جدول 3 الگوریتم‌های حریصانه و مکاشفه‌ای مطرح و برجسته درزمینه‌ی بیشینه‌سازی تأثیر در شبکه‌های اجتماعی را نشان می‌دهد.
3.3. رویکردهای مبتنی بر شناسایی اجتماعات
اجتماعات ساختارهای پنهان و یکی از مهم‌ترین خصوصیات ذاتی شبکه‌های اجتماعی هستند. همه رویکردهای حریصانه و مکاشفه‌ای ذکرشده در دو بخش قبلی عمدتاً بر ارتباطات بین گره‌ها و مکانیسم انتشار اطلاعات متمرکز هستند و نقش حیاتی ساختارهای اجتماعات در یک شبکه اجتماعی را نادیده گرفته‌اند. افزایش تصاعدی اندازه شبکه‌های اجتماعی و گسترش سریع‌تر و مؤثرتر اطلاعات در داخل اجتماعات، اصلی‌ترین عواملی هستند که توجه محققان را به استفاده از رویکردهای مبتنی بر اجتماعات جلب کرده است. واضح است که این استراتژی تقسیم و غیال نقش مهمی در کارایی زمانی و اثربخشی مسئله‌ی بیشینه‌سازی تأثیر دارد.
اولین بار در سال 2010، وانگ و همکاران سعی کردند که معضل مقیاس‌پذیری در مسئله‌ی بیشینه‌سازی تأثیر را با بهره‌گیری از ساختارهای اجتماعات بهبود بخشند [58]. آنها الگوریتم CGA77 را پیشنهاد دادند که در ابتدا گراف را به اجتماعات کوچکتر تقسیم می‌کند. سپس با استفاده از برنامه‌نویسی پویا آن اجتماعی را که باید برای یافتن گره‌های تأثیرگذار بررسی شود، انتخاب می‌کند. نتایج تجربی آنها نشان داد که CGA نمی‌تواند از عهده شبکه‌های اجتماعی در مقیاس بزرگ برآید.
مدل CIM78 که توسط چن و همکاران در سال 2014 پیشنهاد شد [59]، با فرایند شناسایی اجتماعات با سیاست عدم همپوشانی اطلاعات آغاز می‌شود. سپس برای هر اجتماع، یک مجموعه سبد اولیه ساخته می‌شود. سرانجام گره‌های تأثیرگذار نهایی، از مجموعه سبدهای اولیه متناسب با تعداد گره هر سبد، انتخاب خواهند شد. علیرغم کارایی زمانی خیلی‌خوب مدل CIM، فرض نادرست عدم همپوشانی اطلاعات در فرایند شناسایی اجتماعات منجر به کاهش میزان گسترش تأثیر و دقت این مدل شده است.
با استفاده از مفهوم انطباق79، لی و همکاران در سال 2015 الگوریتمی به نام CINEMA80 بر مبنای ساختار اجتماعات ابداع کردند [60]. پس از مرحله شناسایی اجتماع، گره‌های تأثیرگذار نهایی بر اساس بیشترین بهره کسب کرده در داخل اجتماعات شناسایی‌شده، انتخاب می‌شوند. CINEMA به دلیل استفاده از شبیه‌سازی‌های پرهزینه مونت‌کارلو در شبکه‌های بزرگ قابل استفاده نیست. همچنین صرفاً به‌کارگیری معیار بیشترین بهره برای یافتن گره‌های تأثیرگذار در داخل اجتماعات منجر به کاهش دقت این الگوریتم شده است.
رحیم‌خانی و همکاران در سال 2015 مدل ComPath را ارائه دادند که برای شناسایی اجتماعات از الگوریتم [28]SLPA81 استفاده می‌کرد [61]. در این مدل، تأثیرگذارترین اجتماعات و تأثیرگذارترین گره‌های هر اجتماع بر اساس معیار مرکزیت درجه شناسایی می‌شوند. در پایان، گره‌های تأثیرگذار نهایی از میان گره‌های کاندیدای اجتماعات بر اساس معیار فاصله داخلی82 انتخاب می‌شوند.
در مدل INCIM که توسط بزرگی و همکاران در سال 2016 ارائه شده [62]، هر اجتماع به‌عنوان یک گره جداگانه در نظر گرفته می‌شود؛ بنابراین یک گراف جدید ساخته می‌شود که گره‌های آن اجتماعات گراف پایه هستند. در این گراف جدید، هر گره (اجتماع) را می‌توان به‌عنوان یک ماژول انتشار مجزا در نظر گرفت. به‌طورکلی، ابتدا اجتماعات توسط SLPA [28] شناسایی و سپس گراف جدید اجتماعات ساخته می‌شود. همچنین، الگوریتم [47]SimplePath برای محاسبه گسترش تأثیر و استخراج گره‌های تأثیرگذار مورد استفاده قرار گرفته است. پیچیدگی زمانی بالای الگوریتم SimplePath در شبکه‌های بزرگ چالش اصلی INCIM است که
سعی شده است با بهینه‌سازی CELF [35] بهبود یابد. جدول 3. الگوریتم‌های برجسته حریصانه و مکاشفه‌ای علائم اختصاری:
هالاپاناوار و همکاران در سال 2016 مدلی را برای تسریع در فرانید اکتشاف گره‌های تأثیرگذار در شبکه‌های پیچیده با استفاده از شناسایی اجتماعات ایجاد کرند [63]. تعبیه یک روش موازی‌سازی در الگوریتم Louvain [22] نقطه قوت روش آنهاست. همچنین، در این مقاله به‌طور عملی نشان داده‌شده است که با استفاده از رویکرد شناسایی گره در اجتماعات شناسایی‌شده و در نهایت تجمیع سبدها، میزان گسترش تأثیر به‌طور قابل‌توجهی افزایش یافته است. ژائو و همکاران در سال 2016 الگوریتمی معرفی کردند که در آن گام‌های شناسایی اجتماعات و محاسبه گسترش تأثیرگره‌ها با هم تجمیع شده‌اند [64]. با توجه به الگوریتم ارائه شده، تأثیرگذارترین گره در اجتماع می‌تواند برچسب خود را در طی فرآیند انتشار به همه گره‌های دیگر در اجتماعش منتشر کند. همچنین، آنها معیاری برای محاسبه مرکزیت گره‌ها تعریف کردند. این مدل در مقایسه با سایر الگوریتم‌ها به برتری متمایزی هم از لحاظ کارایی زمانی و هم از لحاظ اثربخشی در گراف‌هایی با اندازه متوسط دست یافت. ازآن‌جایی که دو گام شناسایی اجتماعات و یافتن گره‌های تاثیرگذار با هم تجمیع شده اند، زمان اجرای الگوریتم بسیار بهبود می یابد. از طرف دیگر از آنجا که اجتماعات بوسیله‌ی روش انتشار برچسب شکل می‌گیرند، اجتماعات حاصل با ذات مسئله‌ی بیشینه‌سازی تأثیر(سازوکار مدلهای انتشار) بسیار سازگار و منطبق هستند. در نتیجه این الگوریتم گره‌های تاثیرگذار را با دقت بالاتری انتخاب می‌کند. الگوریتم DIN83 یک مدل بدون پارامتر بر مبنای ترکیبی از جنبه‌های ساختاری و معنایی اجتماعات است که توسط جاادی و همکاران در سال 2016 پیشنهاد شده است [65]. ایده‌های اصلی این الگوریتم شناسایی اجتماعات همپوشان، مدل‌سازی معنایی هر اجتماع و سپس انتخاب گره‌های تأثیرگذار است. بدون پارامتر بودن و استخراج اجتماعات همپوشان (همانند شبکه‌های اجتماعی واقعی) از نقاط قوت این الگوریتم به شمار می‌آیند. اما فرآیند مدل‌سازی معنایی هر اجتماع در جاهایی که اندازه اجتماعات بزرگ باشد منجر به کندی الگوریتم خواهد شد. شانگ و همکاران در سال 2016 یک چارچوب حریصانه بر مبنای شناسایی اجتماعات به نام CoFIM84 ارائه دادند [66]. در این الگوریتم فرآیند انتشار اطلاعات یک فرآیند دو فاز است. در فاز انبساط سبد، اطلاعات از گره‌های مجموعه سبد (که معمولاً در اجتماعات مختلف واقع شده‌اند) به همسایه‌هایشان انتشار می‌یابد. در فاز انتشار درون اجتماعی، روند انتشار در داخل اجتماعات مستقل از یکدیگر رخ می‌دهد. استراتژی آنها برای انتخاب گره‌های تأثیرگذار بر اساس الگوریتم حریصانهی ابداعی است که باعث شده این الگوریتم کارایی قابل قبولی در زمان اجرا داشته باشد. این الگوریتم نتوانست تضمینی برای اثربخشی ارائه دهد و در برخی از گراف‌ها عملکردی درحد الگوریتم‌های مبتنی‌برمرکزیت داشت. البته بعدها بسیاری از نویسندگان الگوریتم پیشنهادی خود را با الگوریتم CoFIM (به عنوان یک الگوریتم مبنا) مقایسه کرده اند [67]و [68] و [34]. در مطالعه دیگری در سال 2017 حسینی پژوه و همکاران دو الگوریتم جدید در مسئله‌ی بیشینه‌سازی تأثیر تحت مدلهای انتشار آستانه خطی، آستانه ضربی85 و آستانه حداقلی86 را با استفاده از معیار مرکزیت نزدیکی و شناسایی اجتماعات ارائه دادند [69]. دو الگوریتم پیشنهادی C-SPIN87 و C-SGA88 به ترتیب از رویکردهای SPIN89 [49] و SGA90 [70] برای ساخت مجموعه‌ی گره‌های کاندیدا استفاده می‌کنند. الگوریتم LabelRank [71] به‌منظور شناسایی اجتماعات به‌کارگرفته شده است. برای انتخاب گره‌های تأثیرگذار نهایی از معیار مرکزیت نزدیکی استفاده شده است. ارائه الگوریتم برای مدلهای انتشار آستانه ضربی و آستانه حداقلی را می‌توان از نکات برجسته این تحقیق برشمرد. لازم به ذکر است که الگوریتم‌های پیشنهادی این تحقیق در گرافهای بزرگ مقیاس‌پذیر نیستند. به همین دلیل نویسندگان الگوریتم‌های پیشنهادی خود را صرفاً در دیتاست‌های بسیار کوچک (با 34 تا 1867 گره) بررسی کرده‌اند. بزرگی و همکاران در سال 2017 به مطالعه مسئله رقابت را در مسئله‌ی بیشینه‌سازی تأثیر پرداختند و الگوریتم CI291 را معرفی کردند [72]. در مرحله اول اجتماعات توسط الگوریتم SLPA شناسایی می‌شوند. سپس به‌منظور انتخاب گره‌های تأثیرگذار، الگوریتم حریصانهی کمپ [4] روی هر اجتماع تحت مدل انتشار رقابتی DCM92 (که نسخه‌ای از مدل آستانه خطی است) اجرا می‌شود. تأثیرگذارترین گره‌های انتخاب‌شده هر اجتماع به مجموعه‌ی نامزدها اضافه می‌شوند. سرانجام در یک روش تکراری، گره‌هایی با بیشترین سود حاشیه‌ای به‌عنوان تأثیرگذارترین گره‌های شبکه اجتماعی انتخاب خواهند شد. از معایب این الگوریتم می‌توان به سرعت پایین اجرای الگوریتم برای گرافهای بزرگ به‌دلیل استفاده از الگوریتم حریصانهی کمپ اشاره کرد. همچنین این الگوریتم تک‌منظوره بوده و رقابت همزمان را در نظر نگرفته و صرفاً برای رقابت دو بازیگر طراحی شده است نه چند بازیگر. الگوریتم‌های BCRIM93 و ICRIM94 نسخه‌های بهبود یافته الگوریتم حریصانهی کمپ هستند که توسط یی و همکاران در سال 2018 پیشنهاد شده‌اند [73]. ایده اصلی آن تقسیم کل گراف به اجتماعات با استفاده از الگوریتم کلاسیک k-means است. در طی فرآیند شناسایی اجتماعات، اطلاعات گره‌ها و همسایگان آنها با استفاده از روش LINE به منظور استخراج اجتماعات باکیفیت‌تر نگهداری می‌شود. در نهایت برای انتخاب گره‌های تأثیرگذار، الگوریتم حریصانه‌ی‌کمپ روی دو گروه از گره‌ها اجرا می‌شود: گره‌های هر اجتماع و گره‌های مرزی با اجتماعات همسایه. الگوریتم‌های BCRIM و ICRIM به نتایج قابل قبولی ازنظر سرعت و اثربخشی روی گرافهای کوچک و متوسط دست یافتند. اما بدلیل استفاده از الگوریتم حریصانهی کمپ [4] در مواردی که اندازه اجتماعات بدست‌آمده بزرگ باشد (گرافهای بزرگ)، دارای کارایی زمانی قابل قبولی نیستند. در مدل GTaCB95 که توسط جلایر و همکاران در سال 2018 پیشنهاد شده است [74]، از چند معیار مرکزیت برای یافتن تأثیرگذارترین گره‌ها تحت مدل انتشار SIR96 استفاده شده است: مرکزیت درجه، مرکزیت نزدیک، مرکزیت بینابینی و الگوریتم رتبه‌بندی صفحات. در این تحقیق، گراف توسط الگوریتم خوشه‌بندی طیفی به چندین زیرگراف تقسیم می‌شود. سپس الگوریتم TOPSIS97 برای رتبه‌بندی گره‌های هر زیرگراف اجرا می‌شود. در مرحله بعدی، زیرگراف‌ها بر اساس تعداد گره‌های آنها، به ترتیب نزولی مرتب می‌شوند. در نهایت بر اساس ترتیب به‌دست‌آمده اجتماعات، مهم‌ترین گره‌ی هر اجتماع (با بالاترین امتیاز TOPSIS) به مجموعه سبد S اضافه می‌شود تا اینکه k گره انتخاب شوند. اشکال این روش، انتخاب گره‌های تأثیرگذار نهایی از هر زیرگراف برمبنای معیار تعداد گره‌های زیرگراف‌ها است؛ حال اگر یک اجتماع بسیار بزرگ و یک اجتماع کوچکتر وجود داشته باشد، تعداد گره‌های انتخابی از هر دو یکسان خواهد بود. این سیاست منجر به استخراج یک مجموعه سبد با کیفیت پایین خواهد شد. کو و همکاران در سال 2018 یک مدل ترکیبی به نام HybridIM98 ارائه دادند [75] که با ترکیب تکنیک شناسایی اجتماعات و استراتژی مبتنی بر مسیر، یک چارچوب PB-CD99 را به وجود می‌آورد. در مرحله اول، گراف توسط یک روش مبتنی بر مسیر به اجتماعات تقسیم می‌شود. همچنین برای محاسبه گسترش تأثیر هر گره از مجموع وزن مسیرهای منتهی به گره‌های دیگر استفاده می‌کند. در مرحله بعدی برای هر اجتماع یک صف بر اساس ترتیب نزولی سود حاشیه‌ای گره‌ها ایجاد می‌شود. سپس الگوریتم CELF به‌طور مستقیم روی هر صف اعمال می‌شود. در انتها، k گره با بیشترین سود حاشیه‌ای به‌عنوان گره‌های تأثیرگذار نهایی انتخاب می‌شوند. اثربخشی قابل‌قبول این الگوریتم بدین دلیل است که اجتماعات بوسیله‌ی یک روش مبتنی‌برمسیر ساخته می‌شوند. در نتیجه اجتماعات حاصله با فرآیند پخش اطلاعات در مدلهای انتشار بسیار سازگار هستند. ولی متاسفانه از آنجاکه HybridIM، الگوریتم CELF (با زمان اجرای بسیار زیاد) را روی همه‌ی اجتماعات اجرا می‌کند، در مواردی که اندازه اجتماعات بدست‌آمده بزرگ باشد دارای کارایی زمانی قابل قبولی نیست. در سال 2018 لی و همکاران با استفاده از رویکرد شناسایی اجتماعات، الگوریتمی مکان-آگاه100 پیشنهاد کردند [76]. هدف آن انتخاب یک مجموعه سبد اولیه است که میزان گسترش تأثیر را بر روی کاربران هدف که توسط یک پرسش101 مشخص شده‌اند، بیشینه کند. چالش‌های اصلی پیدا کردن کاربران هدف و محاسبه کارآمد اولویت‌ها و ترجیحات آنها است که با یک راه‌حل مبتنی بر R - درخت102 حل شده‌اند. از الگوریتم MIA که نسخه بهبودیافته الگوریتم حریصانهی کمپ است برای محاسبه میزان گسترش تأثیر استفاده شده است. در ابتدا، گراف توسط الگوریتم خوشه‌بندی طیفی به اجتماعات تقسیم می‌شود تا سربار محاسباتی بالا را کاهش دهد. سپس الگوریتم MIA در هر اجتماع به‌طور مستقل اجرا خواهد شد. سربار محاسباتی الگوریتم MIA در گرافهای بزرگ و در نتیجه مقیاس‌پذیری از معظلات این الگوریتم مکان-آگاه است. الگوریتم IMPC103 که یک مدل بیشینه‌سازی تأثیر مبتنی بر چند همسایه بالقوه است توسط شانگ و همکاران در سال 2018 پیشنهاد شد [77]. در رویکرد آنها، فرآیند انتشار تأثیر مانند ایده الگوریتم CoFIM [66] در دو مرحله صورت می‌گیرد: 1. گسترش سبدها بر مبنای چند همسایه بالقوه 2. انتشار تأثیر درون اجتماعات. همچنین، یک تابع هدف برای ارزیابی تأثیر کلی به‌عنوان ترکیبی از تأثیر در طول دو مرحله، تعریف شده است. این الگوریتم همانند الگوریتم CoFIM [66] نتوانست تضمینی برای اثربخشی ارائه دهد و در برخی از گراف‌ها عملکردی درحد الگوریتم‌های مبتنی‌برمرکزیت داشت. Liqing و همکاران در سال 2019 یک الگوریتم سه فاز به نام PHG104 را ابداع کردند [78] که دارای فازهای زیر است: فاز تقسیم، فاز مکاشفه‌ای و فاز حریصانه. در فاز تقسیم، با استفاده از الگوریتم Louvain اجتماعات را شناسایی می‌شوند. سپس بر اساس معیار مرکزیت، گره‌های کلیدی هر اجتماع انتخاب شده و یک مجموعه نامزد تشکیل می‌شود. در فاز مکاشفه‌ای، گره‌های تأثیرگذارتر مجموعه نامزد، به‌وسیله ترکیب وزن میزان تأثیر گره‌ها و تأثیر اجتماعات آنها مشخص می‌شوند. در فاز حریصانه توسط الگوریتم حریصانهی کمپ، k گره با بیشترین سود حاشیه‌ای به‌عنوان تأثیرگذارترین گره‌ها، به مجموعه سبد اضافه می‌شوند. به عنوان یک نقطه قوت، استفاده از الگوریتم Louvain منجر به استخراج جوامع بهینه خواهد شد. نقطه‌ضعف این روش اندازه‌گیری میزان گسترش تأثیر گره بر اساس معیار مرکزیت درجه در گام مکاشفه‌ای و بازتاب اثرات منفی آن به گام‌های بعدی است. در سال 2019 سینگ و همکاران با تمرکز بر ترجیحات کاربران به‌عنوان یک موضوع در مسئله‌ی بیشینه‌سازی تأثیر، چارچوب C2IM105 را پیشنهاد دادند [79]. برای این منظور، مدلهای انتشار آبشاری مستقل و آستانه‌ی خطی را توسعه دادند و به ترتیب مدلهای CIC106 و CLT107 را معرفی کردند. در ابتدا، اجتماعات توسط الگوریتم خوشه‌بندی سلسله مراتبی شناسایی می‌شوند. سپس الگوریتم انتخاب گره‌های تأثیرگذار بر اساس درجه انتشار گره‌ها با در نظر گرفتن ترجیحات کاربران بر روی هر اجتماع اجرا می‌شود. وجود یک مرحله پیش‌پردازش برای حذف کردن گره‌های کم‌اهمیت، در کل باعث افزایش سرعت اجرای الگوریتم شد. در طرف مقابل، نادیده گرفتن تأثیر گره‌ها بر روی گره‌های اجتماعات دیگر بر روی کیفیت مجموعه سبد خروجی اثر منفی گذاشت. هوانگ و همکاران در سال 2019 بیشینه‌سازی تأثیر موضوع-آگاه را در مدل CTIM108 مطالعه کردند [80]. آنها الگوریتم شناسایی اجتماع را به‌جای اجرای مستقل، با مدل انتشار تأثیر ادغام کردند. آنها یک مدل متغیر نهفته جامع ساخته‌اند که موارد زیر را ضبط می‌کند: 1. رابطه موضوع-آیتم 2. علاقه‌مندی‌های موضوعی در سطح اجتماع 3. توزیع عضویت در اجتماع برای هر کاربر. همچنین آنها برای آموزش مدل پیشنهادیشان، الگوریتم نمونه‌برداری گیبس را توسعه داده‌اند. نویسندگان در نتایج گزارش شده خود [80](صفحه 2147 پاراگراف 2) ادعا کردند که الگوریتم پیشنهادیشان، الگوریتم حریصانهی کمپ را از نظر اثربخشی شکست داده است. لازم به ذکر است که الگوریتم حریصانهی کمپ [4] تاکنون دارای بیشترین میزان اثربخشی در میان همه الگوریتم‌های مطرح‌شده در مسئله‌ی بیشینه‌سازی تأثیر است. از این رو این ادعای عجیب نویسندگان باید مورد بررسی بیشتر قرار گیرد. ComBIM109 یک چارچوب مبتنی بر اجتماع برای حل مسئله‌ی بیشینه‌سازی تأثیر بودجه‌بندی شده است که توسط بانرجی و همکاران در سال 2019 پیشنهاد شده است [81]. این چارچوب چهار مرحله اصلی دارد: 1. شناسایی اجتماع 2. توزیع بودجه کل بین اجتماعات 3. انتخاب گره‌های تأثیرگذار مجموعه سبد 4. انتقال بودجه استفاده‌نشده از یک اجتماع به اجتماع دیگر. پیچیدگی زمانی این الگوریتم سینگ و همکاران در سال 2019 یک مدل بیشینه‌سازی تأثیر مبتنی بر اجتماع به نام CoIM110 که بر حل معضل کارایی زمان متمرکز است، پیشنهاد کردند [82]. این مدل گراف اصلی را با استفاده از الگوریتم خوشه‌بندی سلسله مراتبی بر اساس شباهت ژاکارد به اجتماعات تقسیم می‌کند. در مرحله بعدی، گره‌های نهایی مجموعه سبد را بر اساس تأثیر محلی گره‌ها در داخل اجتماع انتخاب می‌کند. ایراد اساسی این مدل این است که تأثیر گره‌ها بر روی گره‌های اجتماعات دیگر را به‌حساب نمی‌آورد و در نتیجه کاهش اثربخشی است. اتیف و همکاران در سال 2020 یک چارچوب فازی مبنا برای حل مسئله‌ی بیشینه‌سازی تأثیر ارائه دادند [83]. در اولین گام، با تقسیم شبکه به اجتماعات بوسیله الگوریتم CNM-Similarity، فضای جستجوی مسئله کاهش می‌یابد. اجتماعات کشف‌شده به‌عنوان ماژول‌هایی برای یافتن تأثیرگذارترین گره‌ها استفاده می‌شوند. در پایان، گره‌های نهایی سبد بر اساس منطق فازی به‌صورت نسبی انتخاب می‌شوند. همانطورکه نویسندگان پیشنهاد دادند، مقیاس‌پذیری این الگوریتم فازی مبنا می‌بایست مورد مطالعه بیشتر قرار بگیرد. لازم به ذکر است که نویسندگان کارایی و اثربخشی الگوریتم پیشنهادیشان را با هیچکدام از الگوریتم‌های برجسته در این زمینه محک نزده اند. الگوریتم CIMA111 که یک مدل مبتنی بر شناسایی اجتماعات در شبکه‌های خصوصیت‌مبنا است توسط هوانگ و همکاران در سال 2020 معرفی شد [67]. این الگوریتم دارای سه مرحله اصلی است: 1. شناسایی اجتماعات 2. شناسایی اجتماعات منتخب به‌منظور کاهش فضاهای جستجو برای انتخاب سبد 3. انتخاب گره‌های تأثیرگذار. آنها همچنین برای بهبود دقت پیش‌بینی، مدلی را برای پیش‌بینی قدرت تأثیر بین گره‌ها در این نوع شبکه‌ها ارائه دادند. علیرغم استخراج گره‌های تاثیرگذار با کیفیت بالا، پیچیدگی زمانی بدترین حالت این الگوریتم بسیار پرهزینه است ژانگ و همکاران در سال 2020 مدلی را بر اساس ساختار اجتماعات و اختلاف توزیع تأثیر در مسئله‌ی بیشینه‌سازی تأثیر بررسی کردند که CBIMA112 نامیده می‌شود [84]. در اولین گام، ساختارهای اجتماعات شناسایی می‌شوند. در مرحله بعدی، یک الگوریتم مکاشفه‌ای برای یافتن گره‌های نامزد از بین گره‌های داخلی و مرز هر اجتماع به کار گرفته می‌شود. سرانجام بر مبنای خاصیت زیرمدولاریته بودن تابع گسترش تأثیر، گره‌های دارای بیشترین بهره حاشیه‌ای به‌عنوان گره‌های تأثیرگذار مجموعه سبد انتخاب می‌شوند. اثربخشی نسبتاً بالای CBIMA (نزدیک به الگوریتم حریصانهی کمپ) به خاطر الگوریتم مکاشفه‌ای پیشنهادی به همراه معیار اختلاف توزیع گسترش تأثیر گره‌ها است. از طرف دیگر، فرآیند یافتن گره‌های نامزد از بین گره‌های داخلی و مرزی هر اجتماع باعث افت کارایی زمانی این مدل پیشنهادی شده است. مدل TI-SC113 یک رویکرد مبتنی بر اجتماع است که توسط بنی و همکاران در سال 2020 ارائه شده است [85]. این مدل با بررسی روابط بین گره‌های اصلی (هسته) و توانایی امتیازدهی گره‌های دیگر، تأثیرگذارترین گره‌ها را پیدا می‌کند. این روش امتیازدهی باعث کاهش همپوشانی گره‌های مجموعه سبدهای متفاوت شده و یک سبد با کیفیت بالا به‌دست می‌آید. همچنین به‌منظور کاهش سربار محاسباتی اضافی، در ابتدا اجتماعات کوچک حذف شدند. هی و همکاران در سال 2020 مسئله بیشینه‌سازی عقیده‌ی مبتنی بر شناسایی اجتماعات را تحت مدل پیشنهادی CAOM114 مطالعه کردند [68]. آنها یک مدل انتشار عقیده وزندار را به‌منظور محاسبه تغییر پویایی ارزش عقیده ابداع کردند. پس از مرحله شناسایی اجتماعات، به‌منظور کاهش سربار محاسباتی اضافی، اجتماعات مهم‌تر شناسایی شده تا گره‌های تأثیرگذار صرفاً از داخل آنها برداشته شوند. در مرحله بعدی با استفاده از معیار یک-هاپ، گره‌های تأثیرگذار نامزد صرفاً از میان گره‌های بالقوه هر اجتماع بااهمیت‌تر انتخاب می‌شوند. سرانجام، گره‌های نهایی مجموعه سبد از میان گره‌های نامزدشده بر اساس معیار دو-هاپ و حذف همپوشانی انتخاب خواهند شد. استفاده از الگوریتم Louvain برای تشخیص اجتماعات و همچنین ابداع مدل انتشار پویا از نقاط قوت این تحقیق است. از طرف دیگر شناسایی اجتماعات بااهمیت‌تر و حذف اجتاماعات کم‌اهمیت، یک چالش بزرگ است که باعث افت کارایی و اثربخشی شده است. الگوریتم CFIN115 که توسط خمامی و همکاران [86] در سال 2020 پیشنهاد شد، شامل دو مرحله اصلی است: 1. انتخاب سبد 2. گسترش محلی اجتماع. پس از مرحله شناسایی اجتماع، به‌منظور کاهش سربار محاسباتی اضافی، اجتماعات مهم‌تر بر اساس اندازه و تراکمشان انتخاب می‌شوند. سپس k گره با بالاترین درجه به‌عنوان گره‌های اولیه از اجتماعات انتخاب می‌شوند. گره‌های نهایی سبد به‌وسیله الگوریتم simplePath [47] تأثیر محلی خودشان را در درون اجتماعات گسترش می‌دهند. حذف اجتماعات کم اهمیت از روند پیداکردن گره‌های تاثیرگذار از دو جنبه حائز اهمیت است. از نظر زمان اجرای الگوریتم، مسلماً باعث افزایش سرعت شده است. ولی ممکن است که گره‌های تاثیرگذارتر در اجتماعاتی باشند که حذف شده‌اند و بدین‌طریق در سبد نهایی قرار نخواهند گرفت. احمد و همکاران در سال 2020 یک رویکرد مبتنی بر اجتماع به نام HWSMCB116 معرفی کردند [87]. این مدل یک روش جمع وزندار پویا را برای رتبه‌بندی گره‌ها در هر اجتماع پیاده‌سازی می‌کند. همچنین، یک روش تصمیم‌گیری چندمعیاره برای در نظر گرفتن همزمان ویژگیهای توپولوژیکی گره‌ها استفاده شده است. بر اساس تحلیل نویسندگان، پیچیدگی زمانی این الگوریتم همانطور که ذکر شد، سیاست الگوریتم‌های CAOM [68] و CIMA [67] بر این است که گره‌های تأثیرگذار نهایی را فقط از اجتماعات مهم انتخاب کنند. پیداکردن معیار و سنجه‌ای مناسب برای تعیین درجه اهمیت اجتماعات دشوار است و باعث افت کارایی می‌شود. وانگ و همکاران در سال 2021 مدل مبتنی بر اجتماعات CNCG117 را برای دور زدن این چالش پیشنهاد دادند [34]. پس از شناسایی اجتماعات همپوشان، به‌منظور محاسبه تأثیر هر گره در داخل اجتماعش، معیار مرکزیت حساس به پوشش گره تعیین شد. سپس گره‌های تأثیرگذار نهایی مستقیماً با ترکیب ساختار اجتماعات شناسایی‌شده با یک استراتژی از پیش طراحی‌شده (بدون شناسایی اجتماعات مهم‌تر) انتخاب شدند. الگوریتم CNCG مشابه الگوریتم CoFIM [66] علیرغم سرعت بالا، نتوانست اثربخشی خود را در همه مجموعه داده‌ها تضمین کند. در جدول 4 الگوریتم‌های بیشینه‌سازی تأثیر مبتنی بر اجتماعات لیست شده است. 4. مقایسه و تحلیل در بخش قبل، الگوریتم‌های برجسته در حوزه مسئله‌ی بیشینه‌سازی تأثیر از لحاظ دو معیار کلیدی «زمان اجرا» و «گسترش تأثیر» مورد بررسی قرار گرفتند. 4.1. معیارهای ارزیابی الگوریتم‌های موجود تقریباً همه‌ی الگوریتم‌های معرفی‌شده در مسئله‌ی بیشینه‌سازی تأثیر ازلحاظ دو معیار «زمان اجرا118» و «گسترش تأثیر119 (اثربخشی)» مورد ارزیابی قرار گرفته‌اند [8]. از معیار «زمان اجرا» برای ارزیابی کارایی زمانی و مقیاس‌پذیری الگوریتم‌ها استفاده می‌شود. به عبارت دیگر زمان اجرای الگوریتم برابر با زمان سپری‌شده برای یافتن k گره تأثیرگذار به‌منظور تشکیل مجموعه سبد S است.
|
