خلاصة:
یکی از مسائل مهم در زمینۀ شبکههای اجتماعی، مسئلۀ اجتماعیابی است. هدف اجتماعیابی، افرازبندی شبکه به بخشهایی است که ارتباط میان اعضای شبکه در این نواحی متراکم است. بهدلیل ارتباط پررنگ اعضای شبکه در این بخشها، میتوان این اعضا را متعلق به یک اجتماع دانست. تحقیقات بسیاری به توسعۀ الگوریتمهای متعدد در حل این مسائل پرداختهاند. در این پژوهش نیز یک الگوریتم ژنتیک مبتنی بر روش تصمیمگیری چندمعیارۀ تاپسیس ارائه شده است. در الگوریتم پیشنهادی، عملگرهای تقاطع و جهش بر جوابهایی اعمال میشوند که روش تاپسیس بهدست میدهد. برازندگی جوابها بر اساس شاخصهای پودمانگی و چگالی پودمانگی مشخص میشود. در ادامۀ این مقاله، کارایی الگوریتم پیشنهادی نسبت به الگوریتم ژنتیک کلاسیک و یک الگوریتم حریصانه از طریق انجام آزمایشهای عددی سنجیده شد که نتایج نشان از برتری الگوریتم پیشنهادی داشت.
Community detection is one of the most significant issues in the field of social networks. The main purpose of community detection is to partition the network in such a way that the relations between components of the network are dense. Because of the strong relations among network members in these partitions, you can consider them as a community. Many researchers have developed several algorithms to solve such a problem. Therefore, we present a genetic algorithm based on Topsis which is a multi-criteria decision making method (MCDM). The proposed algorithm uses Topsis to rank solutions based on modularity and modularity density which are two of the most well-known criteria in community detection problem. Thereafter, crossover and mutation operators are only applied on solutions ranked by Topsis. The performance of the proposed algorithm has been evaluated through comparing it against classical genetic algorithm and a greedy one. The results showed that the proposed algorithm outperforms the other two methods. Since the application of MCDM approach has not been reported in the related literature, this paper can be considered as a basis for future studies.
ملخص الجهاز:
(2014 با توجه به پيچيدگي مسئلة اجتماع يابي ، هدف از اين مطالعه ، ارائة روش فراابتکاري مبتني بر الگوريتم ژنتيک است که به واسطة آن بتوان اجتماعات متمايزي از رئوس گراف هاي يـک شـبکة پيچيده را در زمان اندک شکل داد.
Parallel Computing در اين پژوهش ، شاخص پودمانگي و نيز شاخص چگالي پودمانگي ١ کـه از جملـه معيارهـاي ارزيابي کيفيت اجتماعات است ، به عنوان تابع هدف مسئله در نظر گرفته شده اسـت و بـه منظـور بيشينه کردن اين دو شاخص ، يک الگوريتم ژنتيـک مبتنـي بـر روش تصـميم گيـري چنـدمعيارٔە تاپسيس ارائه مي شود.
بنابراين با توجه به توضيحاتي که داده شد، در ايـن پـژوهش مسئلة اجتماع يابي با شاخص هاي بيشينه سـازي پودمـانگي و چگـالي پودمـانگي در نظـر گرفتـه مي شود و يک الگوريتم ژنتيک مبتني بر روش تاپسيس معرفي خواهد شد.
استفاده از روش تاپسيس در الگوريتم ژنتيک با هدف بهبود جواب هاي مسئلة اجتماع يابي انجام مي شود.
A Genetic Algorithm for Modularity Density Optimization in Community Detection.
A Genetic Algorithm Based on Modularity Density for Detecting Community Structure in Complex Networks.
Genetic Algorithms for community detection in social networks.
GA-Net: A Genetic Algorithm for Community Detection in Social Networks.
, (2013) Community detection based on modularity and an improved genetic algorithm, Physica A: Statistical Mechanics and its Applications, 392(5), 1215-1231.
A new heuristic algorithm for modularity optimization in complex networks community detection.
A Genetic Algorithm for Detecting Communities in Largescale Complex Networks.