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

با رشد شبکه‌های اجتماعی، این شبکه‌ها هر روز بزرگ و بزرگ‌تر می‌شوند و تحلیل آنها به‌مراتب پیچید‌ه‌تر می‌شود. برای سادگی تحلیل شبکه‌های اجتماعی می‌توان آنها را به مجموعه‌ای از اجتماعات مختلف تقسیم کرد. این کار، تحلیلگران و کارشناسان را در درک رفتار و عملکرد اینگونه شبکه‌ها یاری می‌دهد. روش‌های مختلفی برای تشخیص اجتماعات در شبکه‌ها ارائه شده‌اند. بیشینه‌سازی ماژولاریتی، یکی از روش‌های مدرن و مناسب برای تشخیص اجتماع است. بیشینه‌سازی ماژولاریتی یک مسئله nphard است؛ به این معنی که هیچ الگوریتم چندجمله‌ای برای حل این مسئله وجود ندارد؛ مگر اینکه p=np باشد. یک دسته از روش‌ها برای حل اینگونه مسائل، الگوریتم‌های تقریب است. شناسایی گرههای پرنفوذ، کاربردهای زیادی در شبکه‌های اجتماعی دارد. این روش می‌تواند برای تشخیص اجتماع نیز به‌کار رود. در این مقاله، الگوریتم‌های تقریبی برای بیشینه‌سازی ماژولاریتی براساس شناسایی گرههای پرنفوذ و دامنۀ نفوذشان پیشنهاد می‌شود. همچنین، از مفاهیم شبکه‌های مستقل از مقیاس برای اثبات نرخ تقریب استفاده می‌شود. آزمایش‌ها روی شبکه‌های واقعی نشان می‌دهند الگوریتم پیشنهادی قابل رقابت با روش‌های مدرن تشخیص اجتماع است.

An approximate algorithm for maximizing modularity by estimating the domain of influence

As social networks grow, they become more and more complex and analyzing them becomes complicated. One way to reduce this complexity is to divide the network into subnets, which are also called communities. Dividing social networks into desirable communities can help the analysts and experts to understand the behavior and function of the networks. Community detection in networks is a challenging topic in network science and various methods have been proposed for that. Modularity maximization is one of the stateoftheart methods suggested for community detection. Modularity maximization is an NPhard problem meaning that no polynomialtime algorithm exists that could solve the problem optimally unless P=NP. One group of approaches that could solve such problems is the approximate algorithms. Identifying the influential nodes has many important applications in social networks. This technique could also be used in community detection. To maximize the modularity, in this paper, we propose approximate algorithms based on identifying the influential nodes and their influence domain. We used the concept of scalefree networks to prove the approximate factor. Experiments on realworld networks show that the proposed algorithm can compete with the stateoftheart methods of community detection algorithms.