Министерство образования и науки РФ

ФГБОУ ВПО «Омский государственный технический университет»

Кафедра «Автоматизированные системы обработки информации и управления»

Допускается к защите

Зав. кафедрой АСОИУ,

док-р техн. наук, проф.

__________ А. В. Никонов

«19» июня 2013 г.

Бакалаврская работа

на тему «Разработка и исследование ускоренного алгоритма калибровки моделей больших сетей по коэффициенту кластеризации»

студентки Овчинниковой Елены Владимировны группы ИВТ-449

Пояснительная записка

Шифр работы: БР–02068999–43–08 ПЗ

Направление 230100.62

Научный руководитель,

док-р техн. наук

____________ В.Н. Задорожный

«19» июня 2013 г.

Разработала студентка

____________ Е.В. Овчинникова

«19» июня 2013 г.

Нормоконтролёр:

____________ В.Н. Цыганенко

«19» июня 2013 г.

Омск 2013

Министерство образования и науки РФ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«ОМСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Допускается к защите

Зав. кафедрой АСОИУ,

д-р техн. наук, проф.

__________ А. В. Никонов

«__»__________2013 г.

Задание

на выполнение бакалаврской работы

студентке Овчинниковой Елене Владимировне.

Группа ИВТ-449, факультет информационных технологий и компьютерных систем.

Направление: 230100.62 «Информатика и вычислительная техника»

Код квалификации: .62. Квалификация: бакалавр.

Тема ВКР: «Разработка и исследование ускоренного алгоритма калибровки моделей больших сетей по коэффициенту кластеризации».

Руководитель: Задорожный Владимир Николаевич.

Ученое звание, ученая степень руководителя: доцент, д-р техн. наук.

Срок сдачи полностью оформленной ВКР на кафедру: 27.06.2013 г.

Задание на ВКР (перечень подлежащих разработке разделов).

1. Разработка нового ускоренного алгоритма калибровки по коэффициенту кластеризации.

2. Программная реализация полученного алгоритма в системе моделирования Simbigraph.

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

1. Схема ускоренного алгоритма калибровки моделей больших сетей по коэффициенту кластеризации.

2. Схема модифицированного алгоритма калибровки моделей больших сетей по коэффициенту кластеризации.

3. Схема алгоритма немодифицированного графа предпочтительного связывания.

4. Диаграмма классов проекта.

5. Таблица сравнения диаметра графа и коэффициента кластеризации в различных моделях сети автономных систем.

Научный руководитель: _________________________________ В. Н. Задорожный

Задание приняла к исполнению студентка: _______________ Е. В. Овчинникова

22 Апреля 2013 Аннотация

Объектом выполнения данного исследования является разработка ускоренного алгоритма генерации графов по правилу предпочтительного связывания, позволяющего калибровать графы как по распределению степени вершин, так и по коэффициенту кластеризации. В качестве предмета работы была выбрана разработка ускоренного алгоритма калибровки графов с нелинейным правилом предпочтительного связывания по коэффициенту кластеризации. Целью работы является изучение уже существующие алгоритмов калибровки графов по коэффициенту кластеризации, разработка нового алгоритма, его реализация и проведение необходимых испытаний. В ходе выполнения выпускной квалификационной работы была изучена теория случайных графов, основные модели сетей (графы Барабаши-Альберт, Эрдеша-Реньи, Уотса-Строгатса и др.), разработан алгоритм. Также была изучена программная среда R и были проведены необходимые испытания.

В результате исследования было решено ряд задач. Был разработан ускоренный алгоритм калибровки больших сетей по коэффициенту кластеризации. Полученный алгоритм был реализован на языке Java в среде Eclipse. В конце исследования был проведён анализ экспериментальных данных.