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

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