20327

۲۰۳۲۷

رهيافت‌هايي مبتني بر جست‌وجوي محلي در الگوريتم‌هاي فرا ابتكاري براي تشخيص جوامع در شبكه¬هاي پيچيده

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

نرم‌افزار

۹۵-۹۷

۱۳۹۷/۰۸/۲۹

دكتر سعيد پارسا

كامپيوتر

تجزيه و تحليل ساختاري و عملكردي شبكه‌ها با استفاده از شناسايي جوامع آن‌ها يك مسئله مهم در بسياري از حوزه‌هاي تحقيقاتي از جمله علوم اجتماعي، علوم كامپيوتر، بيولوژي و فيزيك است. مسئله‌ي تشخيص جوامع يك مسئله‌ي NP-hard است. بنابراين يكي از راه‌هاي حل آن استفاده از روش‌هاي فرا ابتكاري است و در اين راستا روش‌هاي گوناگوني توسط محققان مختلف ارائه شده است. چالش اصلي اين روش‌ها زمان اجراي زياد و دقت كم آن‌هاست. به همين دليل، در اين تحقيق به ارائه دو روش نوين فرا ابتكاري براي تشخيص جوامع با استفاده از الگوريتم ژنتيك به نام‌هاي EGACD و MOGGA مي‌پردازيم. در اين الگوريتم‌ها از يك عملگر نوين جستجوي محلي، كه منجر به افزايش نرخ همگرايي و افزايش دقت مي‌شود، استفاده شده است. براي محدود كردن فضاي جستجو، از يك نمايش كه از اطلاعات ساختاري شبكه در فرآيند مقداردهي و بازتوليد جمعيت استفاده مي‌كند بهره برده‌ايم. علاوه بر اين، اين الگوريتم‌ها نيازي به دانستن تعداد جوامع شبكه در ابتداي كار ندارند. بسياري از الگوريتم‌هاي موجود تشخيص جوامع گراف محور هستند و در صورتي كه ساختار گراف پيچيده شود قادر به تشخيص دقيق جوامع نيستند. به همين دليل، در اين تحقيق همچنين به ارائه يك روش متفاوت تشخيص جوامع بر اساس اين فرضيه كه هر جامعه در برگيرنده‌ي يك زيرفضاي جدا در فضاي اقليدسي است مي‌پردازيم. به صورتي كه هر گره مي‌تواند به صورت تركيب خطي از گره‌هاي ديگري كه در همان زيرفضا هستند تعريف شود. اخيرا روشي تحت عنوان خوشه‌بندي قله‌هاي چگال براي خوشه‌بندي موثر و كاراي داده‌ها منتشر شده است. ما با الهام از اين روش، خوشه‌بندي را بر روي شبكه‌هايي كه به فضاي داده نگاشت شده‌اند اعمال كرده و آن را تحت عنوان روش پيشنهادي سوم ارائه مي‌دهيم. نتايج آزمايش‌هاي ما بر روي مجموعه داده‌هاي واقعي و مصنوعي نشان‌دهنده‌ي كارايي بيشتر الگوريتم‌هاي پيشنهادي از نظر دقت بيشتر در مقابسه با روش‌هاي موجود است. واژه‌هاي كليدي: تشخيص جوامع، جستجوي محلي، نگاشت زيرفضايي، خوشه‌بندي قله‌هاي چگال، خوشه‌بندي

1398/01/23

Meta-heuristic and sparse linear coding approaches for identifying communities in complex networks

4/12/2019 12:00:00 AM

Identifing hidden communities of complex networks is an important task across some real-world applications such as: social science, power systems, social networks, biology, physics, and medicine. Although, many community detection methods have been proposed in the literature, but most of them suffer from several shortcomings such as: instability, failure to identify small communities, requiring a prior knowledge about the community structure and low accuracy in identifying communities in networks with unclear communities structure. To tackle these issues, in this research, three novel methods are proposed. More recently, evolutionary-based optimization methods are conventionally applied to cope with some of the above mentioned issues. The primary challenge regarding the application of evolutionary-based approaches is their relatively low convergence speed and accuracy. In this respect, this thesis proposes two genetic-based algorithms known as EGACD and MOGGA, for community detection in complex networks. These algorithms are supplied with a novel local search strategy to speed up the convergence and improve the accuracy. To reduce the search space, a specific representation is used to incorporate domain-specific knowledge with the solutions through initialization and reproduction operators. In addition, it does not need to know the number of communities at the beginning of the search process. Most existing community detection methods are topological-based methods that are directly applied to the adjacency matrix and and they cannot accurately identify community boundaries. To overcome this issue, subspace-based community detection methods first map the graph into a low dimensional space, and then apply spectral clustering method to identify hidden communities. Subspace-based methods are lay on the fact that each network community spans a different subspace in the geodesic space. In this type of representation, each node can only be efficiently represented as a linear combination of nodes spanning the same subspace. Existing subspace-based community detection methods employ the spectral clustering to identify final communities that includes several adjustable parameters that have high sensitivity to their initial values. To tackle this issue the third proposed method a density-based clustering method tis used o reveal final communities. DPC The third proposed method consists of three steps: subspace mapping, identifying community cores, and label propagation. In the first step, the adjacency matrix is converted to vectors in the similarity space, and the graph is mapped to multidimensional space. In the second step, a specific node ranking strategy is used to calculate the importance of nodes, and top-ranked nodes are considered as community cores. In the third step, a label propagation algorithm is used to form the final communities around identified cores.Our experiments with the real-world and atrificial network datasets demonstrate the relatively high capacity of our proposed algorithms in detecting communities with relatively less time and more precision. Keywords: community detection, local search, subspace mapping, density peaks clustering, clustering.