Какие сети наименее подвержены каскадным сбоям?

Описание: Распространение каскадных отказов по сети — проблема, возникающая во многих областях: в случае зараженных отказов, распространяющихся среди финансовых учреждений во время финансового кризиса, через узлы энергосистемы или сети связи во время масштабного отключения электроэнергии, или через человеческую популяцию во время вспышки эпидемического заболевания. Здесь мы изучаем естественную модель порогового заражения: каждому узлу присваивается числовой порог, независимо взятый из базового распределения, и он выйдет из строя, как только число его вышедших из строя соседей достигнет этого порога. Несмотря на простоту формулировки, анализ процессов отказов, возникающих при произвольных пороговых распределениях, оказался очень сложной задачей; даже качественные вопросы о том, какие графы наиболее устойчивы к каскадным отказам в этих моделях, было трудно решить. Мы разрабатываем набор новых методов анализа вероятностей отказов узлов в произвольных графах в рамках этой модели и сравниваем различные графы по максимальной вероятности отказа любого узла в графе, когда пороги взяты из заданного распределения. Мы обнаружили, что пространство распределений пороговых значений обладает удивительно богатой структурой, если рассматривать риск, который эти пороговые значения создают для различных графов: небольшие сдвиги в распределении пороговых значений могут благоприятствовать графам с максимально кластерной структурой (т. е. кликам), графам с максимально разветвленной структурой (деревьям) или даже промежуточным гибридам. Это совместная работа с Ларри Блюмом, Дэвидом Исли, Бобби Кляйнбергом и Евой Тардос.