Статья «Исследование свойств случайных графов и их роль в теории вероятности»

Исследование свойств случайных графов и их роль в теории вероятности

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

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

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

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

Остановимся подробнее на свойствах случайных графов:
Распределение степеней. Степень вершины представляет собой количество рёбер, которые идентичны этой вершине, и в случайных графах степени вершин расположены случайным образом. Так, в модели Эрдёша-Реньи можно увидеть, что степени вершин распределены примерно по биномиальному закону, а вот если значения числа вершин большие, то по закону Пуассона.

Связность. Между любыми двумя вершинами есть путь, это говорит о существовании вероятности, что граф будет связным. При этом вероятность может ощутимо варьироваться в зависимости от того, какова модель случайного графа. К примеру, когда в модели Эрдёша-Реньи увеличивается количество рёбер, растёт и вероятность связности.

Циклы. В случайные графы могут входить циклы, или пути, которые начинаются и завершаются в одной вершине. Количество циклов и их существование зависит от того, какая модель случайного графа, а также от параметров. В качестве примера снова приведём модель Эрдёша-Реньи: если увеличивается количество рёбер, то увеличивается и вероятность содержания больших циклов.

Размер компонентов связности. У компонентов связности в несвязных случайных графах могут быть разные размеры. Так, модель Эрдёша-Реньи имеет порог перколяции, при наличии которого возникает больше компонентов связности.

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

Рассмотрим роль случайных графов с теорией вероятности. Вероятностные методы случайных графы активно используются в комбинаторике, а также в сетевой теории. Работая со случайными графами, учёные активно используют:
Закон больших чисел и ЦПТ, чтобы описать массовые закономерности;
Теорию больших уклонений, чтобы оценить редкие или экстремальные события;
Перколяционную теорию, чтобы проанализировать устойчивость сетей к рандомным или целенаправленным уронам;
Случайные процессы на графах, чтобы изучить распространение информации, эпидемии.

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

Говоря о перколяции и критических явлениях, необходимо отметить, что данная модель исследует процент случайно удалённых рёбер или вершин, при котором сеть уже больше не может быть связной.

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

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

Изучение свойств случайных графов – важная тема, так как она помогает проанализировать и понять то, как же случайность может повлиять на структуру и поведение сложных систем, которые представлены графами.

Список используемых источников:
1. Райгородский А.М. Модели случайных графов. – М.: МЦНМО, 2011 – 136 с.
2. Райгородский А.М., Жуковский М.Е. Случайные графы: модели и предельные характеристики. https://doi.org/10.4213/rm9626