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

Материал из WEGA
Перейти к навигации Перейти к поиску

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

in Random Regular Graphs

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

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

Новая модель случайных графов, которая была предложена в работе [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].


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


[math]\displaystyle{ G^r_{n,p} }[/math] теряет связность


Заметим, что вероятность постоянного возникновения пропущенных ребер существенно изменяет структуру связности регулярного графа в случае низких значений степеней. В частности, использование понятия случайных конфигураций [7] позволяет доказать следующую теорему:


Теорема 5. Если [math]\displaystyle{ 2 \le r \le \frac{\sqrt{log \; n}}{2} }[/math] и [math]\displaystyle{ p = \Theta\ (1) \; }[/math], то [math]\displaystyle{ G^r_{n,p} }[/math] содержит по меньшей мере одну изолированную вершину с вероятностью не менее [math]\displaystyle{ 1 - n^{- k}, k \ge 2 }[/math].


На деле скорость потери связности выше, поскольку в [7] показано, что [math]\displaystyle{ G^r_{n,p} }[/math] почти наверняка теряет связность даже для [math]\displaystyle{ r = o(log \; n) }[/math] и константного значения f. Доказательство последнего утверждения осложняет тот факт, что применение расширенной леммы о переводе невозможно из-за диапазона r.


Существование огромного компонента в [math]\displaystyle{ G^r_{n,p} }[/math]


Поскольку [math]\displaystyle{ G^r_{n,p} }[/math] почти наверняка теряет связность при [math]\displaystyle{ r = o(log \; n) }[/math] и [math]\displaystyle{ 1 - p = f = \Theta\ (1) }[/math], было бы интересно узнать, остается ли связной по крайней мере большая часть сети, представленной [math]\displaystyle{ G^r_{n,p} }[/math]; иными словами, является ли наибольший связный компонент [math]\displaystyle{ G^r_{n,p} }[/math] действительно большим. В частности, в [7] утверждается следующее:


Теорема 6. Если [math]\displaystyle{ f \lt 1 - \frac{32}{r} }[/math], то [math]\displaystyle{ G^r_{n,p} }[/math] содержит огромный (размером [math]\displaystyle{ \Theta\ (n) \; }[/math]) связный компонент для любого [math]\displaystyle{ r \ge 64 \; }[/math] с вероятностью не менее [math]\displaystyle{ 1 - O(log^2 n)/(n^{\alpha\ /3}) }[/math], где [math]\displaystyle{ \alpha\ \gt 0 }[/math] – константа, которую требуется выбрать.


Для доказательства существования компоненты необходимо вначале доказать существование (с высокой вероятностью) достаточно длинного пути (логарифмической длины) в качестве основы для процесса обхода в ширину, начинающегося с вершин того пути, на основе которого создается компонент. В процессе довольно сложного доказательства используются соображения занятости (столбики диаграмм соответствуют вершинам графов, а круги – ребрам); однако упоминаемые в ходе него случайные переменные не являются независимыми, и для использования границ Чернова-Хёффдинга для концентрации необходимо вначале доказать, что эти случайные переменные, не будучи независимыми, являются отрицательно связанными. Далее при оценке успешности процесса обхода в ширину используется более точный и детальный алгоритм «анализа в среднем».

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

Теорема 7. Огромный компонент [math]\displaystyle{ G^r_{n,p} }[/math] может быть построен за время [math]\displaystyle{ O(n \; log \; n) }[/math] с вероятностью не менее [math]\displaystyle{ 1 - O(log^2 n)/(n^{\alpha\ /3}) }[/math], где [math]\displaystyle{ \alpha\ \gt 0 }[/math] – константа, которую можно выбрать.

Применение

В последние годы развитие и использование распределенных систем и коммуникационных сетей шло стремительными темпами. Современные многопроцессорные архитектуры производят вычисления в средах структурированных регулярных сетей. В подобной среде несколько приложений могут выполняться одновременно в одной и той же сети. Это приводит к тому, что определенные ресурсы сети (например, связи) становятся недоступными для определенных приложений. Точно так же к недоступности связей или вершин могут приводить ошибки. Вопрос надежности распределенных вычислений (включающий в себя вычисления на доступных ресурсах и устойчивость к ошибкам) повышает ценность приложений, разработанных в таких средах.

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

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

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

На основе представленных в [7] идей были проведены и другие интересные исследования. Андреас Гердт [4] продолжил работать над темами, представленными в предыдущей ([8]) версии работы [7], и продемонстрировал следующие результаты: если степень r фиксирована, то [math]\displaystyle{ p = \frac{1}{r - 1} }[/math] представляет собой пороговую вероятность существования компонента линейного размера в версии почти любого случайного регулярного графа с пропусками ребер. Фактически он демонстрирует, что в случае, если каждое ребро произвольного графа G с максимальной степенью, ограниченной сверху r, имеется в наличии с вероятностью [math]\displaystyle{ p = \frac{\lambda\ }{r - 1} }[/math], где [math]\displaystyle{ \lambda\ \lt 1 \; }[/math], тогда версия G с пропусками ребер с высокой вероятностью содержит только компоненты, имеющие не более чем логарифмический размер относительно числа вершин. Из этого следует некоторое понятие оптимальности случайных регулярных графов с пропущенными ребрами. В [5, 10] исследуются важные свойства расширения случайных регулярных графов с пропущенными ребрами; в [9] та же задача рассматривается для случая утолщенных деревьев – распространенного типа топологии сетей. В продолжение этих исследований следовало бы изучить другие комбинаторные свойства случайных регулярных графов с пропущенными ребрами, а также предложить для них эффективные алгоритмы.

См. также

Литература

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)

Источник — http://pco.iis.nsk.su/wega/index.php?title=Связность_и_отказоустойчивость_в_случайных_регулярных_графах&oldid=15669