Multilevel approach for combinatorial optimization in bipartite network

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