Тези Концепції дослідження складних випадкових мереж

« Назад

На практиці існує досить багато проблем, при розв’язанні яких треба побудувати складні системи за допомогою певного впорядкування їхніх елементів. Високий рівень абстракції та узагальнення дає змогу використовувати при цьому типові алгоритми теорії графів. Ці алгоритми можна застосовувати для розв’язування зовні несхожих задач, пов’язаних, наприклад, з транспортними й комп’ютерними мережами, будівельним проектуванням, молекулярним моделюванням та ін. При вивченні мереж зі складною топологією й невідомими, неочевидними (випадковими) принципами організації можна застосовувати теорію випадкових графів [1].

Мережами, які мають випадкові принципи побудови, є, наприклад, мережа Інтернет — складна система маршрутизаторів і комп’ютерів, з’єднаних різними фізичними й бездротовими зв’язками; www — віртуальна мережа веб-сторінок, з’єднаних гіперпосиланнями.

При поданні складних випадкових мереж основними є концепції “малих світів”, кластерності й розподілу степенів.

Відповідно до концепції “малих світів” у більшості великих складних випадкових мереж існує порівняно короткий шлях між двома будь-якими вершинами. У загальному випадку середня відстань між двома вершинами у випадковому графі дорівнює логарифмові кількості його вершин. Так, речовини в клітині, як правило, відділені трьома хімічними реакціями, після проведення розрахунків фірма Microsoft підтвердила, що практично між будь-якими двома громадянами США існує ланцюжок знайомств у середньому довжиною 6, між акторами в Голівуді є по 3 співробітники в ланцюжку знайомих. Мережі Інтернет і www також підпорядковуються законові “малих світів”.

Кластерність передбачає розбиття графа на окремі зв’язані, але не ізольовані від інших підграфи. Так, загальною властивістю соціальних мереж є те, що існують групи (кластери) друзів і знайомих. Властивість кластерності також мають Інтернет і www. Тенденція до розбиття на кластери визначається коефіцієнтом кластерності. Загальний коефіцієнт кластерності мережі можна знайти як суму коефіцієнтів окремих вершин.

Концепція розподілу степенів базується на тому, що не всі вершини мережі мають однаковий степінь (кількість ребер). Розподіл степенів вершин характеризується функцією p(k), яка визначає ймовірність того, що випадково вибрана вершина буде мати саме степінь k. Прикладом мережі, яка характеризується двома функціями розподілу, є орієнтована мережа www (має вихідні й вхідні гіперпосилання). У випадковому графі ребра розподіляються випадково, тому більша частина вершин має приблизно однаковий степінь, близький до середнього степеня  мережі. Такий розподіл є розподілом Пуассона. Останнім часом емпіричні дослідження показали, що для більшості реальних мереж, наприклад, для Інтернету і www, розподіл степенів значно відрізняється від розподілу Пуассона (це мережі без масштабування), і це привело до появи різних моделей без масштабування.

Застосування теорії випадкових графів при дослідженні великих реальних мереж зі складною структурою дає можливість звести розв’язання складної задачі до ряду простіших задач.