یک الگوریتم تقریب برای بیشینه سازی ماژولاریتی به وسیله تخمین حوزه نفوذ

با رشد شبکه های اجتماعی، این شبکه ها هر روز بزرگ و بزرگ تر می شوند و تحلیل آنها به مراتب پیچید ه تر می شود. برای سادگی تحلیل شبکه های اجتماعی می توان آنها را به مجموعه ای از اجتماعات مختلف تقسیم کرد. این کار، تحلیلگران و کارشناسان را در درک رفتار و عملکرد اینگونه شبکه ها یاری می دهد. روش های مختلفی برای تشخیص اجتماعات در شبکه ها ارائه شده اند. بیشینه سازی ماژولاریتی، یکی از روش های مدرن و مناسب برای تشخیص اجتماع است. بیشینه سازی ماژولاریتی یک مسئله NP-hard است؛ به این معنی که هیچ الگوریتم چندجمله ای برای حل این مسئله وجود ندارد؛ مگر اینکه P=NP باشد. یک دسته از روش ها برای حل اینگونه مسائل، الگوریتم های تقریب است. شناسایی گرههای پرنفوذ، کاربردهای زیادی در شبکه های اجتماعی دارد. این روش می تواند برای تشخیص اجتماع نیز به کار رود. در این مقاله، الگوریتم های تقریبی برای بیشینه سازی ماژولاریتی براساس شناسایی گرههای پرنفوذ و دامنه نفوذشان پیشنهاد می شود. همچنین، از مفاهیم شبکه های مستقل از مقیاس برای اثبات نرخ تقریب استفاده می شود. آزمایش ها روی شبکه های واقعی نشان می دهند الگوریتم پیشنهادی قابل رقابت با روش های مدرن تشخیص اجتماع است.

کلیدواژه ها:

الگوریتم تقریب ، تشخیص اجتماع ، چارچوب نمونه گیری نفوذ معکوس (RIS) ، شبکه های اجتماعی ، گرههای پرنفوذ ، ماژولاریتی