24180

MAT2 702

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

رياضي كاربردي- علوم داده

رياضي و آمار

1403/10/18

106 ص.

فرزاد پرورش , مجيد اسدي

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

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

Community detection , stochastic block model , clusterig , random graph , recovery threshold

A Study On The Community Detection And Stochastic Block Models

رياضي كاربردي و علوم كامپيوتر

With the advancement of technology, especially in the digital world, we are faced with an enormous volume of data and information that requires new tools in data science and network theory for analysis. One important issue in analyzing such data is how to classify individuals into different communities with similar features. In the relevant scientific literature, this problem is commonly referred to as community detection. Community detection in complex networks, especially in the stochastic block model, is a significant challenge. New phase transition phenomena have been discovered for the stochastic block model in the case of two symmetric and nonoverlapping communities, which has posed new algorithmic challenges. This research investigates whether this phenomenon extends to multiple communities without imposing symmetry constraints. In this study, partial and exact recovery of communities in the general stochastic block model in both constant and logarithmic degree regimes is examined, and the results are generally applied to analyze overlapping communities. The primary goal is to provide an algorithm that, by using new divergence criteria such as Hellinger and Chernoff divergences, enhances the exact recovery of communities in this model. This research specifically includes the following: (1) determining the exact recovery threshold for communities in the general stochastic block model using a new divergence function, (2) developing an efficient algorithm with quasi-linear complexity for exact community recovery that performs optimally up to the threshold, and (3) proposing an algorithm capable of identifying communities with high accuracy in the constant-degree regime, enabling near-perfect accuracy with an appropriate signal-to-noise ratio.

5