تحلیل گراف توانی

شبکه ها نقشی حیاتی در زیست شناسی محاسباتی ایفا می کنند؛ اما تحلیل و نمایش آن ها هنوز یک مسئلهٔ باز است. تحلیل گراف توانی یک تبدیل از شبکه های زیستی به نمایشی فشرده و با افزونگی کمتر است که از وفور خوشه ها و گراف های کامل دوبخشی به عنوان اجزای ابتدایی توپولوژیکی بهره می گیرد. در این تبدیل همهٔ اطلاعات شبکهٔ ابتدایی حفظ می شوند. [ ۱]
گراف ها با دایره ها یا نقطه هایی که نمایش دهندهٔ راس ها هستند و خط هایی که دو راس را به هم وصل می کنند و نمایش دهندهٔ یال ها هستند رسم می شوند. گراف های توانی این شیوهٔ نمایش را گسترش داده و از راس توانی و یال توانی استفاده می کنند. راس های توانی با دایره هایی نشان داده می شوند که تعدادی راس یا راس توانی دیگر را در بر می گیرد. یال های توانی با خط هایی بین راس های توانی نشان داده می شوند.
گراف کامل دوبخشی دو مجموعه از رئوس است که بین هر راس از مجموعهٔ اول و هر راس از مجموعهٔ دوم یال وجود دارد. در یک گراف توانی، یک گراف کامل دوبخشی به صورت یک یال بین دو راس توانی نشان داده می شود.
خوشه مجموعه ای از رئوس است که بین هر دو راس یال وجود دارد. در یک گراف توانی، یک خوشه به صورت یک راس توانی با یک طوقه نشان داده می شود.
ستاره مجموعه ای از رئوس است که بین یک راس از آن و بقیهٔ رئوس یال وجود دارد. در واقع ستاره حالت خاصی از گراف کامل دوبخشی است که در آن اندازهٔ یکی از بخش ها برابر ۱ است. در یک گراف توانی، ستاره به صورت یک یال توانی بین یک راس معمولی و یک راس توانی نشان داده می شود.
با داشتن گراف G = ( V , E ) که در آن V = { v 1 , … , v n } مجموعهٔ راس ها و E ⊆ V × V مجموعهٔ یال هاست، گراف توانی G ′ = ( V ′ , E ′ ) گرافی است که توسط مجموعه رئوس توانی V ′ ⊆ P ( V ) که با یال های توانی E ′ ⊆ V ′ × V ′ به هم متصل شده اند تعریف می شود؛ بنابراین گراف های توانی روی مجموعه توانی راس ها و مجموعه توانی یال ها تعریف می شوند.
معنی شناسی گراف توانی به این صورت است: اگر دو راس توانی با یک یال توانی به هم متصل اند، به این معنی است که همهٔ رئوس درون راس توانی اول به همهٔ رئوس درون راس توانی دوم متصل اند. به طور مشابه، اگر یک راس توانی با یک یال توانی به خودش متصل باشد، به این معنی است که رئوس درون این راس توانی دو به دو به هم متصل اند.