Регистрация / Вход
Прислать материал

Компьютерное исследование ассортативности безмасштабной сети на примере модели Бакли-Остус

ФИО: Морозов Д.В.

Направление: Информационные технологии (У.М.Н.И.К.)

Научный руководитель: к.ф.-м.н., доц. Шихеева В.В.

Институт: Институт информационных технологий и автоматизированных систем управления

Кафедра: Кафедра Инженерной кибернетики

Академическая группа: ММ-10-1

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

Одной из таких моделей является модель Бакли-Остус, в которой вершины обладают «изначальной привлекательностью»: вероятность того, что старая вершина будет выбрана соседом новой вершины пропорциональна ее входящей степени плюс константе, т.е. «изначальной привлекательности» . Если , то мы просто получаем модель Барабаши-Альберт. При генерации сети с помощью модели Бакли-Остус, граф строится рекуррентно, начиная с – графа с одной петлёй и одной вершиной до графа – с вершинами и рёбрами, путем последовательного добавления одного узла и одной связи случайным образом по следующему закону распределения:

(1)

где – степень узла в графе , – «изначальная привлекательность» узлов.

Затем из графа получаем граф – с вершинами и рёбрами путём стандартной склейки.

Наличие параметра «изначальной привлекательности» узлов в модели Бакли-Остус позволяет строить сети с различными характеристиками.

В настоящей работе ставится задача выявления зависимостей между показателем ассортативности и другими характеристиками сети на примере модели Бакли-Остус.

Ассортативность служит мерой тенденции узлов сети оказаться соединенными с другими узлами с одним и тем же числом связей. Его можно определить как коэффициент Пирса:

(2)

здесь – число связей в сети, а и – число связей у узлов на обоих концах связи. Если узлы с большим числом связей (хабы) связаны друг с другом, то . Если узлы с большим числом связей связаны с узлами с небольшим числом связей, то .

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

Для решения поставленной задачи требуется:

1. Разработать и реализовать алгоритм построения сети на основе модели Бакли-Остус.

2. Провести серию компьютерных экспериментов и получить графики зависимостей стационарных характеристик сети от её коэффициента ассортативности.

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

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

В дальнейшем планируется реализовать алгоритм построения сложной сети на основе модели Бакли-Остус и вычислить зависимости её характеристик от показателя ассортативности. Так же планируется вывести зависимость типов динамических процессов от ассортативности сложной сети.