الگوریتم گیروان-نیومن
الگوریتم گیروان-نیومن (به نام میشل گیروان و مارک نیومن) یک روش سلسله مراتبی تقسیم‌کننده است که برای شناسایی انجمن در سیستم‌های پیچیده استفاده می‌شود.[۱] این الگوریتم با حذف کردن مرحله به مرحله پیوندها، شبکه اصلی را به تعدادی شبکه مجزا تقسیم می‌کند که همان انجمن‌ها هستند.[۲]
میانگی یال و ساختار جامعه[ویرایش]
در الگوریتم گیروان-نیومن معمولا از «میانگی یال» به عنوان معیار مرکزیت استفاده می‌شود. میانگی یک یال متناسب است با تعداد کوتاه‌ترین مسیرها بین تمام جفت گره‌های شبکه که از آن یال می‌گذرند. اگر بیش از یک کوتاه‌ترین مسیر بین یک جفت گره وجود داشته باشد، به هر مسیر وزن مساوی داده می‌شود به طوری که وزن کل مسیرها برابر با واحد شود. در شبکه‌هایی که انجمن‌بندی دارند، داخل هر انجمن تعداد زیادی یال وجود دارد و تعداد پیوندهای بین انجمن‌ها به مراتب کمتر است. در نتیجه تمام کوتاه‌ترین مسیرها بین اعضای انجمن‌های متفاوت از این یال‌ها می‌گذرند و میانگی زیادی به این یال‌ها می‌دهند. با حذف این یال‌ها، گروه‌ها از یکدیگر جدا می شوند و بنابراین ساختار جامعه در شبکه آشکار می شود.
جزئیات الگوریتم[ویرایش]
مراحل این الگوریتم به شکل زیر خلاصه شده‌اند:
- ابتدا میانگی تمام یال‌های موجود در شبکه را محاسبه می‌کنیم.
- یال با بیش‌ترین میانگی را حذف می‌کنیم. (اگر چند یال با چنین ویژگی موجود بودند، یکی را به دلخواه حذف می‌کنیم.)
- میانگی یال‌هایی را که تحت تأثیر قرار گرفته‌اند را دوباره محاسبه می‌کنیم.
- مراحل ۲ و ۳ را تا زمانی که هیچ یالی باقی نماند تکرار می‌کنیم.
این که تنها میانگی یال‌هایی مجدداً محاسبه می‌شود که تحت تأثیر حذف قرار گرفته‌اند، ممکن است زمان اجرای شبیه‌سازی را کاهش دهد. با این حال، میانگی باید در هر مرحله دوباره محاسبه شود، در غیر این صورت خطا رخ می‌دهد. چرا که حذف هر یال میانگی تعداد زیادی از یال‌های دیگر تا تغییر می‌دهد. مثلا ممکن است دو انجمن با بیش از یک پیوند به هم متصل باشند که یکی از آن‌ها بیش‌ترین میانگی را داشته باشد. بعد از حذف آن پیوند، میانگی باقی پیوندها افزایش می‌یابد.
نتیجه نهایی یک دندروگرام است. در طول اجرای الگوریتم، دندروگرام از بالا به پایین تولید می شود (یعنی شبکه با حذف پی‌درپی پیوندها به جوامع مختلف تقسیم می‌شود). برگ‌های دندروگرام، گره‌های منفرد هستند. می‌توان برای انتخاب کردن بهترین انجمن‌بندی، پودمانگی را در هر مرحله محاسبه کنیم و تقسیم‌بندی با بیش‌ترین پودمانگی را به عنوان انجمن‌بندی نهایی برگزینیم.
همچنین ببینید[ویرایش]
- نزدیکی
- خوشه بندی سلسله مراتبی
- پودمانگی
مراجع[ویرایش]
- ↑ Girvan M. and Newman M. E. J., Community structure in social and biological networks, Proc. Natl. Acad. Sci. USA 99, 7821–7826 (2002)
- ↑ Albert-László Barabási. "Divisive Procedures: the Girvan-Newman Algorithm" (به انگلیسی).