Связность и отказоустойчивость в случайных регулярных графах: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
Строка 2: | Строка 2: | ||
== Постановка задачи == | == Постановка задачи == | ||
Новая модель [[случайный граф|случайных графов]], которая была предложена в работе [7], касается случайных графов с пропущенными | Новая модель [[случайный граф|случайных графов]], которая была предложена в работе [7], касается случайных графов с пропущенными ребрами (далее обозначаемыми <math>G^r_{n,p}</math>), полученных путем выбора ребер из случайного элемента множества всех регулярных графов степени r независимым образом, с вероятностью p. Такие графы могут представлять сеть коммуникаций, в которой связи обрываются независимо друг от друга с вероятностью f = 1 — p. Формальное определение пространства вероятностей <math>G^r_{n,p}</math> выглядит следующим образом: | ||
'''Определение 1 (пространство вероятности <math>G^r_{n,p}</math>).''' Пусть <math>G^r_n</math> – пространство вероятности всех случайных регулярных графов с n вершинами, каждая вершина которых имеет степень r. Пространство вероятности <math>G^r_{n,p}</math> случайных регулярных графов с пропущенными | '''Определение 1 (пространство вероятности <math>G^r_{n,p}</math>).''' Пусть <math>G^r_n</math> – пространство вероятности всех случайных регулярных графов с n вершинами, каждая вершина которых имеет степень r. Пространство вероятности <math>G^r_{n,p}</math> случайных регулярных графов с пропущенными ребрами строится на основании двух последовательных случайных экспериментов: вначале из пространства <math>G^r_n</math> выбирается случайный регулярный граф, а затем каждое ребро случайным и независимым образом удаляется из этого графа с вероятностью f = 1 — p. | ||
Важное свойство связности <math>G^r_{n,p}</math> исследуется путем оценки диапазонов r и f, для которых, с высокой вероятностью, графы <math>G^r_{n,p}</math> (а) являются сильно связными; (б) теряют связность и (в) содержат большой (размера <math>\Theta\ (n)</math>) связный компонент меньшего диаметра. | Важное свойство связности <math>G^r_{n,p}</math> исследуется путем оценки диапазонов r и f, для которых, с высокой вероятностью, графы <math>G^r_{n,p}</math> (а) являются сильно связными; (б) теряют связность и (в) содержат большой (размера <math>\Theta\ (n)</math>) связный компонент меньшего диаметра. | ||
Строка 13: | Строка 13: | ||
== Основные результаты == | == Основные результаты == | ||
Рассмотрим несколько важных свойств связности для случайных регулярных графов с ошибочными | Рассмотрим несколько важных свойств связности для случайных регулярных графов с ошибочными ребрами. Чтобы иметь возможность работать с моделью <math>G^r_{n,p}</math>, в [7] вначале расширяется понятие конфигураций и приводится лемма о переводе между конфигурациями и случайными регулярными графами, введенная Боллобасом [2, 3]; вводится понятие [[случайная конфигурация|случайных конфигураций]], отвечающих за пропущенные ребра, и приводится расширенная лемма о переводе между случайными конфигурациями и случайными регулярными графами с пропущенными ребрами. | ||
Согласно [7], для этой новой модели случайных регулярных графов с пропущенными | Согласно [7], для этой новой модели случайных регулярных графов с пропущенными ребрами верно следующее: | ||
1. Для всех вероятностей ошибки <math>f = 1 - p \le n^{- \epsilon\ }</math> (<math>\epsilon\ \ge \frac{3}{2r}</math> фиксировано) и любого <math>r \ge 3</math> наибольшая часть <math>G^r_{n,p}</math> (иными словами, весь граф за вычетом O(1) вершин) остается связной и, таким образом, связная часть графа почти наверняка не может быть выделена, если только не будут удалены более r вершин. Заметим, что ситуация с диапазоном графа и значением r, несмотря на пропуски, очень напоминает свойства <math>G^r_n</math>, являющегося r-связным для <math>r \ge 3</math>. | 1. Для всех вероятностей ошибки <math>f = 1 - p \le n^{- \epsilon\ }</math> (<math>\epsilon\ \ge \frac{3}{2r}</math> фиксировано) и любого <math>r \ge 3</math> наибольшая часть <math>G^r_{n,p}</math> (иными словами, весь граф за вычетом O(1) вершин) остается связной и, таким образом, связная часть графа почти наверняка не может быть выделена, если только не будут удалены более r вершин. Заметим, что ситуация с диапазоном графа и значением r, несмотря на пропуски, очень напоминает свойства <math>G^r_n</math>, являющегося r-связным для <math>r \ge 3</math>. | ||
Строка 27: | Строка 27: | ||
== Лемма о конфигурации, лемма о переводе == | == Лемма о конфигурации, лемма о переводе == | ||
С технической точки зрения делать какие-либо утверждения о случайных регулярных графах не так просто, как в случае <math>G_{n,p}</math>, в силу стохастических зависимостей от существования | С технической точки зрения делать какие-либо утверждения о случайных регулярных графах не так просто, как в случае <math>G_{n,p}</math>, в силу стохастических зависимостей от существования ребер, связанных с регулярностью. Введенная Боллобасом [2, 3] нотация [[конфигурация|конфигурации]] предназначена для перевода операторов для случайных регулярных графов в операторы для соответствующих конфигураций, которые не содержат зависимостей между ребрами в силу регулярности и с которыми поэтому намного проще работать. | ||
'''Определение 2 (Боллобас, [3])'''. Пусть <math>w = \cup^n_{j=1} w_j</math> – фиксированное множество <math>2m = \sum^n_{j=1} d_j</math> помеченных вершин, где <math>|w_j| = d_j \; </math>. Конфигурация F представляет собой разбиение w на m пар вершин, называемых | '''Определение 2 (Боллобас, [3])'''. Пусть <math>w = \cup^n_{j=1} w_j</math> – фиксированное множество <math>2m = \sum^n_{j=1} d_j</math> помеченных вершин, где <math>|w_j| = d_j \; </math>. Конфигурация F представляет собой разбиение w на m пар вершин, называемых ребрами F. | ||
Пусть дана конфигурация F. Пусть <math>\theta\ (F)</math> – (мульти)граф с множеством вершин V, в котором (i, j) является | Пусть дана конфигурация F. Пусть <math>\theta\ (F)</math> – (мульти)граф с множеством вершин V, в котором (i, j) является ребром в том и только том случае, если в F имеется пара (ребро), имеющая один элемент в <math>w_i \; </math>, а другой – в <math>w_j \; </math>. Заметим, что каждый регулярный граф <math>G \in G^r_n</math> имеет форму <math>\theta\ (F)</math> в точности для <math>(r!)^n \; </math> конфигураций. Однако не каждая конфигурация F с <math>d_j = r \; </math> для всех j соответствует ситуации <math>G \in G^r_n</math>, поскольку F может содержать ребро, полностью находящееся в некотором <math>w_j \; </math>, либо параллельные ребра, связывающие <math>w_i \; </math> и <math>w_j \; </math>. | ||
Строка 44: | Строка 44: | ||
Основная ценность этой леммы заключается в том, что при исследовании случайных регулярных графов вместо рассмотрения множества всех случайных регулярных графов можно исследовать только множество конфигураций, работать с которым намного проще. | Основная ценность этой леммы заключается в том, что при исследовании случайных регулярных графов вместо рассмотрения множества всех случайных регулярных графов можно исследовать только множество конфигураций, работать с которым намного проще. | ||
Для обработки пропущенных | Для обработки пропущенных ребер в [7] вводится следующее расширение понятия конфигураций: | ||
'''Определение 3 (случайные конфигурации).''' Пусть <math>w = \cup^n_{j=1} w_j</math> – фиксированное множество <math>2m = \sum^n_{j=1} d_j</math> помеченных «вершин», где <math>|w_j| = d_j \; </math>. Пусть F – любая конфигурация множества <math>\varphi\ \;</math> . Взяв | '''Определение 3 (случайные конфигурации).''' Пусть <math>w = \cup^n_{j=1} w_j</math> – фиксированное множество <math>2m = \sum^n_{j=1} d_j</math> помеченных «вершин», где <math>|w_j| = d_j \; </math>. Пусть F – любая конфигурация множества <math>\varphi\ \;</math> . Взяв каждое ребро из F, удалить его с вероятностью 1 — p независимым от других образом. Пусть <math>\quad \hat{\phi\ }</math> – новое множество объектов, а <math>\quad \hat{F}</math> – результат эксперимента. <math>\quad \hat{F}</math> будем называть [[случайная конфигурация|случайной конфигурацией]]. | ||
Если ввести для | Если ввести для каждого ребра вероятность p, расширение доказательства леммы 1 (поскольку и в <math>\bar{Q}</math>, и в <math>\hat{Q}</math> каждое ребро имеет одну и ту же вероятность быть удаленным одинаково независимо от других, в результате чего модифицированные пространства соответствуют свойствам <math>Q \; </math> и <math>Q^* \;</math>) приводит к следующему расширению случайных конфигураций. | ||
Строка 59: | Строка 59: | ||
Рассматривается случай вероятности постоянного возникновения пропущенных | Рассматривается случай вероятности постоянного возникновения пропущенных ребер f, представляющего наихудший случай для сохранения связности. В [7] показано, что логарифмических степеней достаточно, чтобы гарантировать, что <math>G^r_{n,p}</math> с высокой вероятностью остается сильно связным, несмотря на постоянное возникновение пропусков ребер. Подробнее об этом говорит следующая теорема. | ||
Строка 75: | Строка 75: | ||
Для доказательства используется расширенная для работы с пропущенными | Для доказательства используется расширенная для работы с пропущенными ребрами техника, предназначенная для недопущения малых разделителей в случайных регулярных графах. | ||
Строка 81: | Строка 81: | ||
Заметим, что вероятность постоянного возникновения пропущенных | Заметим, что вероятность постоянного возникновения пропущенных ребер существенно изменяет структуру связности регулярного графа в случае низких значений степеней. В частности, использование понятия случайных конфигураций [7] позволяет доказать следующую теорему: | ||
Строка 99: | Строка 99: | ||
Для доказательства существования компоненты необходимо вначале доказать существование (с высокой вероятностью) достаточно длинного пути (логарифмической длины) в качестве основы для процесса обхода в ширину, начинающегося с вершин того пути, на основе которого создается компонент. В процессе довольно сложного доказательства используются соображения занятости (столбики диаграмм соответствуют вершинам графов, а круги – | Для доказательства существования компоненты необходимо вначале доказать существование (с высокой вероятностью) достаточно длинного пути (логарифмической длины) в качестве основы для процесса обхода в ширину, начинающегося с вершин того пути, на основе которого создается компонент. В процессе довольно сложного доказательства используются соображения занятости (столбики диаграмм соответствуют вершинам графов, а круги – ребрам); однако упоминаемые в ходе него случайные переменные не являются независимыми, и для использования границ Черноффа-Хеффдинга для концентрации необходимо вначале доказать, что эти случайные переменные, не будучи независимыми, являются отрицательно связанными. Далее при оценке успешности процесса обхода в ширину используется более точный и детальный алгоритм «анализа в среднем». | ||
Построение пути и процесс обхода в ширину могут в совокупности рассматриваться как алгоритм, который (в случае, если не найдено пропусков) позволяет найти огромный связный компонент. Этот алгоритм весьма эффективен, что иллюстрирует следующая теорема. | Построение пути и процесс обхода в ширину могут в совокупности рассматриваться как алгоритм, который (в случае, если не найдено пропусков) позволяет найти огромный связный компонент. Этот алгоритм весьма эффективен, что иллюстрирует следующая теорема. | ||
Строка 114: | Строка 114: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
На основе представленных в [7] идей были проведены и другие интересные исследования. Андреас Гердт [4] продолжил работать над темами, представленными в предыдущей ([8]) версии работы [7], и продемонстрировал следующие результаты: если степень r фиксирована, то <math>p = \frac{1}{r - 1}</math> представляет собой пороговую вероятность существования компонента линейного размера в версии почти любого случайного регулярного графа с пропусками | На основе представленных в [7] идей были проведены и другие интересные исследования. Андреас Гердт [4] продолжил работать над темами, представленными в предыдущей ([8]) версии работы [7], и продемонстрировал следующие результаты: если степень r фиксирована, то <math>p = \frac{1}{r - 1}</math> представляет собой пороговую вероятность существования компонента линейного размера в версии почти любого случайного регулярного графа с пропусками ребер. Фактически он демонстрирует, что в случае, если каждое ребро произвольного графа G с максимальной степенью, ограниченной сверху r, имеется в наличии с вероятностью <math>p = \frac{\lambda\ }{r - 1}</math>, где <math>\lambda\ < 1 \; </math>, тогда версия G с пропусками ребер с высокой вероятностью содержит только компоненты, имеющие не более чем логарифмический размер относительно числа вершин. Из этого следует некоторое понятие оптимальности случайных регулярных графов с пропущенными ребрами. В [5, 10] исследуются важные свойства расширения случайных регулярных графов с пропущенными ребрами; в [9] та же задача рассматривается для случая утолщенных деревьев – распространенного типа топологии сетей. В продолжение этих исследований следовало бы изучить другие комбинаторные свойства случайных регулярных графов с пропущенными ребрами, а также предложить для них эффективные алгоритмы. | ||
== См. также == | == См. также == |