Моделиь Барабаши-Альберт

Для решения многих задач в повседневной жизни достаточно часто используют случайные графы. Случайные графы нашли свое применение в большинстве отраслей современного мира, где требуется смоделировать сложные сети.
«Случайный граф» – это термин, обозначающий вероятностное распределение графов. Случайный граф – это граф, который генерируется в результате некоторого случайного процесса [8].
В данной работе рассмотрена одна активно используемая и хорошо изученная модель – модель Барабаши-Альберт.
Целями данной работы являются рассмотрение теоретического материала о модели Барабаши-Альберта и изучение материала, основанного на статистических данных.
Для достижения этих целей необходимо:
- собрать теоретические сведения о модели Барабаши-Альберта;
- на примере современной всемирно известной социальной сети с использованием статистических данных рассмотреть модель Барабаши-Альберта.

ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ О МОДЕЛИ БАРАБАШИ-АЛЬБЕРТ

Во время зарождения сети Интернет Барабаши Альберт– Ласло (венгерско-американский физик румынского происхождения) [1] и Река Альберт (румынско-венгерский ученый) [11] начали задаваться вопросами: модель описания свойств сети Интернет? Законы подчинения роста интернета?
В 1999 году они предложили модель Барабаши-Альберт для объяснения широкого распространения в технологических, социальных и природных сферах бесмасштабных сетей [10].

Наблюдения Барабаши-Альберт
В работах Л.-А. Барабаши и Р. Альберт описывают те статистики Интернета, которые являются основой науки о росте сети – науки, имеющей глубокие приложения как в собственной интернетской проблематике, так и в многочисленных близких дисциплинах. В реальности большинство сетей имеют схожую «типологию». Под понятием «сеть Интернет» понимаем «веб-граф».
Веб-граф - ориентированный мульти-граф, вершины которого это конкретные структурные единицы в интернете: сайты, владельцы, хосты, страницы и прочее). Вершинами веб-графа для определенности примем сайты, а ребрами, соединяющими вершины веб-графа - ссылки. При этом логично между двумя вершинами проводить столько ребер, сколько ссылок есть между соответствующими сайтами. Ребра считать направленными. Следовательно, веб-граф нацелен и может иметь кратные петли и ребра (ссылки могут переходить с одной страницы сайта на его другую страницу).
Одной из первых моделей веб-графов стала модель Барабаши-Альберт [6].
Существует три основных закономерности в веб-графах, которые выявили в своих исследования Барабаши-Альберт.
Веб-граф – разреженный граф. У него на n-вершинах mn-ребер, m ϵ N, m≥1 - некоторая константа,. Для сопоставления, у полного графа на n-вершинах С_n^2=θ(n^2 )-ребер.
Веб-граф подчиняется феномену «малого мира». Диаметр веб-графа исключительно скромен. В 1999 году его величина составляла 5-7. То есть переходить по ссылкам с одного сайта на другой можно примерно за 5…7 кликов.
Только лишь едва созданные сайты не связаны с внешним по отношению к нем миру.
Проще сказать, что в веб-графе есть громадная компонента, и уже ее диаметр небольшой. Следовательно, веб-граф достаточно специфичен: являясь разреженным, он, тем не менее, тесен.
Веб-графу подчиняется степенному закону, то есть свойственно характерное распределение степеней вершин.
|{v:deg(v)=d}|/n≈c/d^λ ,c=const,λ~2.1
Эмпирическая вероятность того, что вершина веб-графа имеет степень d, оценивается как c⁄d^λ , где λ≈2.1 и c- нормирующий множитель, рассчитываемый из условия «сумма вероятностей =1». Этот факт объединяет Интернет с достаточно большим количеством сетей – биологическими, социальными, транспортными. Все они подчиняются степенному закону, только у каждой из них свой показатель λ [2].
Исследователи Р. Альберт и А.-Л. Барабаши предположили, что в каждый момент времени появляется новый сайт и этот сайт устанавливает фиксированное количество ссылок на своих предшественников. Вероятность, с которой новый сайт поставит ссылку на один из прежних сайтов, пропорциональна числу уже имевшихся ссылок на тот сайт.
На основании своих наблюдений ученые ввели понятие «preferential attachment» (предпочтительное присоединение).