مروری جامع بر مسئله بیشینهسازی تأثیر در شبکههای اجتماعی
محورهای موضوعی : فناوری اطلاعات و ارتباطاتمحسن طاهری نیا 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 . نمادهای پرتکرار
نماد | شرح | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| گراف با مجموعه گره و مجموعه یال | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| به ترتیب برابر تعداد گرهها و یالها در گراف | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| مجموعه سبد گرههای فعال | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| تعداد عناصر مجموعه | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| تعداد شبیهسازی مونتکارلو | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| مدل انتشار | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| تعداد گرههای تحت تأثیرقرارگرفته توسط مجموعه 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. الگوریتمهای برجسته حریصانه و مکاشفهای
|