Еволюційні мережі – це мережі, що змінюються з часом. Вони є природним розширенням мережевої науки, оскільки майже всі реальні мережі змінюються з часом — шляхом додавання або видалення вершин і зв’язків. Часто ці процеси відбуваються одночасно, наприклад у соціальних мережах, де люди з часом набувають і втрачають друзів, створюючи та руйнуючи зв’язки, а також приєднуються до нових соціальних мереж або залишають наявні, тим самим змінюючи структуру вузлів у мережі. Концепції еволюційних мереж ґрунтуються на вже сформованій теорії мереж і наразі застосовуються в дослідженнях мереж у багатьох різних галузях.

Передумови теорії мереж Вивчення мереж бере свій початок від розвитку теорії графів, яку вперше проаналізував Леонард Ейлер у 1736 році, коли він написав відому статтю « Сім мостів Кенігсберга» . Ймовірнісна теорія мереж потім розвивалася за допомогою восьми відомих статей, присвячених вивчення випадкових графів, написаних Паулем Ердешем та Альфредом Реньї. Модель Ердеша-Реньї (ER) припускає, що граф складається з N позначених вузлів, де кожна пара вузлів з'єднана заданою ймовірністю p.

Хоча простота моделі ER допомогла їй знайти багато застосувань, вона неточно описує багато реальних мереж. Модель ER не генерує локальну кластеризацію та тріадні замикання так часто, як вони зустрічаються в реальних мережах. Тому була запропонована модель Воттса — Строгаца, за якою мережа будується як регулярна кільцева решітка, а потім вузли перемонтовуються відповідно до певної ймовірності β. Це створює локально кластеризовану мережу та різко зменшує середню довжину шляху, створюючи мережі, які представляють собою феномен малого світу, що спостерігається в багатьох реальних мережах.

Незважаючи на це досягнення, ні моделі ER, ні моделі Воттса та Строгаца не враховують формулювання хабів, яке спостерігається в багатьох реальних мережах. Розподіл ступенів у моделі ER відповідає розподілу Пуассона, тоді як модель Воттса та Строгаца створює графіки, однорідні за ступенем . Багато мереж натомість не масштабуються, що означає, що їхній розподіл ступенів відповідає степеневому закону виду:

Цей степеневий показник у багатьох реальних мережах виявляється приблизно рівним 3, однак він не є універсальною сталою величиною і може змінюватися залежно від параметрів конкретної мережі.

Перша модель еволюційної мережі – безмасштабні мережі Модель Барабаші-Альберта (BA) була першою широко прийнятою моделлю для створення безмасштабних мереж. Цього було досягнуто шляхом включення переважного приєднання та зростання, де вузли додаються до мережі з часом і з більшою ймовірністю пов'язуються з іншими вузлами з високим розподілом ступенів. Модель BA вперше була застосована до розподілу ступенів в Інтернеті, де обидва ці ефекти можна чітко спостерігати. Нові веб-сторінки з’являються з часом, і кожна нова сторінка з більшою ймовірністю формує зв’язки з добре відомими хабами, такими як Google, які мають високий ступінь, ніж з вузлами з невеликою кількістю посилань. Формально цей механізм переважного приєднання записується так:

Доповнення до моделі BA Модель BA була першою моделлю, яка вивела топологію мережі з механізму її формування, де вузли та зв’язки додаються з плином часу. Водночас модель ґрунтується лише на мінімальних припущеннях, необхідних для виникнення безмасштабної мережі, а саме — на лінійному зростанні та лінійному механізмі переважного приєднання. Ця мінімальна модель не враховує варіації форми розподілу ступенів, варіації показника ступеня або коефіцієнта кластеризації, незалежного від розміру. Тому оригінальна модель з того часу була модифікована щоб повніше охопити властивості мереж, що розвиваються, шляхом введення кількох нових властивостей.

Фітнес Одна з проблем моделі BA полягає в тому, що розподіл ступенів кожного вузла відчуває сильний позитивний зворотний зв'язок, завдяки якому найдавніші вузли з високим розподілом ступенів продовжують домінувати в мережі необмежений час. Однак це можна пом'якшити, ввівши придатність для кожного вузла, яка змінює ймовірність створення нових зв'язків з цим вузлом або навіть видалення зв'язків з цим вузломAlbert R. and Barabási A.-L., "Statistical mechanics of complex networks", Reviews of Modern Physics 74, 47 (2002).

Щоб зберегти механізм переважного приєднання з моделі BA, ця «придатність» множиться на фактор переважного приєднання, що базується на розподілі ступенів, утворюючи таким чином справжню ймовірність формування зв’язку з вузлом i.

Де – це придатність, яка також може залежати від часу. Може відбуватися зниження придатності з часом, що може бути формалізовано за допомогою

де збільшується з

Видалення вузлів та перепідключення з'єднань Подальші ускладнення пов’язані з тим, що вузли можуть бути вилучені з мережі з певною ймовірністю. Крім того, наявні зв’язки можуть руйнуватися, а також можуть утворюватися нові зв’язки між вже існуючими вузлами. Ймовірності цих процесів можуть залежати від часу, а також бути пов’язаними з придатністю вузла. Цим подіям можна зіставити ймовірності, аналізуючи характеристики розглядуваної мережі з метою побудови моделі з еквівалентними властивостями. Таке зростання реалізується через одну з таких дій, що відбуваються на кожному часовому кроці:

Ймовірність p: додати внутрішній зв’язок.

Ймовірність q: видалити зв’язок.

Ймовірність r: видалити вузол.

Ймовірність 1−p−q−r: додати вузол.

Інші способи характеристики еволюційних мереж Окрім моделей еволюційних мереж як описано вище, можуть бути випадки, коли інші методи є більш корисними або зручними для характеристики певних властивостей мереж, що розвиваються.

Збіжність до рівноважних станів У мережевих системах із конкурентним прийняттям рішень теорія ігор часто використовується для моделювання динаміки системи, а збіжність до рівноваги може розглядатися як рушійна сила топологічної еволюції. Наприклад, Кастуріратна та Піравінан показали, що за наявності різних рівнів раціональності в індивідів системи підвищення загальної раціональності може виступати еволюційним механізмом формування безмасштабних мереж. Вони продемонстрували це, застосувавши еволюційний тиск до початково випадкової мережі, що моделює низку класичних ігор, унаслідок чого мережа збігається до рівноваги Неша і водночас перебудовується. У процесі такої еволюції мережі стають дедалі більш безмасштабними.

Розгляд еволюційних мережі як послідовні знімки статичної мережі Найпоширеніший спосіб розглядати мережі, що розвиваються, – це розглядати їх як послідовні статичні мережі. Це можна концептуалізувати як окремі нерухомі зображення, що складають кінофільм. Існує багато простих параметрів для опису статичної мережі (кількість вузлів, ребер, довжина шляху, зв'язані компоненти) або для опису конкретних вузлів у графі, таких як кількість посилань або коефіцієнт кластеризації. Ці властивості потім можна окремо вивчати як часовий ряд за допомогою понять обробки сигналів. Наприклад, ми можемо відстежувати кількість посилань, встановлених із сервером за хвилину, переглядаючи послідовні знімки мережі та підраховуючи ці посилання в кожному знімку.

На жаль, аналогія з кінофільмом також підкреслює ключову складність такого підходу: часові кроки зазвичай не задаються самою мережею і є довільними. Використання дуже малих інтервалів між знімками зберігає високу роздільну здатність, але може приховувати ширші тенденції, які проявляються лише на довших часових масштабах. Навпаки, збільшення часових інтервалів призводить до втрати впорядкованості подій усередині кожного знімка. Тому визначення адекватної часової шкали для поділу еволюції мережі на статичні стани є нетривіальним завданням.

Визначення динамічних властивостей Може бути важливим розглянути властивості, які неможливо безпосередньо спостерігати, розглядаючи мережі, що розвиваються, як послідовність знімків, такі як тривалість контактів між вузлами Можна визначити інші подібні властивості, а потім натомість можна відстежувати ці властивості протягом еволюції мережі та візуалізувати їх безпосередньо.

Ще однією проблемою використання послідовних знімків є те, що навіть незначні зміни в топології мережі можуть суттєво впливати на результати алгоритмів, призначених для виявлення спільнот. У зв’язку з цим виникає потреба у використанні некласичного означення спільнот, яке дозволяє відстежувати їхню еволюцію за допомогою набору правил, зокрема народження, зникнення, злиття, поділу, зростання та скорочення.

Застосування

Майже всі мережі реального світу є еволюційними, оскільки формуються та змінюються з часом. Змінюючи відповідні ймовірності, описані вище, розширену модель BA можна використовувати для побудови мереж, властивості яких майже повністю відповідають характеристикам багатьох реальних мереж. Більше того, концепція безмасштабних мереж показує нам, що еволюція в часі є необхідною частиною розуміння властивостей мережі, і що важко моделювати існуючу мережу як таку, що була створена миттєво. Реальні мережі, що розвиваються, які зараз вивчаються, включають соціальні мережі, комунікаційні мережі, Інтернет, мережу кіноакторів, Всесвітню павутину та транспортні мережі .

Додаткова література

«Розуміння науки про мережі», https://web.archive.org/web/20110718151116/http://www.zangani.com/blog/2007-1030-networkingscience «Зв’язані: Нова наука про мережі», А.-Л. Барабасі, видавництво «Персей», Кембридж.

Посилання