واحد های اصلی شبکه های پیچیده: مروری بر الگوریتم های جستجوی موتیف در شبکه

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

کلیدواژه ها:

جستجوی موتیف ، شبکه های پیچیده ، فراوانی ، زیرگراف