Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически во время прогулок. Доказать или опровергнуть возможность существования такого маршрута никто не мог до 1736 года, когда выдающийся математик Леонард Эйлер не написал письмо своему другу с решением. Ответ был «нельзя». Так и родилась теория графов. Но что будет, если процесс, который описывает граф – случаен? Теория случайных графов находится на стыке теории графов и теории вероятностей. Наука появилась в середине ХХ века, и она сразу же привлекла огромное внимание как со стороны чистых математиков, так и со стороны прикладников. В курсе мы изучим как основы теории случайных графов, так и настоящие ее жемчужины. Мы научимся воспринимать многие сложные системы как "случайные графы". Среди них – интернет, социальные сети (Фейсбука, Вконтакте), биологические, межбанковские сети. Прослушав этот курс, вы проникнетесь чрезвычайно красивой математической теорией и научитесь решать комбинаторные и алгоритмические задачи на случайных графах. Все эти знания позволят нам затем перейти к курсу веб-графов, в котором мы расскажем о самых современных приложениях вероятностно-графовых моделей и конструкций. Для освоения материала будет достаточно математики школьного уровня, базовых знаний комбинаторики и теории вероятностей.
Теорема о появлении гигантской компоненты в случайном графе
Loading...
来自 Moscow Institute of Physics and Technology 的课程
Случайные графы
63 个评分
从本节课中
Две модели случайного графа
Случайный граф Эрдеша-Реньи: биномиальная модель и равномерная модель. Свойства случайного графа. Свойство связности. Пороговая вероятность для свойства связности. Пороговая вероятность для свойства связности. Возникновение гигантской компоненты в случайном графе.
与讲师见面
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Максим Жуковскийпреподаватель
кафедра дискретной математики МФТИ
Дабы завершить эту вводную лекцию,
я хочу сформулировать еще один очень глубокий результат.
Я подумаю, доказывать его в рамках этого курса или нет.
Возможно, частично я его докажу, это очень красиво.
Это очень важный, очень глубокий результат, который характерен,
на самом деле, не только для случайного графа Эрдеша-Реньи, но и для многих других
сложных сетей, о которых мы обязательно поговорим еще в одном нашем курсе.
Вот, это результат о так называемой гигантской компоненте в случайном
графе Эрдеша-Реньи, и это тоже классический результат,
с которого, собственно, началась вся наука.
Он тоже появился, по большому счету, еще в работе классиков, то есть,
Эрдеша и Реньи самих.
Так.
Теорема, соответственно, звучит следующим образом.
Сейчас я ее сформулирую, прокомментирую и потом сопоставлю с утверждением,
которое мы точно докажем.
Значит, пусть вероятность ребра случайного графа
ведет себя вот так, где c — это опять константа.
Заметьте, что конечно, эта вероятность еще во много раз меньше,
нежели та вероятность, которая возникала в предыдущей теореме.
То есть, если говорить о пороге, то там порог был логарифм n / n,
а здесь, здесь это тоже будет порогом,
но этот порог будет еще быстрее стремиться к 0 при n, стремящемся к бесконечности.
Как c / n, где c — константа.
Тогда возможны опять два принципиально различных варианта,
то есть, имеет место фазовый переход.
Пусть c < 1.
Давайте вот в этой теореме немножко несимметрично по отношению к предыдущей
начнем с рассмотрения случая, когда c < 1, то есть,
вероятность ребра случайного графа совсем крошечная.
c ниже вот этого порога 1 / n.
Не c, вернее, а p ниже этого порога, вероятность ребра.
Вот пусть c < 1.
Тогда существует такая константа β, зависящая от c...
Ну, понятно, что если я зафиксировал c и говорю,
что существует β, то понятно, что она, скорее всего, будет зависеть от c.
Вот тогда существует такая константа β, что асимптотически
почти наверное число вершин,
число вершин в каждой связной компоненте,
в каждой связной компоненте,
компоненте случайного графа...
Число вершин в каждой связной
компоненте случайного графа не превосходит β * логарифм n.
То есть, мало того, что граф, конечно, не является связным, это понятно.
Мы сейчас находимся в том режиме, в котором, согласно предыдущей теореме,
граф связным точно не будет.
Ну, вернее, не точно, а с высокой вероятностью,
асимптотически почти наверное.
Вот, но мало того, что он не связен, но те кусочки, на которые он распадается,
компоненты связности, они все крошечные.
Граф разваливается на кучу мелких мирков.
И тем удивительнее утверждение 2.
Оказывается, что едва мы преодолеваем новый порог,
вот этот порог 1 / n, то есть, едва c оказывается строго > 1,
пусть очень-очень близко к 1, возникает прямо противоположная картина.
Ну давайте я ее вот так сформулирую.
Тогда существует β опять же,
зависящая от c Ну, я, конечно, не утверждаю, что та же самая,
что здесь, какая-то, вообще говоря, просто константа, не важно как зависящая от c.
Важно, конечно, из доказательства это будет, было бы видно,
если доказательство привести.
Так вот тогда существует такая константа β, и существует такая константа γ...
Ну, β, понятно, > 0, это, я думаю, все понимают.
А вот γ, тоже зависящая от c, она не просто > 0,
но она находится на интервале от 0 до 1.
Сейчас будет понятно, зачем я написал второе ограничение.
Вот, существуют две константы, β и γ, такие,
что число...
Забыл сказать «асимптотически почти наверное».
Такие, что асимптотически почти наверное число
вершин в самой большой,
в самой большой, естественно,
по числу вершин Число вершин в самой большой компоненте связности,
число вершин в самой большой компоненте связности не меньше, чем γ * n.
И вот ровно здесь видно, зачем я потребовал, чтоб γ было < 1.
Ну разумеется, не может же быть число вершин в связной компоненте строго >,
чем n, это было бы нелепо.
n — это общее количество вершин случайного графа.
Вот, ну а то, что γ строго < 1...
Ну понятно, это связано с тем, что граф-то, все-таки,
скорее всего, не связный, это мы знаем из предыдущей теоремы.
Ну вот, значит, асимптотически почти наверное число вершин в самой большой
компоненте не меньше, чем γ * n.
Прямо противоположная ситуация!
Тут были все компоненты крошечные, а тут откуда-то появилась гигантская компонента,
вот как я говорил, гигантская компонента, у которой порядка n вершин.
А число вершин в каждой из оставшихся,
в каждой из оставшихся связных компонент...
В каждой из оставшихся компонент...
Ну их ясно, сколько-то будет.
Опять не превосходит β логарифм n.
То есть, смотрите,
какой происходит интересный скачок при переходе через порог 1 / n.
До этого порога с высокой вероятность случайный граф распадается на
крошечные мирки логарифмического размера — логарифм гораздо меньше, чем n, правда же?
Но едва c становится > 1, и случайный граф,
он как-бы вроде и разваливается на крошечные мирки,
но помимо этих крошечных мирков, такой вот окраины, появляется гигантская компонента,
она официально называется гигантской, вот эта самая большая компонента.
Появляется гигантская компонента, у которой порядка n вершин.
То есть, за какое-то ничтожное время, за время, покуда p преодолевает вот этот
вот водораздел, у нас куча мелких мирков умудряется
слепиться в одну вот эту вот гигантскую компоненту, в такую, если угодно, империю.
То есть, картина, которую я в этом месте обычно рисую, и на которой,
наверное, я бы эту лекцию-то, на максимально пафосном моменте и завершил,
картина, которая складывается за счет теории случайных графов,
чтобы вот вам просто было понятно, что здесь происходит.
Картина такая: когда...
Давайте я вот так нарисую.
Это вот у нас ось p, условно говоря.
Ну или, если угодно, c.
Ну, не знаю, нет, c здесь не подходит, это я так, зря нарисовал.
Нет, это ось p все-таки.
Так вот, когда у нас есть точка 1 на n,
и мы находимся где-то левее этой точки — c строго < 1 — тогда у нас,
ну если угодно, такой своего рода феодализм развивается.
Феодализм, много отдельных мелких логарифмических компонент,
которые между собой никак не связаны.
Я обычно это характеризую как феодализм.
Вот, но едва мы переваливаем через вот эту вот интересную точку,
через вот этот порог 1 / n, значение p переваливает через этот порог,
и сразу возникает ну понятно что, я уже это слово произнес,
возникает империя, возникает империя.
Но из формулировки теоремы видно, что эта империя — единственная, то есть,
возникает огромная империя, которая вовлекает в себя кучу изначальных вот
этих вот крошечных феодальных кусочков, а вокруг нее по-прежнему феодализм.
Видите, количество вершин в самой большой компоненте порядка n,
но во всех-то остальных не больше, чем логарифм у каждой.
Поэтому империя в этой конструкции только одна.
Но, как мы увидим в каких-нибудь еще наших курсах, это очень расхожее свойство.
Ну и дальше есть еще одна интересная точка, это логарифм n / n, она,
конечно, сильно правее в том смысле, что ln n гораздо больше, конечно,
чем 1, когда n растет.
Вот эта империя растет, ширится, растет, ширится, но по-прежнему у нее какие-то,
какие-то окраины остаются.
И когда мы загадочным образом перескакиваем вот через эту точку, вернее,
перескакиваем-то естественно, а загадочно то, что происходит при этом перескоке.
Империя захватывает все, больше никаких охвостий нету.
Есть только одно огромное такое государство.
Ну, я это обычно характеризую выражением «мировое господство».
Империя захватывает мировое господство.
Вот такая вот картина рисуется случайными графами, я вам доложу.
Ну все, давайте в следующей лекции подоказываем, собственно,
теорему основную, которая про вот этот вот порог, и там будет много очень красивой,
хорошей математики: неравенство Маркова, неравенство Чебышёва,
будем считать там разные математические ожидания с помощью линейности, дисперсию,
естественно, коль скоро неравенство Чебышёва.
Готовьтесь.
