Ієрархічні мережеві моделі – це ітераційні алгоритми для створення мереж, які здатні одночасно відтворювати унікальні властивості безмасштабної топології та високого рівня кластеризації вузлів. Ці характеристики широко спостерігаються в природі, від біології до мови та деяких соціальних мереж.
Концепція
Ієрархічна мережева модель є частиною сімейства безмасштабних моделей, що мають їхню головну властивість мати пропорційно більше хабів серед вузлів, ніж при випадковій генерації. Однак вона суттєво відрізняється від інших подібних моделей (Барабаші-Альберт, Воттса-Строгаца) розподілом коефіцієнтів кластеризації вузлів: оскільки інші моделі передбачають постійний коефіцієнт кластеризації як функцію ступеня вузла, в ієрархічних моделях очікується, що вузли з більшою кількістю зв'язків матимуть нижчий коефіцієнт кластеризації.
Більше того, хоча модель Барабаші-Альберта передбачає зменшення середнього коефіцієнта кластеризації зі збільшенням кількості вузлів, у випадку ієрархічних моделей немає зв'язку між розміром мережі та її середнім коефіцієнтом кластеризації.
Розробка ієрархічних мережевих моделей була головним чином мотивована невдачею інших безмасштабних моделей в об'єднанні безмасштабної топології та високого рівня кластеризації в одну єдину модель. Оскільки кілька реальних мереж (метаболічні мережі, мережа взаємодії білків, Всесвітнє павутиння або деякі соціальні мережі) демонструють такі властивості, були введені різні ієрархічні топології, щоб врахувати ці різні характеристики.
Алгоритм Ієрархічні мережеві моделі зазвичай будуються ітеративно шляхом реплікації початкового кластера мережі відповідно до певного правила. Наприклад, розглянемо початкову мережу, що складається з п’яти повністю з’єднаних вузлів (N=5). На наступному кроці створюються чотири копії цього кластера, після чого периферійні вузли кожної копії з’єднуються з центральним вузлом початкового кластера (N=25). Цей процес можна повторювати необмежену кількість разів. У такому разі після k ітерацій кількість вузлів у мережі визначається як N=5k+1.
Звичайно, у науковій літературі запропоновано кілька різних способів побудови ієрархічних систем. Такі системи зазвичай відрізняються структурою початкового кластера, а також ступенем розширення, який часто називають коефіцієнтом реплікації моделі.
Властивості
Розподіл ступенів Будучи частиною сімейства безмасштабних моделей, розподіл ступенів ієрархічної мережевої моделі відповідає степеневому закону, що означає, що випадково вибраний вузол у мережі має k ребер з ймовірністю
де c – константа, а γ – показник степеня. У більшості реальних мереж, що демонструють безмасштабні властивості, γ лежить в інтервалі [2,3].
Як конкретний результат для ієрархічних моделей було показано, що показник степеня функції розподілу можна обчислити як
де M представляє коефіцієнт реплікації моделі.
Коефіцієнт кластеризації На відміну від інших безмасштабних моделей ( Ердешева-Реньї, Барабаші-Альберта, Воттса-Строгатца), де коефіцієнт кластеризації не залежить від ступеня конкретного вузла, в ієрархічних мережах коефіцієнт кластеризації можна виразити як функцію ступеня наступним чином:
Аналітично було показано, що в детермінованих безмасштабних мережах показник степеня β набуває значення 1.
Приклади
Акторська мережа Згідно з базою даних акторів, доступною на сайті www.IMDb.com, мережа визначається голлівудськими акторами, які пов'язані один з одним, якщо вони обидва знімалися в одному фільмі, що призводить до набору даних з 392 340 вузлів та 15 347 957 ребер. Як показали попередні дослідження, ця мережа демонструє властивості безмасштабності щонайменше для високих значень k. Крім того, коефіцієнти кластеризації, ймовірно, відповідають необхідному закону масштабування з параметром −1, що свідчить про ієрархічну топологію мережі. Інтуїтивно зрозуміло, що актори, які беруть участь в одному фільмі, за визначенням мають коефіцієнт кластеризації, рівний одиниці, тоді як актори, які знімаються у кількох фільмах, менш імовірно працюватимуть з тією самою знімальною групою. У результаті це загалом призводить до зменшення коефіцієнта кластеризації зі збільшенням кількості колег по знімальному майданчику.
Мовна мережа Слова можна розглядати як мережу, якщо вказати критерії зв'язку між ними. Визначаючи зв'язки як зовнішній вигляд як синонім у словнику Merriam-Webster, було побудовано семантичну мережу з 182 853 вузлів з 317 658 ребрами. Як виявилося, отримана мережа слів дійсно відповідає степеневому закону у своєму розподілі ступенів, тоді як розподіл коефіцієнта кластеризації вказує на те, що базова мережа відповідає ієрархічній структурі з γ = 3,25 та β = 1.
Мережа веб-сторінок Шляхом відображення домену www.nd.edu було отримано мережу, що містить 325 729 вузлів і 1 497 135 ребер, у якій розподіл степенів відповідав степеневому закону з γout=2.45 та γin=2.1 для вихідних і вхідних степенів відповідно. Докази наявності степеневого закону масштабування в розподілі коефіцієнтів кластеризації є значно слабшими, ніж у попередніх випадках, хоча чітко простежується тенденція до зниження розподілу C(k). Це вказує на те, що зі збільшенням кількості посилань, пов’язаних із доменом, пов’язані з ним веб-сторінки стають менш взаємопов’язаними.
Доменна мережа Доменна мережа, тобто Інтернет на рівні автономної системи (AS), де адміністративні домени вважаються з'єднаними у випадку наявності маршрутизатора, який їх з'єднує, була виявлена як така, що містить 65 520 вузлів та 24 412 з'єднань між ними та демонструє властивості безмасштабної мережі. Розподіл вибірки коефіцієнтів кластеризації був апроксимований функцією масштабування C(k)~k −0,75 , показник якої (в абсолютному вираженні) дещо менший за теоретичний параметр для детермінованих безмасштабних мереж.
Посилання