تحلیل گراف توانی - ویکی‌پدیا، دانشنامهٔ آزاد

شبکه‌ها نقشی حیاتی در زیست‌شناسی محاسباتی ایفا می‌کنند؛ اما تحلیل و نمایش آن‌ها هنوز یک مسئلهٔ باز است. تحلیل گراف توانی یک تبدیل از شبکه‌های زیستی به نمایشی فشرده و با افزونگی کمتر است که از وفور خوشه‌ها و گراف‌های کامل دوبخشی به عنوان اجزای ابتدایی توپولوژیکی بهره می‌گیرد. در این تبدیل همهٔ اطلاعات شبکهٔ ابتدایی حفظ می‌شوند.^[۱]

گراف توانی[ویرایش]

نمایش گرافیکی[ویرایش]

گراف‌ها با دایره‌ها یا نقطه‌هایی که نمایش‌دهندهٔ راس‌ها هستند و خط‌هایی که دو راس را به هم وصل می‌کنند و نمایش‌دهندهٔ یال‌ها هستند رسم می‌شوند. گراف‌های توانی این شیوهٔ نمایش را گسترش داده و از راس توانی و یال توانی استفاده می‌کنند. راس‌های توانی با دایره‌هایی نشان داده می‌شوند که تعدادی راس یا راس توانی دیگر را در بر می‌گیرد. یال‌های توانی با خط‌هایی بین راس‌های توانی نشان داده می‌شوند.

گراف کامل دوبخشی دو مجموعه از رئوس است که بین هر راس از مجموعهٔ اول و هر راس از مجموعهٔ دوم یال وجود دارد. در یک گراف توانی، یک گراف کامل دوبخشی به صورت یک یال بین دو راس توانی نشان داده می‌شود.

خوشه مجموعه‌ای از رئوس است که بین هر دو راس یال وجود دارد. در یک گراف توانی، یک خوشه به صورت یک راس توانی با یک طوقه نشان داده می‌شود.

ستاره مجموعه‌ای از رئوس است که بین یک راس از آن و بقیهٔ رئوس یال وجود دارد. در واقع ستاره حالت خاصی از گراف کامل دوبخشی است که در آن اندازهٔ یکی از بخش‌ها برابر ۱ است. در یک گراف توانی، ستاره به صورت یک یال توانی بین یک راس معمولی و یک راس توانی نشان داده می‌شود.

تعریف رسمی[ویرایش]

با داشتن گراف ${\displaystyle G={\bigl (}{V,E}{\bigr )}}$ که در آن ${\displaystyle V={\bigl \{}v_{1},\dots ,v_{n}{\bigr \}}}$ مجموعهٔ راس‌ها و ${\displaystyle E\subseteq V\times V}$ مجموعهٔ یال‌هاست، گراف توانی ${\displaystyle G'={\bigl (}{V',E'}{\bigr )}}$ گرافی است که توسط مجموعه رئوس توانی ${\displaystyle V'\subseteq {\mathcal {P}}{\bigl (}V{\bigr )}}$ که با یال‌های توانی ${\displaystyle E'\subseteq V'\times V'}$ به هم متصل شده‌اند تعریف می‌شود؛ بنابراین گراف‌های توانی روی مجموعه توانی راس‌ها و مجموعه توانی یال‌ها تعریف می‌شوند.

معنی‌شناسی گراف توانی به این صورت است: اگر دو راس توانی با یک یال توانی به هم متصل اند، به این معنی است که همهٔ رئوس درون راس توانی اول به همهٔ رئوس درون راس توانی دوم متصل اند. به‌طور مشابه، اگر یک راس توانی با یک یال توانی به خودش متصل باشد، به این معنی است که رئوس درون این راس توانی دو به دو به هم متصل اند.

دو شرط زیر برای ساده‌سازی نمایش لازم اند:

• شرط سلسله‌مراتب راس‌های توانی: هر دو راس توانی یا مجزا اند یا یکی زیرمجموعهٔ دیگری است.
• شرط جدایی یال‌های توانی: هر یال در گراف اصلی با یک و فقط یک یال توانی نمایش داده می‌شود. به بیان دیگر یال‌های توانی یک افراز از یال‌های گراف اصلی هستند.

رعایت نکردن این دو شرط منجر به یک گراف توانی انتزاعی می‌شود که به سختی قابل نمایش دادن است.^[۱]

الگوریتم گراف توانی[ویرایش]

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

• در فاز اول، هدف پیدا کردن راس‌های توانی بالقوه است. اگر مجموعه‌ای از رئوس دارای همسایه‌های مشابه باشند، این مجموعه یک کاندیدا برای یک راس توانی است. برای تشخیص این مجموعه‌ها از یک الگوریتم خوشه‌بندی سلسله‌مراتبی بر اساس شباهت همسایگی استفاده می‌شود. معیار شباهت در این الگوریتم، اندیس ژاکار است (البته می‌توان از معیارهای دیگری نیز برای شباهت همسایگی استفاده کرد). این اندیس همیشه مقداری بین ۰ و ۱ دارد: اگر مجموعه‌های ${\displaystyle U}$ و ${\displaystyle V}$ هیچ همسایهٔ مشترکی نداشته باشند برابر ۰ است و اگر همسایه‌هایشان دقیقاً یکسان باشند برابر ۱ است. شکل ۲ نشان می‌دهد چگونه خوشه‌بندی راس‌هایی که همسایگی یکسان یا مشابه دارند، مجموعه‌های کاندیدا برای خوشه‌ها و گراف‌های کامل دوبخشی را بدست می‌دهد.
• در بین راس‌های توانی بالقوه که در فاز اول بدست آمدند، هر دوتایی که متناظر با یک یال توانی باشند، یک کاندیدا برای یال توانی اند. از بین این یال‌های توانی، آن که شامل بیشترین یال از گراف اصلی است را به گراف توانی اضافه می‌کنیم. این کار را به‌طور پی در پی ادامه می‌دهیم تا زمانی که همهٔ یال‌های گراف اصلی اضافه شوند. در نهایت آن راس‌های توانی کاندیدایی که انتهای هیچ‌یک از یال‌های توانی نیستند از گراف توانی حذف می‌شوند.^[۱]

کاربردها[ویرایش]

شبکه‌های زیستی[ویرایش]

نشان داده شده که تحلیل گراف توانی روشی مفید برای تحلیل انواع متنوعی از شبکه‌های زیستی از جمله شبکه‌های تعامل پروتئین-پروتئین،^[۱] شبکه تنظیم‌کننده ژن^[۲] و شبکه‌های همولوژی/پارالوژی است. همچنین به وسیلهٔ گراف توانی می‌توان یک نرخ فشرده‌سازی برای گراف‌ها تعریف کرد که معیاری مناسب برای سنجش کیفیت یک شبکهٔ تعاملی پروتئین است.^[۳] اگر گراف اولیه ${\displaystyle |E|}$ یال و گراف توانی ${\displaystyle |E'|}$ یال داشته باشد، نرخ فشرده‌سازی به این صورت محاسبه می‌شود: ${\displaystyle c={\frac {|E|-|E'|}{|E|}}}$.

نرخ فشرده‌سازی عددی بین ۰ و ۱ است. اگر تعداد یال‌های گراف توانی و گراف اولیه برابر باشند، نرخ فشرده‌سازی برابر ۰ است. بیشترین نرخ فشرده‌سازی مربوط به شبکه‌ای است که همهٔ رئوس آن به هم متصل اند؛ که این شبکه به یک یال توانی کاهش می‌یابد. گراف‌های توانی تا ۸۵ درصد یال‌ها را در شبکه‌های برهم‌کنش پروتئینی فشرده می‌کنند.

شبکه‌های اجتماعی[ویرایش]

از تحلیل گراف توانی برای تشخیص جامعه‌ها در شبکه‌های اجتماعی پیچیده استفاده می‌شود.^[۴]

جستارهای وابسته[ویرایش]

• زیست‌شناسی محاسباتی
• شبکه‌ها/گراف
• شبکه‌های پیچیده

منابع[ویرایش]