الگوریتمی تقریبی برای حل مساله‌ی خوشه‌بندی همبستگی با استفاده از عملیات ماتریسی

شکیبا, علی

doi:10.22072/wala.2023.1988384.1411

الگوریتمی تقریبی برای حل مساله‌ی خوشه‌بندی همبستگی با استفاده از عملیات ماتریسی

Document Type : Research Paper

Author

علی شکیبا

گروه علوم کامپیوتر،دانشگاه ولی عصر رفسنجان، رفسنجان، ایران.

https://doi.org/10.22072/wala.2023.1988384.1411

Abstract

مساله‌ی خوشه‌بندی همبستگی، یکی از شهودی‌ترین مدل‌های افراز یک گراف مشابهت به اجتماعی از خوشه‌ها است. متاسفانه این مساله در رده‌ی مسائل NP-سخت قرار دارد. به همین دلیل، ارائه‌ی یک الگوریتم کارآ از زمان چندجمله‌ای که یک افراز دقیق و بهینه را برای گراف‌های دلخواه ایجاد نماید، بعید به‌نظر می‌رسد. در این مقاله، ابتدا یک فرمول‌بندی جدید از این مساله با استفاده از رویکردی حریصانه به منظور محاسبه‌ی پاسخی تقریبی در زمان چندجمله‌ای ارائه خواهیم داد. سپس، با استفاده از عملیات پایه‌ی ماتریسی، فرمول‌بندی معادل از الگوریتم ارائه شده را ارائه خواهیم کرد که در هر زبان برنامه‌نویسی مبتنی بر عملیات ماتریسی، به سادگی قابل پیاده‌سازی است. علاوه بر این، فرمول‌بندی ارائه شده امکان استفاده از توازی موجود در عملیات ماتریسی پایه را فراهم می‌نماید.

Keywords

Correlation clustering

Linear algebra

Approximation algorithm