Аналитический обзор моделей случайных графов для моделирования социальных сетей
Автор(ы): Сухов Дмитрий Юрьевич
Рубрика: Технические науки
Журнал: «Евразийский Научный Журнал №3 2017» (март, 2017)
Количество просмотров статьи: 2027
Показать PDF версию Аналитический обзор моделей случайных графов для моделирования социальных сетей
Сухов Дмитрий Юрьевич
студент 1го курса магистратуры
Московского технологического университета
г. Москва
E-mail: strongbad88@mail.ru
Понятие «Социальная сеть» впервые было использовано социологом Джеймсом Барнсом в 1954 году, задолго до появления привычных современному пользователю социальных сетей. Современное понятие этого термина можно описать как круг знакомых человеку лиц, где человек — центр социальной сети, его знакомые — ветви социальной сети, а отношения между людьми — связи.
В современном интернете под социальной сетью понимают площадку, на которой люди могут взаимодействовать друг с другом и объединяться в сообщества по общим интересам или по иным причинам для непосредственного общения между собой.
В настоящее время для построения различных моделей социальных сетей применяют теорию случайных графов. Существует много видов моделей, генерирующих случайные графы, близкие по свойствам к реальным сетям [1].
В своих работах [2], [3], [4] Барабаши и Альберт, а также Х. Джеонг дают описание статистикам интернета, которые послужили основой для создания науки о росте интернета. При ближайшем же рассмотрении можно заметить, что большинство реальных сетей, таких как биологические, транспортные и им подобные, имеют топологию, схожую с интернет сетью.
Для начала определимся с тем, что мы будем понимать под интернет сетью. Сеть интернет — так называемый интернет-граф, вершины которого представляют собой обособленную структурную единицу, расположенную в сети интернет. Интернет-граф формируют добавлением к нему новых вершин, соединяемых ребрами со старыми вершинами. Для большей наглядности возьмем за вершину интернет-графа сайт. В качестве ребер будут выступать ссылки, которые объединяют сайты, при этом ребра разумно считать направленными.
Таким образом, интернет-граф ориентирован, и он может иметь кратные ребра, петли и даже кратные петли (ссылки, расположенные на сайте, могут вести с одной страницы сайта на другую его страницу) [5]. Для подобной модели построения модель графов Эрдеша — Реньи является неактуальной.
Перечислим основные моменты исследования Барабаши — Альберт. Во-первых, интернет-граф — это весьма разреженный граф. У него на t вершинах примерно kt ребер, где k ≥ 1 — некоторая константа. Для сравнения, у полного графа на t вершинах ребер. Во—вторых, — диаметр интернет-графа исключительно скромен.
К концу 20 — началу 21 века, интернет граф имел величину 5 — 7. [4] Это широко известное свойство социальной сети, которое обычно описывают выражением «мир тесен». Оно гласит о том, что любые два человека в мире разделены не более чем пятью уровнями общих знакомых, или же 6 уровнями связей. Аналогичная схема работает и для интернет сайтов: переходя по ссылкам, можно с любого сайта на любой другой перейти за 5 — 7 кликов компьютерной мыши. Но есть и некоторые ограничения. Так, к примеру, только-только созданные сайты могут не иметь непосредственной связи с внешними ресурсами.
В-третьих, у интернет-графа весьма характерное распределение степеней вершин. Эмпирическая вероятность того, что вершина интернет-графа имеет степень d, оценивается как , где λ ≈ 2.1, а c —нормирующий множитель, вычисляемый из условия «сумма вероятностей равна 1». Таким образом, интернет-граф имеет степенное распределение вершин, что, делает его очень похожим на многие реальные сети — все они подчиняются степенному закону, только у каждой из них свой степенной показатель распределения. Такие графы принято называть безмасштабными.
| Критерий | Модель Эрдеша — Реньи | Модель Барабаши — Альберт |
| Разреженность графа | Плотный | Разреженный |
| Диаметр графа | Большой | Малый |
| Распределение степеней вершин графа | Нехарактерное | Характерное |
Таблица 1 — сравнение моделей случайных графов
При изучении выбранных для сравнения критериев можно заключить, что модель Эрдеша — Реньи слабо применима для моделирования интернета и подобных сетей. Если подбором вероятности p можно добиться разреженности и тесноты (хотя и не с теми параметрами), то степенной закон совсем уж не имеет отношения к схеме Бернулли, в рамках которой появляются ребра обычного случайного графа. В модели G (n,p) степень каждой вершины случайного графа биномиальна с параметрами n — 1 и p, и при тех p, которые хоть сколько-нибудь гарантируют разреженность (т.е. при ), указанное биномиальное распределение аппроксимируется пуассоновским, а не степенным. Таким образом, можно заключить, что модель случайных графов Барабаши и Альберта является наиболее подходящей для моделирования социальных сетей.
Список источников
- Райгородский А.М. Математические модели Интернета // Журнал «Квант». 2012. № 4.
- Barabasi L.-A., Albert R. Emergence of scaling in random networks // Science. — 1999. — V. 286. P.
- Barabasi L.-A., Albert R., Jeong H. Scale-free characteristics of random networks: the topology of the world-wide web // Physica. — 2000. — V. A281. — P.
- Albert R., Jeong H., Barab ́asi L.A.Diameter of the world-wide web // Nature. — 1999. — V. 401. P.
- Райгородский А.М. Модели случайных графов и их применение // Тр. МФТИ. 2010. Т. 2, № 4. С.
ИМИТ
Сеть Интернет — это так называемый веб-граф, вершины которого суть какие-либо конкретные структурные единицы в Интернете: речь может идти о страницах, сайтах, хостах, владельцах и пр. Для определенности будем считать, что вершинами веб-графа служат именно сайты. Ребрами же мы будем соединять те вершины, между которыми имеются ссылки. При этом разумно проводить столько ребер между двумя вершинами, сколько есть ссылок между соответствующими сайтами. Более того, ребра естественно считать направленными. Таким образом, веб-граф ориентирован и он может иметь кратные ребра, петли и даже кратные петли (ссылки вполне могут идти с одной страницы данного сайта на другую его страницу).
Веб-граф – это весьма разреженный граф. У него на t вершинах примерно kt ребер, где k – некоторая константа (для сравнения, у полного графа на t вершинах C_t^2 ребер, это порядка t^2).
Однако диаметр веб-графа исключительно скромен. (Напомним, что расстояние между двумя вершинами графа – это количество ребер в кратчайшем реберном пути между ними, а диаметр графа –– это максимум попарных расстояний между его вершинами.)
В 1999 году диаметр Интернета имел величину 5–7. Это хорошо всем известное свойство любой социальной сети, которое принято в обыденной речи характеризовать выражением «мир тесен». Например, говорят о том, что любые два человека в мире «знакомы через 5–6 рукопожатий». Точно так же и сайты: «кликая» по ссылкам, можно с любого сайта на любой другой перейти за 5–7 нажатий клавиши компьютерной мыши. Конечно, тут есть важная оговорка. Некоторые едва появившиеся сайты могут не быть связаны с внешним по отношению к ним миром. Несколько правильнее сказать, что в веб-графе есть гигантская компонента, и уже ее диаметр невелик. Таким образом, веб-граф очень специфичен: будучи разреженным, он, тем не менее, в известном смысле тесен.
По книге А.М.Райгородского «Модели случайных графов»