Изучение алгоритмов генерации случайных графов, разработка нового алгоритма, его реализация, проведение необходимых испытаний. Разбор методов генерации графов Барабаши-Альберт, Эрдеша-Реньи; графов с нелинейным правилом предпочтительного связывания.
Аннотация к работе
Бакалаврская работа на тему "Разработка и исследование ускоренного алгоритма калибровки моделей больших сетей по коэффициенту кластеризации"С геометрической точки зрения, сеть представляет собой граф, т.е. множество вершин, связанных друг с другом ребрами, поэтому исследование сетей неразрывно связано с теорией графов. Теория случайных графов была представлена Полом Эрдешом и Альфредом Реньи, после того, как Эрдеш открыл, что вероятностные методы часто оказываются полезными в проблемах теории графов. Тем не менее, эта модель активно использовалась в теории перколяции и теории критических явлений, поскольку обладает критическими свойствами, например, существует такая критическая вероятность pc связывания вершин, ниже которой сеть распадается на множество несвязных компонент, а выше - образуется так называемый стягивающий кластер. Причиной этому стал тот факт, что большое значение приобрели сеть интернет и "всемирная паутина", сеть ссылок веб-страниц, имеющая английскую аббревиатуру WWW - World Wide Web. А поскольку стало возможным получить мгновенный снимок сети, например, подсети WWW и представить его в виде графа (каждый отдельный сайт будет вершинной графа, а ссылки между ними будут являться его ребрами), то встал вопрос анализа этих графов.В данном разделе производится обзор существующих методов и по итогам ставится задача исследования. Во втором параграфе производится обзор существующих графовых моделей, вводятся понятия случайных графов Барабаши-Альберт, Эрдеша-Реньи, Уаттса-Строгатца, описаны правила их генерации.Объекты представляются как вершины, или узлы графа, а связи - как дуги, или ребра. Степень связности одной вершины равна количеству ребер присоединенных к этой вершине. Данное значение можно получить, если поделить число ребер в графе на число вершин это же графа и умножить на два, поскольку одно ребро связывает два узла. Коэффициент кластеризации C в общем случае определяется как утроенное отношение среднего числа ND "треугольников" (три вершины, связанные тремя ребрами) в графе к среднему числу NV "вилок" (число путей длины 2). Вероятность pi того, что вершина присоединится к i-ой вершине равна: , (1) где ki-степень i-ой вершины [2].Рассматриваются алгоритм генерации графа БА и ускоренный метод генерации графа с НППС, а также метод сепарабельной реконфигурации. Добавления m ребер являются независимыми событиями, поэтому каждая следующая выбранная для присоединения вершина добавляется в специальный список lst, пока не будут выбраны все m вершин. После выбора всех m вершин (выход из цикла) в граф G "одновременно" добавляются m новых ребер e = (vi, vlst[h]), между добавленной вершиной vi и вершинами из списка vlst[h] (p = 1, …, m). Основная трудоемкость рассмотренного алгоритма заключается в количестве итераций при выборе вершины для присоединения, поскольку в исследуемых сетях таких вершин сотни тысяч. Среднее число итераций при выборе вершин в графе, содержащем n вершин при условии, что степени вершин при их переборе распределены случайно, равно n / 2 [10]. Количество итераций зависит от числа вершин в графе: чем больше граф, тем труднее выполнить данный алгоритм.Модель классического случайного графа (графа Эрдеша-Реньи) плохо воспроизводит некоторые свойства реальных сетей (степени вершин, величину коэффициента кластеризации и длины пути). Графы БА по своим структурным свойствам оказались более адекватными моделями реальных сетей, чем графы Эрдеша-Реньи. Эффект "тесного мира" был обнаружен при исследовании реальных сетей и характеризует собой "правило шести рукопожатий" т.е. перебирая круг своих ближайших знакомых, затем людей, знающих наших ближайших знакомых и т.д. любой человек опосредовано знаком с любым другим человеком в мире. Графы БА имеют небольшую среднюю длину пути между вершинами и таким образом также демонстрируют собой эффект "тесного мира". Единственным методом калибровки графов по коэффициенту кластеризации является метод сепарабельной реконфигурации графа, но этот метод нарушает структуру, сформированную в результате применения графа с НППС.Первый параграф данного раздела посвящен описанию алгоритма генерации графа с НППС с возможностью калибровки по коэффициенту кластеризации. Второй параграф описывает модифицированный алгоритм генерации графа с НППС с возможностью калибровки по коэффициенту кластеризации, представлена схема этого алгоритмаВ классических графах c НППС не оговаривается, к какой именно вершине необходимо присоединить новое ребро при выращивании графа (считается, что это происходит случайно, равновероятно из всех вершин из данного слоя). От способа выбора этой вершины зависят значения структурных характеристик полученного графа, хотя распределение степени связности и остается прежним. Для этого необходимо увеличить количество связанных троек вершин в графе.
План
Содержание
Введение
1. Аналитический обзор и постановка задачи
1.1 Структурные характеристики случайных графов
1.2 Обзор аналогов
2. Разработка алгоритма генератора графа с НППС с возможностью калибровки по коэффициенту кластеризации
2.1 Алгоритм генерации графа с НППС с возможностью калибровки по коэффициенту кластеризации
2.2 Модификация разработанного алгоритма
2.3 Демонстрация работы алгоритма
3. Аспекты программной реализации в системе имитационного моделирования Simbigraph