استحکام شبکه‌های پیچیده

استحکام یا استواری (به انگلیسی: Robustness)، توانایی مقاومت در برابر خرابی‌ها و اختلال‌ها، یکی از ویژگی‌های مهم بسیاری از سامانه‌های پیچیده از جمله شبکه‌های پیچیده است.

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

نظریه تراوش

تمرکز استحکام در شبکه‌های پیچیده، پاسخ شبکه به حذف گره‌ها (به انگلیسی: node) یا پیوندها است. مدل ریاضی چنین فرآیندی را می‌توان به عنوان یک فرایند تراوش معکوس در نظر گرفت. نظریه تراوش فرایند قرار دادن تصادفی سنگریزه‌ها روی یک شبکه n بعدی را با احتمال p مدل می‌کند و تشکیل ناگهانی یک خوشه بزرگ را با احتمال بحرانی$p_{c}$ پیش‌بینی می‌کند. در نظریه تراوش به این خوشه، خوشه تراوا می‌گویند. این پدیده در نظریه تراوش با کمیت‌هایی مثل متوسط اندازه خوش‌ها $\langle s\rangle$ مشخص می‌شود. این کمیت نشان دهنده میانگین اندازه همه خوشه‌های محدود است و با معادله زیر به دست می‌آید.

${\begin{aligned}\langle s\rangle \sim \left|p-p_{c}\right|^{\gamma _{p}}\end{aligned}}$

می‌توانیم ببینیم که متوسط اندازه خوشه به‌طور ناگهانی نزدیک احتمال بحرانی واگرا می‌شود، که نشان‌دهنده تشکیل یک خوشه بزرگ است. همچنین توجه به این نکته ضروری است که توان $\gamma _{p}$ برای همه شبکه‌ها عمومی است، در حالی که $p_{c}$ نیست. این ویژگی مهمی است چرا که نشان دهنده یک گذار فاز عمومی در نقطه‌ای وابسته به توپولوژی شبکه است. مسئله استحکام در شبکه‌های پیچیده را می‌توان به عنوان شروع با خوشه تراوا و حذف بخش مهمی از سنگریزه‌ها برای شکستن خوشه مشاهده کرد. مشابه شکل‌گیری خوشه تراوا در نظریه تراوش، شکستن یک شبکه پیچیده به‌طور ناگهانی در طول یک گذار فاز در بخش مهمی از گره‌ها حذف شده اتفاق می‌افتد.

آستانه بحرانی برای خرابی‌های تصادفی

پیدا کردن آستانه‌ای که در آن یک شبکه پیچیده مولفه غول‌آسا (بزرگترین خوشه) خود را از دست می‌دهد، بر اساس معیار مولوی-ری‌د (به انگلیسی: Molloy-Reed) به دست می‌آید.

${\begin{aligned}\kappa \equiv {\frac {\langle k^{2}\rangle }{\langle k\rangle }}>2\end{aligned}}$

معیار مولوی-ری‌د از قاعده ساده‌ای به دست می‌آید که برای این‌که یک مولفه غول‌پیکر وجود داشته باشد، به‌طور متوسط هر گره در شبکه باید حداقل دو پیوند داشته باشد. این شبیه به این است که هر فرد دست دو نفر دیگر را برای تشکیل یک زنجیره می‌گیرد. با استفاده از این معیار و یک اثبات ریاضی، می‌توان آستانه بحرانی برای کسری از گره‌هایی که برای شکست مولفه غول‌آسا در یک شبکه پیچیده نیاز است را به دست آورد.

${\begin{aligned}f_{c}=1-{\frac {1}{{\frac {\langle k^{2}\rangle }{\langle k\rangle }}-1}}\end{aligned}}$

یک نتیجه مهم این رابطه این است که آستانه بحرانی تنها به گشتاور اول و دوم توزیع درجه وابسته است و برای هر توزیع درجه‌ای معتبر است.

شبکه تصادفی

با استفاده از $\langle k^{2}\rangle =\langle k\rangle (\langle k\rangle +1)$ برای گراف تصادفی اردوش-رنیی، می‌توان نقطه بحرانی یک شبکه تصادفی را این گونه بیان کرد.

${\begin{aligned}f_{c}^{ER}=1-{\frac {1}{\langle k\rangle }}\end{aligned}}$

همان‌طور که یک شبکه تصادفی متراکم‌تر می‌شود، آستانه بحرانی افزایش می‌یابد، به این معنی که بخش بیشتری از گره‌ها باید حذف شوند تا مولفه غول‌آسا ناهمبند شود.

شبکه بی‌مقیاس

با بیان مجدد آستانه بحرانی به عنوان تابعی از توان گاما برای یک شبکه بدون مقیاس، می‌توانیم چند نتیجه مهم در مورد استحکام شبکه بدون مقیاس پیدا کنیم.

${\begin{aligned}f_{c}&=1-{\frac {1}{\kappa -1}}\\\kappa &={\frac {\langle k^{2}\rangle }{\langle k\rangle }}=\left|{\frac {2-\gamma }{3-\gamma }}\right|A\\A&=K_{min},~\gamma >3\\A&=K_{max}^{3-\gamma }K_{min}^{\gamma -2},~3>\gamma >2\\A&=K_{max},~2>\gamma >1\\&where~K_{max}=K_{min}N^{\frac {1}{\gamma -1}}\end{aligned}}$

برای گامای بیشتر از ۳، آستانه بحرانی فقط به گاما و کمترین درجه بستگی دارد، و در این رژیم شبکه مانند یک شبکه تصادفی عمل می‌کند که وقتی بخش محدودی از گره‌ها آن حذف می‌شود، ناهمبند می‌شود. برای گامای کمتر از ۳، $\kappa$ زمانی که N به سمت بی‌نهایت می‌رود، واگرا می‌شود. در این حالت، برای شبکه‌های بدون مقیاس بزرگ، آستانه بحرانی به ۱ نزدیک می‌شود. این اساساً به این معنی است که تقریباً تمام گره‌ها باید حذف شوند تا مؤلفه غول‌آسا از بین برود. شبکه‌های بی‌مقیاس بزرگ نسبت به خرابی‌های تصادفی بسیار مستحکم هستند. می‌توان با اندیشیدن به ناهمگنی شبکه‌های بی‌مقیاس و به‌ویژه هاب‌ها، این نتیجه‌گیری را به‌طور شهودی درک کرد. از آنجایی که هاب‌ها به تعداد نسبتاً کمی وجود دارند، احتمال حذف آنها از طریق خرابی‌های تصادفی کمتر است در حالی که گره‌های کم‌درجه به احتمال زیاد حذف‌می‌شوند. از آنجایی که گره‌ها کم‌درجه اهمیت کمی در همبندی مولفه غول‌آسا دارند، حذف آن‌ها تأثیر کمی دارد.