27779

تشخيص جامعه در شبكه‌هاي اجتماعي براساس بهينه‌سازي كلوني زنبورعسل با استفاده از الگوريتم ژنتيك

كارشناسي ارشد

مهندسي كامپيوتر نرم افزار

1399

1401/10/3

دكتر عين‌اله خنجري

دكتر بهروز مينايي

مهندسي كامپيوتر

تاكنون چندين روش براي تشخيص جوامع پيشنهاد شده‌ است كه نشان‌دهنده اهميت بالاي كشف جوامع براي درك شبكه‌هاي اجتماعي و تشخيص الگوهاي مفيد و پنهان در شبكه‌ها مي‌باشند. هدف از اين گونه تحليل ها پيدا كردن دسته‌اي از كاربران با ويژگي‌هاي مشترك است. اصولا شبكه‌هاي اجتماعي به صورت گراف در نظر گرفته مي‌شوند لذا تحليل نيز با استفاده روش‌هاي گراف مي‌باشد، در اين صورت گره‌ها نشان‌دهنده‌ي افراد و يال‌ها نشان‌دهنده‌ي روابط بين آن‌ها است. محققان الگوريتم‌هاي زيادي را براي كشف ساختارهاي اجتماعي شبكه‌ها استخراج كرده‌اند. كشف جوامع يك كار چالش برانگيز است و هيچ الگوريتم واحدي وجود ندارد كه بهترين نتايج را براي همه شبكه‌ها ايجاد كند. بنابراين، با وجود بسياري از راه‌حل‌هاي ظريف كشف جوامع يك حوزه فعال تحقيقاتي باقي مي‌ماند. در اين پايان‌نامه بعد از بررسي روش‌هاي تشخيص جوامع با استفاده از الگوريتم‌هاي تكاملي ژنتيك و كلوني زنبورعسل و ساير روش‌هاي ارائه شده، يك روش تشخيص جوامع تركيبي كلوني زنبور عسل و ژنتيك ارائه شده است. در اين روش از تكنيك موازي جهت تسريع بهينه‌سازي استفاده شده‌ است و همچنين سعي شده است ضعف‌هاي ساير روش‌ها را پوشش دهد. يكي از ضعف‌ها تابع برازندگي است. در اكثر رويكردها از پيمانگي استفاده شده است كه اين روش از محدوديت وضوح رنج مي‌برد و نمي‌تواند جوامعي كه اندازه‌ي آن كوچك است را تشخيص دهد و آن را در تركيب با جوامع بزرگ در نظر مي‌گيرد. بنابراين در اين روش همچون روش‌هاي اخير از تابع برازندگي پيمانگي متعادل استفاده شده‌است. روش پيشنهادي با استفاده از مزاياي الگوريتم ژنتيك در ايجاد جمعيت اوليه كارآمد و استفاده از عملگرها در جست‌وجوي منابع غذايي توسط زنبورها، شامل سرعت بالا در تشخيص جوامع است. آزمايش‌ها بر روي شبكه‌هاي معروف دنياي واقعي، از جمله كاراته، فوتبال آمريكايي، دلفين‌ها و كتاب‌هاي سياسي نشان داده‌اند كه الگوريتم پيشنهادي ( BSOGA) داراي دقت بالاتر و كارايي قابل مقايسه با روش‌هاي مطرح در تشخيص جامعه است.

1401/11/01

Community detection in social networks based on bee swarm optimization using genetic algorithm

12/24/2023 12:00:00 AM

So far, several methods for detecting communities have been proposed, which show the high importance of detecting communities for understanding social networks and identifying useful and hidden patterns in networks. The purpose of such analyzes is to find a group of users with common characteristics. Basically, social networks are considered in the form of graphs, so the analysis is also done using graph methods, in this case, the nodes represent people and the strands represent the relationships between them. Researchers have derived many algorithms to discover the social structures of networks. Community discovery is a challenging task and there is no single algorithm that produces the best results for all networks. Therefore, despite many elegant solutions, the discovery of communities remains an active area of research. In this thesis, after examining the methods of detecting communities using evolutionary genetic and bee colony algorithms and other presented methods, a method of detecting combined bee and genetic communities is presented. In this method, a parallel technique has been used to speed up the optimization and it has also tried to cover the weaknesses of other methods. One of the weaknesses is the fitness function. In most of the approaches, the modularity has been used, but this method suffers from the limitation of clarity and cannot recognize the communities whose size is small, and considers it in combination with large communities. Therefore, in this method, the fitness function of the balanced has been used. The proposed method, using the advantages of the genetic algorithm in creating an efficient primary population and using operators in the search for food sources by bees. Experiments on popular real-world networks, including karate, American football, dolphins, and political books, have shown that our proposed algorithm (BSOGA) has higher accuracy and performance comparable to existing community detection methods.

تشخيص جامعه , الگوريتم ژنتيك , كلوني زنبورعسل , نمايش مجاورتي مبتني بر مكان , پيمانگي

community detection , Genetic algorithm , bee colony , locus-based proximity representation , Modularity

fatemeh akbari

eynollah khanjari