تشخیص جوامع به روش انتشار برچسب گره های مرزی با استفاده از ترکیب معیارهای محلی

یکی از مهمترین ویژگی های قابل مشاهده در شبکه های پیچیده، وجود ساختارهای انجمنی یا جوامع است. از طرف دیگر به دلیل افزایش روزافزون اندازه شبکه های پیچیده مثل شبکه های اجتماعی و یا بیولوژیکی، نیازمند طراحی الگوریتم های هرچه سریع تر و با دقت قابل قبول جهت شناسایی ساختارهای هستیم. به همین دلیل الگوریتم های محلی و نیمه محلی مثل G-CN و LPA امروزه از محبوبیت بالایی برخودار هستند. ولی هر دو الگوریتم فوق از لحاظ دقت تشخیص دارای مشکلاتی هستند. در این مقاله مشکلات مربوط به روش G-CN در دو فاز مرتفع شده است. در فاز اول، مرکزیت درجه 1 گره ها نیز برای بروزرسانی برچسب استفاده شد و درنتیجه، کیفیت تشخیص جوامع بهبود یافت. همچنین به دلیل کم شدن تعداد بروزرسانی تصادفی گره ها، نتایج حاصل از اجرای الگوریتم نیز پایداری بیشتری پیدا کرد و زمان اجرای الگوریتم به شکل موثری کاهش یافت. در ادامه بر اساس تحلیل تعداد جوامع حاصل از فاز اول، روش جدیدی برای ادغام جوامع در فاز دوم ارائه شده است که در نتیجه NMI برای برخی شبکه ها بصورت محسوسی تا حدود 25 / 0 افزایش یافت.

کلیدواژه ها:

انتشار برچسب ، جامعه ، شبکه های اجتماعی ، گره های مرزی