پیش‌نویس:حذف راس در شبکه

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

حذف تصادفی

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

مدل اردوش-رنی

تأثیری که حذف یک راس شبکه بر همبندی شبکه می‌گذارد، با قطر آن شبکه (طول بیشترین کوتاه‌ترین مسیر بین دو راس) اندازه‌گیری می‌شود. هنگامی که ما کسری $f$ از راس‌ها را حذف می‌کنیم، قطر شبکه به طور یکنواخت با $f$ افزایش می‌یابد. این به این دلیل است که در مدل اردوش-رنی هر راس تقریبا درجه یکسان دارد و بنابراین نسبتا به یک میزان به همبستگی و همبندی شبکه کمک می‌کند.

مدل باراباشی-آلبرت

تاثیر حذف راس بر روی یک شبکه بی‌مقیاس بسیار متفاوت از آنچه که با شبکه های تصادفی تجربه می شود، است. با افزایش $f$، قطر حتی در سطح خطای 5 ٪ هم بدون تغییر باقی می‌ماند. این استحکام نتیجه حضور هاب‌ها (راس‌هایی با بیشترین درجه) در شبکه هستند. تا زمانی که راس‌های با بیشترین درجه کارآمدی خود را از دست نداده‌اند، هم‌بستگی شبکه دست نخورده باقی می‌ماند.

حذف تصادفی از یک شبکه در حال رشد

هنگامی که حذف یک راس با فرآیندهای دیگر ترکیب می‌شود، ساختار شبکه می‌تواند به شدت تغییر کند. برای نشان دادن این ادعا، مدل باراباشی-آلبرت را در نظر بگیرید. در هر مرحله یک راس جدید با m یال به شبکه اضافه کنید و یک راس را با احتمال r را حذف کنید. این منجر به شبکه‌هایی با ساختارهای متفاوت وابسته به m و r می شود.

• $r<1$، فاز بی‌مقیاس: در این دوره شبکه همچنان در حال رشد است، اگرچه نرخ رشد به دلیل حذف راس‌ها کمتر است. در اینجا توزیع درجه، یک توزیع قانون توان باقی می‌ماند که ضریب آن برابر است با: $\gamma =3+{\frac {2r}{1-r}}$.
• $r=1$، فاز نمایی: در این فاز نرخ حذف راس‌ها و نرخ پدید آمدن راس‌های جدید برابر است، بنابراین شبکه دارای اندازه‌ی ثابت است. شبکه خاصیت بی‌مقیاس بودن خود را از دست می‌دهد و توزیع درجه به شکل یک نمایی کشیده تبدیل می‌شود.
• $r>1$، شبکه در حال نابودی: نرخ حذف راس بیشتر از نرخ رشد است، بنابراین اندازه شبکه کاهش می‌یابد و پس از متناهی مرحله ناپدید می‌شود.

حذف هدفمند

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

مدل اردوش-رنی

وقتی راس‌های یک شبکه با مدل اردوش-رنی را با شروع از راس با بیشترین درجه (متصل‌ترین راس) حذف می‌کنیم، قطر مدل اردوش-رنی به مانند حذف تصادفی راس‌ها واکنش نشان می‌دهد. این به این دلیل است که این مدل نسبتا همگن است و درجه راس‌ها به یکدیگر نزدیک است ( توزیع درجه به شدت در اطراف میانگین آن به اوج خود می‌رسد)، بنابراین هدف قرار دادن راس‌های با بیشترین درجه با انتخاب تصادفی آن‌ها چندان متفاوت نیست.

مدل باراباشی-آلبرت

قطر مدل باراباشی-آلبرت زمانی که متصل‌ترین راس‌ها حذف می‌شوند در مقایسه با زمانی که تصادفی حذف می‌شوند، به شدت افزایش می‌یابد. زمانی که تنها 5 درصد از این راس‌ها حذف می شوند، قطر شبکه دو برابر می‌شود. این به این دلیل است که حذف هاب‌ها (متصل‌ترین راس‌ها) به طور جدی ساختار شبکه را تغییر می‌دهد و تاثیر زیادی بر توپولوژی آن دارد، اکثر یال‌ها حذف می شوند، بنابراین قطر بیشتر می‌شود.