17669

17669

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

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

نرم افزار

بهمن ماه 1395

دكتر حسن نادري

كامپيوتر

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

1396/04/26

7/11/2018 12:00:00 AM

Community detection is the basic topics in network analysis. Local community detection or seed expansion is designed to run on large scale network. These methods can not accurately estimate the number, distance and location of communities because there is no local knowledge about network structure. These approaches have a global pre- and post-processing that conflict with local processing. In this research, we propose sliding window algorithm to identify communities in local areas. This algorithm moves towards a community with high quality, based on crawling movement. Quality is determined based on conductance measure. The sliding window algorithm based on local knowledge that is gained during run, estimate number of communities and set the distance of community Based on community’s center. Our algorithm is less complex than previous methods because the computation is purely local. The proposed algorithm extracts overlapping communities, also with change the structure of algorithm can detect disjoint communities. We eva​luate the sliding window method against the new community detection methods on large real networks. There are two types of eva​luation, structure measure and identify ground-truth communities. Experiments show that the proposed method, in both eva​luations have a better performance relative to other algorithms. Keywords: community detection, network, local approach, Sliding window, conductance, ground-truth community