الگوریتم راواس

این الگوریتم یکی از روش‌های خوشه‌بندی سلسله‌مراتبی شبکه است. در این روش ابتدا هر راس شبکه یک انجمن مجزا در نظر گرفته می‌شود و در ادامه در هر مرحله راس‌های دارای مشابهت بیشتر با یکدیگر یک انجمن تشکیل خواهند داد.

ماتریس مشابهت

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

برای تعریف مشابهت بین رئوس، ماتریسی تعریف می‌شود به طوری که درایه $x_{ij}$ این ماتریس، که نشان دهنده مشابهت میان دو راس $i$ و $j$ است، اینگونه تعریف می‌شود:

$x_{ij}={\frac {J(i,j)}{min(k_{i},k_{j})+1-\Theta (A_{ij})}}$

که $J(i,j)$ تعداد همسایه‌های مشترک دو راس است و در صورتی که بین دو راس پیوند مستقیم وجود داشته باشد این عدد را با ۱ جمع می‌کنیم. $\Theta (x)$ نیز یک تابع پله‌ای است که در صورتی که $x\leqslant 0$ باشد برابر صفر و در صورتی که $x>0$ باشد برابر یک است. قطر اصلی این ماتریس را نیز صفر قرار می‌دهیم. همانطور که مشخص است ماتریس مشابهت یک ماتریس متقارن است که قطر اصلی آن صفر است.

زمانی که راس‌ها با یکدیگر ادغام شده و یک انجمن تشکیل دهند، مشابهت بین دو انجمن به روش‌ها مختلف می‌تواند تعریف شود. مثلا در بعضی موارد کمترین $x_{ij}$ در نظر گرفته می‌شود به طوری که $i$ عضو انجمن اول و $j$ عضو انجمن دوم باشد، و یا می‌توان به طریق مشابه بیشترین $x_{ij}$ را در نظر گرفت. در الگوریتم راواس میانگین مشابهت انجمن‌ها در نظر گرفته می‌شود. به این معنی که میانگین $x_{ij}$ روی تمامی $i$ و $j$های متعلق به انجمن‌‌های متمایز را به عنوان مشابهت دو انجمن در نظر می‌گیریم.

الگوریتم

گام اول: هر راس را یک انجمن متمایز در نظر می‌گیریم و ماتریس مشابهت را محاسبه می‌کنیم.

گام دوم: دو راس یا دو انجمن با بیشترین مشابهت را پیدا کرده و آن دو را با هم ادغام می‌کنیم.

گام سوم: مشابهت میان انجمن جدید و تمامی انجمن‌ها را محاسبه می‌کنیم.

گام چهارم: گام دوم و سوم را آنقدر تکرار می‌کنیم تا تمامی راس‌ها عضو یک انجمن شوند.

This article "الگوریتم راواس" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:الگوریتم راواس. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

---

 Facebook Page

 Follow us on Twitter !

Read or create/edit this page in another language

• الگوریتم راواس in English