|
|
ارائهی یک رویکرد جدید برای حل مسئلهی اجتماعیابی شبکههای اجتماعی با توسعهی الگوریتمهای NSGAII و NRGAnrga
|
|
|
|
|
نویسنده
|
برادران وحید ,حسینیان امیرحسین ,درخشانی رضا ,نیک ضمیر محمد
|
منبع
|
مهندسي صنايع و مديريت شريف - 1397 - دوره : 34-1 - شماره : 1/2 - صفحه:101 -115
|
|
|
چکیده
|
مسئلهی اجتماعیابی، از جمله مسائل تحلیل شبکههای اجتماعی، عبارت است از افرازبندی شبکه به بخشهایی که ارتباط میان اعضای شبکه در هر بخش متراکم است. در این مقاله، افرازبندی شبکه در قالب مسئلهی بهینهسازی چندهدفه با توابع هدف، شاخص پودمانگی و امتیاز اجتماعات مدلسازی شده است. بهمنظور حل مدل بهینهسازی چندهدفه، دو الگوریتم تکاملی nsgaii و nrga بهبود یافته است. الگوریتمهای پیشنهادی برای ایجاد جوابهای اولیه از یک روش حریصانه استفاده میکنند. همچنین، عملگرهای تقاطع و جهشی جدید برای الگوریتمهای پیشنهادی طراحی شده است. عملگر تقاطع ارائه شده، مبتنی بر مقدار نزدیکی گرههاست. عملگر جهش نیز مبتنی بر روش تاپسیس عمل میکند. کارایی الگوریتمهای پیشنهادی نسبت به سه الگوریتم کلاسیک nsgaii، nrga و moganet از طریق انجام آزمایشهای عددی بر روی 6 شبکهی دنیای واقعی مورد سنجش قرار گرفته است. نتایج، نشان از بهبود قابل توجهی در جوابهای مسئلهی اجتماعیابی توسط الگوریتمهای پیشنهادی داشت.
|
کلیدواژه
|
اجتماعیابی، بهینهسازی چندهدفه، شبکههای پیچیده، روش تاپسیس
|
آدرس
|
دانشگاه آزاد اسلامی واحد تهران شمال, گروه مهندسی صنایع, ایران, دانشگاه آزاد اسلامی واحد تهران شمال, گروه مهندسی صنایع, ایران, دانشگاه آزاد اسلامی واحد تهران شمال, گروه مهندسی صنایع, ایران, دانشگاه آزاد اسلامی واحد تهران شمال, گروه مهندسی صنایع, ایران
|
پست الکترونیکی
|
m_nikzamir@iau-tnb.ac.ir
|
|
|
|
|
|
|
|
|
A NEW APPROACH TO DEVELOPMENT OF NSGAII AND NRGA FOR SOLVING COMMUNITY DETECTION PROBLEM
|
|
|
Authors
|
Hoseinian A.H. ,Nikzamir M. ,Derakhshani R. ,Baradaran V.
|
Abstract
|
Detecting community structures is applicable in a wide range of scientific fields such as biological and social sciences. Community detection is one of the most renowned problems in the field of social networks mining. Thus, many methods have been introduced and developed in order to meet diverse needs of community detection. The aim of community detection is to partition the network in such a way that relations between components of network are dense. Since the relations between the members of partitions are strong, it is possible to consider them as a community or a cluster. In this paper, we have considered community detection as a multiobjective problem. The objective functions are modularity and community scores, which are two of the most wellknown objectives in the literature. In order to optimize these objective functions, two algorithms, which are the enhanced versions of NSGAII and NRGA, have been proposed. These methods use a greedy algorithm to obtain initial population. Moreover, new crossover and mutation operators have been designed. The crossover operator is based on closeness of nodes. The mutation operator is based on TOPSIS method. The proposed crossover and mutation operators always generate feasible solutions. Furthermore, the closeness index helps to form distinct and high quality communities. We have compared the performance of the proposed methods with those of classical NSGAII, NRGA, and a wellknown method called MOGANet by conducting several numerical experiments in six realworld networks. The experiments split into two parts. In the first part, we have compared the solutions of these five algorithms regarding the values of objective functions. The second part is dedicated to the comparisons made based on various multiobjective metrics. We have considered spacing, generational distance, inverted generational distance, set coverage, normalized mutual information, computation time, and the number of nondominated solutions obtained by each method. In order to ensure that the solutions obtained by the proposed algorithms are significantly better than the ones provided by the other three methods, we have conducted several twosample ttests. The results showed significant improvement, and the proposed algorithms outperformed the other three methods regarding various criteria.
|
Keywords
|
|
|
|
|
|
|
|
|
|
|
|