روجیار پیرمحمدیانی

مسئله تشخیص جوامع در شبکه‌ها یکی از مسائل مهم علم شبکه بوده و مطالعات گسترده‌ای در این خصوص صورت گرفته است. مفهوم جامعه را می‌توان در شبکه‌های بسیاری از جمله شبکه‌های بیولوژیکی، علوم کامپیوتر،مهندسی، اقتصاد ،سیاست و .... مشاهده کرد. خوشه‌بندی، اشیاء را با توجه به شباهت بین اشیاء به چندین گروه تقسیم می‌کند. با توجه به استراتژی‌های مختلف، روش‌های مختلفی پیشنهاد شده‌است.در میان همه الگوریتم‌های تشخیص جامعه ، خوشه‌بندی طیفی به عنوان یک رقیب قدرتمند به نسبت سایر روش‌های خوشه-بندی به دلیل اجرای آسان و دقت بالا برای اکثر شبکه‌های پیچیده محسوب می‌شود. این روش براساس ویژگی-های طیفی گراف است و بر روی بردارهای ویژه ماتریس لاپلاسین تمرکز دارد. مزیت خوشه‌بندی طیفی این است که محدودیت خاصی در مورد شکل خوشه‌ها ندارد و به دلیل عملکرد خوبی که به نسبت الگوریتم‌های خوشه‌بندی پایه مانندk-means درکشف خوشه‌های غیر محدب و با ویژگی‌های مختلف دارد، به طور گسترده‌ای در حوزه‌های مختلف استفاده می‌شود. با این حال از معایب این روش می‌توان به هزینه‌های محاسباتی بالا، نتایج خوشه‌بندی ناپایدار وعدم مقاومت در مقابل نویز اشاره کرد. در این پژوهش جهت استفاده از مزایای خوشه‌بندی طیفی در مجموعه داده‌های بزرگ از روش‌ خوشه‌بندی طیفی تقریبی، که در آن خوشه‌بندی طیفی را بر روی مجموعه کاهش‌یافته از نقاط ( نمایندگان داده‌ها) انتخاب‌شده با نمونه‌برداری یا کمی سازی اعمال می‌کنیم و در نهایت نتایج به کل داده ها تعمیم داده می شود. مراحل اصلی خوشه‌بندی طیفی شامل محاسبه ماتریس شباهت، به دست آوردن نمایش‌های جدید از مجموعه داده‌ها با روش تجزیه ویژه وتقسیم پارامترهای جدید با الگوریتم خوشه‌بندی k-means برای به دست آوردن برچسب‌های خوشه می‌باشد. الگوریتم‌های خوشه‌بندی طیفی بر تحلیل ماتریس شباهت تکیه دارند، از این رو، تعریف یک ماتریس مناسب تاثیر زیادی بر بهبود عملکرد این نوع از خوشه‌بندی دارد، زیرا رابطه بین اجسام را حفظ می‌کند. ماتریس شباهت روش پایه‌ای خوشه بندی طیفی مبتنی بر فاصله اقلیدسی می‌باشد و این نوع شباهت نمی‌تواند توزیع داده‌ها را به خوبی نشان دهد و در نتیجه منجر به عملکرد ضعیف خوشه‌بندی طیفی می‌شود. همچنین این ماتریس تنها برا ساس خصیصه‌های توپولوژیکی ساخته شده است حال آنکه در شبکه‌های دارای ویژگی هر دو ساختار توپولوژیکی و ویژگی گره، ویژگیهایی مهم در تشخیص جامعه هستند و عملکرد خوشه‌بندی طیفی تا حد زیادی به خوبی ماتریس شباهت بستگی دارد. از این رو در این مطالعه نسخه جدیدی به نام خوشه‌بندی طیفی درشبکه های دارای ویژگی به کار می‌رود که جوامع شناسایی‌شده دارای پیوستگی ساختاری و همگنی ویژگی بوده و همچنین بر اساس یک نوع فاصله حساس به چگالی به جای فاصله اقلیدسی می‌باشد. در فاصله جدید حساس به چگالی می‌توانیم فاصله را در مناطق با چگالی متفاوت تنظیم کنیم و سپس با اندازه‌گیری فاصله حساس به چگالی می‌توانیم شباهت جدیدی را تعریف کنیم. برای اجتناب از مقداردهی تصادفی مراکز، از گراف تصمیم استفاده می‌شود تا به مراکز و تعداد خوشه ها دست پیدا کنیم. برای افزایش کارایی تعداد خوشه‌ها از طریق گراف تصمیم تعیین شده است. واژه‌های کلیدی: تشخیص‌جامعه، خوشه‌بندی طیفی، ماتریس شباهت، فاصله حساس به چگالی، کاهش نقاط داده، خوشه‌بندی طیفی تقریبی، شبکه‌های دارای مشخصه، ساختار توپولوژیکی