Связность и отказоустойчивость в случайных регулярных графах

Ключевые слова и синонимы: Устойчивость

Постановка задачи

Новая модель случайных графов, которая была предложена в работе [7], касается случайных графов с пропущенными дугами (далее обозначаемыми [math]\displaystyle{ G^r_{n,p} }[/math]), полученных путем выбора дуг из случайного элемента множества всех регулярных графов степени r независимым образом, с вероятностью p. Такие графы могут представлять сеть коммуникаций, в которой связи обрываются независимо друг от друга с вероятностью f = 1 — p. Формальное определение пространства вероятностей [math]\displaystyle{ G^r_{n,p} }[/math] выглядит следующим образом:

Определение 1 (пространство вероятности [math]\displaystyle{ G^r_{n,p} }[/math]). Пусть [math]\displaystyle{ G^r_n }[/math] – пространство вероятности всех случайных регулярных графов с n вершинами, каждая вершина которых имеет степень r. Пространство вероятности [math]\displaystyle{ G^r_{n,p} }[/math] случайных регулярных графов с пропущенными дугами строится на основании двух последовательных случайных экспериментов: вначале из пространства [math]\displaystyle{ G^r_n }[/math] выбирается случайный регулярный граф, а затем каждая дуга случайным и независимым образом удаляется из этого графа с вероятностью f = 1 — p.

Важное свойство связности [math]\displaystyle{ G^r_{n,p} }[/math] исследуется путем оценки диапазонов r и f, для которых, с высокой вероятностью, графы [math]\displaystyle{ G^r_{n,p} }[/math] (а) являются сильно связными; (б) теряют связность и (в) содержат большой (размера [math]\displaystyle{ \Theta\ (n) }[/math]) связный компонент меньшего диаметра.

Нотация

Термины «почти наверняка» и «с высокой вероятностью» будут использоваться в их обычном значении при описании свойств случайных графов. Свойство, определенное для случайного графа, выполняется «почти наверняка», если его вероятность стремится к 1 по мере того, как значение независимой переменной (обычно такой переменной является число вершин графа) стремится к бесконечности. Выражение «с высокой вероятностью» означает, что вероятность выполнения свойства случайного графа (или вероятность успешного завершения рандомизированного алгоритма) равна по меньшей мере [math]\displaystyle{ 1 - \; n^{- \alpha\ } }[/math], где [math]\displaystyle{ \alpha\ \gt 0 }[/math] – константа, а n – число вершин графа. В [1] приводится великолепное изложение вероятностного метода и вариантов его применения, [2] является классическим учебником по случайным графам, а [6] представляет собой превосходное пособие по конструированию и анализу рандомизированных алгоритмов.

Основные результаты

Рассмотрим несколько важных свойств связности для случайных регулярных графов с ошибочными дугами. Чтобы иметь возможность работать с моделью [math]\displaystyle{ G^r_{n,p} }[/math], в [7] вначале расширяется понятие конфигураций и приводится лемма о переводе между конфигурациями и случайными регулярными графами, введенная Боллобасом [2, 3]; вводится понятие случайных конфигураций, отвечающих за пропущенные дуги, и приводится расширенная лемма о переводе между случайными конфигурациями и случайными регулярными графами с пропущенными дугами.

Согласно [7], для этой новой модели случайных регулярных графов с пропущенными дугами верно следующее:

1. Для всех вероятностей ошибки [math]\displaystyle{ f = 1 - p \le n^{- \epsilon\ } }[/math] ([math]\displaystyle{ \epsilon\ \ge \frac{3}{2r} }[/math] фиксировано) и любого [math]\displaystyle{ r \ge 3 }[/math] наибольшая часть [math]\displaystyle{ G^r_{n,p} }[/math] (иными словами, весь граф за вычетом O(1) вершин) остается связной и, таким образом, связная часть графа почти наверняка не может быть выделена, если только не будут удалены более r вершин. Заметим, что ситуация с диапазоном графа и значением r, несмотря на пропуски, очень напоминает свойства [math]\displaystyle{ G^r_n }[/math], являющегося r-связным для [math]\displaystyle{ r \ge 3 }[/math].

2. [math]\displaystyle{ G^r_{n,p} }[/math] почти наверняка теряет связность для константного f и любого [math]\displaystyle{ r = o(log \; n) }[/math], однако почти наверняка обладает высокой связностью в случае [math]\displaystyle{ r \ge \alpha\ log \; n }[/math], где [math]\displaystyle{ \alpha\ \gt 0 }[/math] – подходящая константа.

3. Даже если [math]\displaystyle{ G^r_{n,p} }[/math] теряет связность, он по-прежнему включает огромный компонент меньшего диаметра, даже если r = O(1). Разработан алгоритм для построения этого огромного компонента за время O(n log n).

Лемма о конфигурации, лемма о переводе

С технической точки зрения делать какие-либо утверждения о случайных регулярных графах не так просто, как в случае [math]\displaystyle{ G_{n,p} }[/math], в силу стохастических зависимостей от существования дуг, связанных с регулярностью. Введенная Боллобасом [2, 3] нотация конфигурации предназначена для перевода операторов для случайных регулярных графов в операторы для соответствующих конфигураций, которые не содержат зависимостей между дугами в силу регулярности и с которыми поэтому намного проще работать.

Определение 2 (Боллобас, [3]). Пусть [math]\displaystyle{ w = \cup^n_{j=1} w_j }[/math] – фиксированное множество [math]\displaystyle{ 2m = \sum^n_{j=1} d_j }[/math] помеченных вершин, где [math]\displaystyle{ |w_j| = d_j \; }[/math]. Конфигурация F представляет собой разбиение w на m пар вершин, называемых дугами F.

Пусть дана конфигурация F. Пусть [math]\displaystyle{ \theta\ (F) }[/math] – (мульти)граф с множеством вершин V, в котором (i, j) является дугой в том и только том случае, если в F имеется пара (дуга), имеющая один элемент в [math]\displaystyle{ w_i \; }[/math], а другой – в [math]\displaystyle{ w_j \; }[/math]. Заметим, что каждый регулярный граф [math]\displaystyle{ G \in G^r_n }[/math] имеет форму [math]\displaystyle{ \theta\ (F) }[/math] в точности для [math]\displaystyle{ (r!)^n \; }[/math] конфигураций. Однако не каждая конфигурация F с [math]\displaystyle{ d_j = r \; }[/math] для всех j соответствует ситуации [math]\displaystyle{ G \in G^r_n }[/math], поскольку F может содержать дугу, полностью находящуюся в некотором [math]\displaystyle{ w_j \; }[/math], либо параллельные дуги, связывающие [math]\displaystyle{ w_i \; }[/math] и [math]\displaystyle{ w_j \; }[/math].

Пусть [math]\displaystyle{ \varphi\ \; }[/math] – множество всех конфигураций F, а [math]\displaystyle{ G^r_n }[/math] – множество всех регулярных графов. Учитывая свойство [math]\displaystyle{ Q \subseteq G^r_n }[/math], положим [math]\displaystyle{ Q^* \subseteq \phi\ }[/math], такое, что [math]\displaystyle{ Q^* \cap \theta\ ^{-1} (G^r_n) = \theta\ ^{-1}(Q) }[/math]. В результате оценки вероятности возможных циклов длины 1 (петля) и 2 (цикл) между парами [math]\displaystyle{ w_i, w_j \; }[/math] в [math]\displaystyle{ \theta\ (F) }[/math] получается следующая лемма.

Лемма 1 (Боллобас, [2]). Если [math]\displaystyle{ r \ge 2 \; }[/math] фиксировано, а свойство [math]\displaystyle{ Q^* \; }[/math] выполняется для конфигурации почти наверняка, то свойство Q почти наверняка выполняется для r–регулярного графа.

Основная ценность этой леммы заключается в том, что при исследовании случайных регулярных графов вместо рассмотрения множества всех случайных регулярных графов можно исследовать только множество конфигураций, работать с которым намного проще.

Для обработки пропущенных дуг в [7] вводится следующее расширение понятия конфигураций:

Определение 3 (случайные конфигурации). Пусть [math]\displaystyle{ w = \cup^n_{j=1} w_j }[/math] – фиксированное множество [math]\displaystyle{ 2m = \sum^n_{j=1} d_j }[/math] помеченных «вершин», где [math]\displaystyle{ |w_j| = d_j \; }[/math]. Пусть F – любая конфигурация множества [math]\displaystyle{ \varphi\ \; }[/math] . Взяв каждую дугу из F, удалить ее с вероятностью 1 — p независимым от других образом. Пусть [math]\displaystyle{ \quad \hat{\phi\ } }[/math] – новое множество объектов, а [math]\displaystyle{ \quad \hat{F} }[/math] – результат эксперимента. [math]\displaystyle{ \quad \hat{F} }[/math] будем называть случайной конфигурацией.

Если ввести для каждой дуги вероятность p, расширение доказательства леммы 1 (поскольку и в [math]\displaystyle{ \bar{Q} }[/math], и в [math]\displaystyle{ \hat{Q} }[/math] каждая дуга имеет одну и ту же вероятность быть удаленной одинаково независимо от других, в результате чего модифицированные пространства соответствуют свойствам [math]\displaystyle{ Q \; }[/math] и [math]\displaystyle{ Q^* \; }[/math]) приводит к следующему расширению случайных конфигураций.

Лемма 2 (расширенная лемма о переводе). Пусть [math]\displaystyle{ r \ge 2 \; }[/math] фиксировано, пусть [math]\displaystyle{ \bar{Q} }[/math] – свойство графов из [math]\displaystyle{ G^r_{n,p} }[/math]. Если свойство [math]\displaystyle{ \hat{Q} }[/math] выполняется для случайной конфигурации почти наверняка, то соответствующее свойство [math]\displaystyle{ \bar{Q} }[/math] почти наверняка выполняется для графа в [math]\displaystyle{ G^r_{n,p} }[/math].

Свойство мультисвязности [math]\displaystyle{ G^r_{n,p} }[/math]

Рассматривается случай вероятности постоянного возникновения пропущенных дуг f, представляющего наихудший случай для сохранения связности. В [7] показано, что логарифмических степеней достаточно, чтобы гарантировать, что [math]\displaystyle{ G^r_{n,p} }[/math] с высокой вероятностью остается сильно связным, несмотря на постоянное возникновение пропусков дуг. Подробнее об этом говорит следующая теорема.

Теорема 3. Пусть G – экземпляр [math]\displaystyle{ G^r_{n,p} }[/math], где [math]\displaystyle{ p = \Theta(1) \; }[/math] и [math]\displaystyle{ r \ge \alpha\ log n }[/math], где [math]\displaystyle{ \alpha \gt 0 \; }[/math] – подходящая константа.

Тогда G почти наверняка является k-связным, где [math]\displaystyle{ k = O\left ( \frac{log \; n}{log \; log \; n} \right ) }[/math]

В доказательстве теоремы используется граница Черноффа для оценки степеней вершин в [math]\displaystyle{ G^r_{n,p} }[/math] и «схожести» [math]\displaystyle{ G^r_{n,p} }[/math] и [math]\displaystyle{ G_{n,p'} \; }[/math] (свойства которого известны) для подходящим образом выбранного [math]\displaystyle{ p' \; }[/math].

Для более практичного случая, в котором [math]\displaystyle{ f = 1 - p = o(1) \; }[/math], доказано, что желаемые свойства связности случайных регулярных графов почти сохраняются, несмотря на появление пропущенных ребер.

Теорема 4. Пусть [math]\displaystyle{ r \ge 3 \; }[/math] и [math]\displaystyle{ f = 1 - p = O(n^{- \epsilon\ }) }[/math] для [math]\displaystyle{ \epsilon\ \ge \frac{3}{2r} }[/math]. Тогда наибольшая часть [math]\displaystyle{ G^r_{n,p} }[/math] (иными словами, весь граф за вычетом O(1) вершин) сохраняет связность, и эта связная часть графа (за исключением вершин, которые изначально были соседями потерявшего связность множества размером O(1)) не может быть выделена, если только не удалены более r вершин, с вероятностью, стремящейся к 1, по мере того, как n стремится к [math]\displaystyle{ + \infty }[/math].

Для доказательства используется расширенная для работы с пропущенными дугами техника, предназначенная для недопущения малых разделителей в случайных регулярных графах. с вероятностью не менее 1 — O(log n)/(na/3), где a > 0 – константа, которую требуется выбрать. Для доказательства существования компоненты необходимо вначале доказать существование (с высокой вероятностью) достаточно длинного пути (логарифмической длины) в качестве основы для процесса поиска базисного возможного решения, начинающегося с вершин того пути, на основе которого создается компонент. В процессе довольно сложного доказательства используются соображения занятости (столбики диаграмм соответствуют вершинам графов, а шары – дугам); однако упоминаемые в ходе него случайные переменные не являются независимыми, и для использования границ Черноффа-Хеффдинга для концентрации необходимо вначале доказать, что эти случайные переменные, не будучи независимыми, являются отрицательно связанными. Далее при оценке успешности процесса поиска базисного возможного решения используется более точный и детальный алгоритм «анализа в среднем». Построение пути и процесса поиска базисного возможного решения могут в совокупности рассматриваться как алгоритм, который (в случае, если не найдено пропусков) позволяет найти огромный связный компонент. Этот алгоритм весьма эффективен, что иллюстрирует следующая теорема.

Теорема 7. Огромный компонент Gnr; p может быть построен за время O(n log n) с вероятностью не менее 1 — O(log2 n)/(nal3), где a > 0 – константа, которую можно выбрать. Gnr;p теряет связность log n Заметим, что вероятность постоянного возникновения пропущенных дуг существенно изменяет структуру связности регулярного графа в случае низких значений степеней. В частности, использование понятия случайных конфигураций [ ] позволяет доказать следующую теорему:

Теорема 5. Если 2 < r < - r - 2 и p = 0(1), то Grn p содержит по меньшей мере одну изолированную вершину с вероятностью не менее l-n~k,k>2. На деле скорость потери связности выше, поскольку в [7] показано, что Grn p почти наверняка теряет связность даже для r = o(log n) и константного значения f. Доказательство последнего утверждения осложняет тот факт, что применение расширенной леммы о переводе невозможно из-за диапазона r.

Существование огромного компонента в Grn;p Поскольку Gnr; p почти наверняка теряет связность при r = o(log n) и 1 — p = f = 0(1), было бы интересно узнать, остается ли связной по крайней мере большая часть сети, представленной Grn p; иными словами, является ли наибольший связный компонент Gnr;p действительно большим. В частности, в [ ] утверждается следующее:

Теорема 6. Если f < 1 — ^, то Grn p содержит огромный (размером 0{n)) связный компонент для любого r > 64

Применение

В последние годы развитие и использование распределенных систем и коммуникационных сетей шло стремительными темпами. Современные многопроцессорные архитектуры производят вычисления в средах структурированных регулярных сетей. В подобной среде несколько приложений могут исполняться одновременно в одной и той же сети. Это приводит к тому, что определенные ресурсы сети (например, связи) становятся недоступными для определенных приложений. Точно так же к недоступности связей или вершин могут приводить ошибки. Вопрос надежности распределенных вычислений (включающий в себя вычисления на доступных ресурсах и устойчивость к ошибкам) повышает ценность приложений, разработанных в таких средах. Когда вычисления производятся в присутствии ошибок, невозможно считать структуру вычислительной среды заведомо известной. Ошибки могут появляться даже во время исполнения. То, что одному приложению представляется «ошибочной» или «недоступной» связью, может на деле представлять собой, например, открепление этой связи из-за ее назначения сетевой операционной системой другому приложению. Задача анализа размещенных вычислений или коммуникаций в сети по случайным образом назначенной подсети и в присутствии ошибок заметно отличается от задачи анализа ошибок в хорошо структурированных сетях специального вида (таких как гиперкуб), в которой не учитываются сетевые аспекты. Здесь решается именно эта интересная задача, то есть анализ среднего случая, взятого над множеством возможных топологий, состоящая в определении мультисвязности и существования свойств огромного компонента, необходимых для обеспечения надежности распределенных вычислений в подобных случайным образом размещаемых ненадежных средах. Отдельного упоминания заслуживает один из важнейших вариантов ее применения: многозадачность в мультипроцессорах с распределенной памятью обычно достигается путем назначения каждой задаче (называемой графом вычислений) произвольной подсети имеющейся сети. В результате каждая параллельная программа может быть представлена в виде взаимосвязей процессоров над графом вычислений. Заметим, что величина мультисвязности k графа вычислений означает, что исполнение приложения может допускать до k — 1 дополнительных ошибок в режиме выполнения.

Открытые вопросы

На основе представленных в [ ] идей были проведены и другие интересные исследования. Андреас Гердт [ ] продолжил работать над темами, представленными в предыдущей ([8]) версии работы [7], и продемонстрировал следующие результаты: если степерь r фиксирована, то p = -^ представляет собой пороговую вероятность существования компонента линейного размера в версии почти любого случайного регулярного графа с пропусками дуг. Фактически он демонстрирует, что в случае, если каждая дуга произвольного графа G с максимальной степенью, ограниченной сверху r, имеется в наличии с вероятностью p = -^, где Я < 1, тогда версия G с пропусками дуг с высокой вероятностью содержит только компоненты, имеющие не более чем логарифмический размер относительно числа вершин. Из этого следует некоторое понятие оптимальности случайных регулярных графов с пропущенными дугами. В [5, 10] исследуются важные свойства расширения случайных регулярных графов с пропущенными дугами; в [ ] та же задача рассматривается для случая утолщенных деревьев – распространенного типа топологии сетей. В продолжение этих исследований следовало бы изучить другие комбинаторные свойства случайных регулярных графов с пропущенными дугами, а также предложить для них эффективные алгоритмы.

См. также

• Гамильтоновы циклы в случайных графах пересечений
• Независимые множества в случайных графах пересечений
• Минимальные k-связные геометрические сети

Литература

1. Alon, N., Spencer, J.: The Probabilistic Method. Wiley (1992) 2. Bollobas, B.: Random Graphs. Academic Press (1985) 3. Bollobas, B.: A probabilistic proof of an asymptotic formula for the number of labeled regular graphs. Eur. J. Comb. 1,311-316 (1980) 4. Goerdt, A.: The giant component threshold for random regular graphs with edge faults. In: Proceedings of Mathematical Foundations of Computer Science '97 (MFCS'97), pp. 279-288. (1997) 5. Goerdt, A.: Random regular graphs with edge faults: Expansion through cores. Theor. Comput. Sci. 264(1), 91-125 (2001) 6. Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press (1995) 7. Nikoletseas, S., Palem, K., Spirakis, P., Yung, M.: Connectivity Properties in Random Regular Graphs with Edge Faults. In: Special Issue on Randomized Computing of the International Journal of Foundations of Computer Science (IJFCS), vol. 11 no. 2, pp. 247-262, World Scientific Publishing Company (2000) 8. Nikoletseas, S., Palem, K., Spirakis, P., Yung, M.: Short Vertex Disjoint Paths and Multiconnectivity in Random Graphs: Reliable Network Computing. In: Proc. 21st International Colloquium on Automata, Languages and Programming (ICALP), pp. 508-515. Jerusalem (1994) 9. Nikoletseas, S., Pantziou, G., Psycharis, P., Spirakis, P.: On the reliability of fat-trees. In: Proc. 3rd International European Conference on Parallel Processing (Euro-Par), pp. 208-217, Passau, Germany (1997) 10. Nikoletseas, S., Spirakis, P.: Expander Properties in Random Regular Graphs with Edge Faults. In: Proc. 12th Annual Symposium on Theoretical Aspects of Computer Science (STACS), pp.421 -432, MCinchen (1995)