Мережеві структури та системи: ІI. Сердцевини мереж та мультиплексів

The notion of the flow core of the network system is introduced and the functional advantages of its structure in comparison with the core of the complex network are analyzed. It has been shown that the flow cores allow us to construct a much more adequate with functional point of view the models of...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2018
Автори:	Polishchuk, O. D., Yadzhak, M. S.
Формат:	Стаття
Мова:	Українська
Опубліковано:	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2018
Теми:	складна мережа мережева система потік мультиплекс модель серцевина ядро
Онлайн доступ:	https://journal.iasa.kpi.ua/article/view/122262
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	System research and information technologies
Завантажити файл:

Репозитарії

System research and information technologies

_version_	1866302164534558720
author	Polishchuk, O. D. Yadzhak, M. S.
author_facet	Polishchuk, O. D. Yadzhak, M. S.
author_sort	Polishchuk, O. D.
baseUrl_str	http://journal.iasa.kpi.ua/oai
collection	OJS
datestamp_date	2019-01-17T13:31:43Z
description	The notion of the flow core of the network system is introduced and the functional advantages of its structure in comparison with the core of the complex network are analyzed. It has been shown that the flow cores allow us to construct a much more adequate with functional point of view the models of network systems than the cores of complex networks. This is demonstrated on the examples of practically important problems of controllability, observability and synchronization of complex networks. On the base of analysis of the structures of real systems, a generalized definition of the multiplex is proposed and the notion of its kernel is introduced. A few of modeling problems of multiplexes are considered and it is established that the effect of the "small world" in them increases. The flow adjacency matrix for the multiplex system is constructed. On its basis, a few of local and global characteristics of the multiplex system are determined and the properties of its flow core are investigated. Methods of reducing the dimension of models of multiplex systems with simultaneous monitoring of the quantitative measure of maintaining their adequacy are analyzed.
doi_str_mv	10.20535/SRIT.2308-8893.2018.3.04
first_indexed	2025-07-17T10:23:24Z
format	Article
fulltext	 О.Д. Поліщук, М.С. Яджак, 2018 38 ISSN 1681–6048 System Research & Information Technologies, 2018, № 3 TIДC ПРОБЛЕМНО І ФУНКЦІОНАЛЬНО ОРІЄНТОВАНІ КОМП’ЮТЕРНІ СИСТЕМИ ТА МЕРЕЖІ УДК 519.7 DOI: 10.20535/SRIT.2308-8893.2018.3.04 МЕРЕЖЕВІ СТРУКТУРИ ТА СИСТЕМИ: ІІ. СЕРЦЕВИНИ МЕРЕЖ ТА МУЛЬТИПЛЕКСІВ О.Д. ПОЛІЩУК, М.С. ЯДЖАК Анотація. Уведено поняття потокової серцевини мережевої системи та про- аналізовано функціональні переваги її структури порівняно із серцевиною складної мережі. Показано, що потокові серцевини дозволяють будувати знач- но адекватніші з функціонального погляду моделі мережевих систем, ніж сер- цевини складних мереж. Це продемонстровано на прикладі практично важли- вих задач керованості, спостережуваності та синхронізації складних мереж. На підставі аналізу структур реальних систем запропоновано узагальнене визна- чення мультиплексу та введено поняття його ядра. Розглянуто низку задач мо- делювання мультиплексів і встановлено, що ефект «тісного світу» у них поси- люється. Побудовано потокову матрицю суміжності системи мультиплексного типу. На її основі визначено деякі локальні та глобальні характеристики муль- типлекс-системи і досліджено властивості її потокової серцевини. Проаналізо- вано способи зменшення розмірності моделей мультиплекс-систем з одночас- ним відстеженням кількісної міри збереження їх адекватності. Ключові слова: складна мережа, мережева система, потік, мультиплекс, мо- дель, серцевина, ядро. ВСТУП Під час дослідження складних мережевих систем (СМС) виникає проблема розмірності їх моделей. Складні мережі (СМ) можуть налічувати мільйони та мільярди елементів (вузлів і ребер, що їх поєднують) [1]. Кількість проце- сів, які перебігають у системах з такою структурою, є принаймні на порядок більшою [2]. Зазвичай основний спосіб вирішення проблеми розмірності полягає у спрощенні моделі завдяки відкиданню найменш важливих з по- гляду дослідника елементів [3]. Однак у разі такого спрощення вини- кає проблема збереження адекватності моделі. У праці [4] розглянуто один з варіантів зменшення розмірності моделі без утрати її адекватності, який по- лягає у видаленні зі структури системи фіктивних вузлів та зв’язків. Ще один спосіб спрощення моделей СМ — уведення поняття k -серцевини ме- режі [5], тобто найбільшої підмережі вихідної СМ, усі вузли якої мають структурний ступінь не менший за k , та вилученні зі структури мережі вуз- лів зі ступенем, що менший за k [6]. Використання потокових характерис- тик СМС [4] дозволяє ввести поняття потокової серцевини мережевої сис- Мережеві структури та системи: II. Cерцевини мереж та мультиплексів Системні дослідження та інформаційні технології, 2018, № 3 39 теми. Потокові серцевини СМС дають змогу будувати функціонально знач- но адекватніші спрощені моделі мереж, ніж їх k -серцевини. Будь-яка реальна система є відкритою, тобто вона взаємодіє з іншими системами [7]. Одними з різновидів міжсистемних взаємодій є мультиплек- си [8], у яких вузли однієї мережі можуть одночасно бути вузлами багатьох інших мереж. Так, кожна країна є об’єктом (або вузлом) міжнародної полі- тичної, економічної, військової, безпекової, культурної, спортивної співпра- ці і т.ін. Кожне місто країни є вузлом кількох транспортних мереж різних типів, мереж державного та місцевого управління, економічних та фінансо- вих мереж тощо. Кожна людина також є вузлом багатьох мереж (родинної, професійної, соціальної, релігійної і т.ін.). Кожну мережу, яка є складовою мультиплексу, називають шаром. Наведені приклади показують, що між вузлами окремих мережевих шарів існують різні види взаємодій. Ці вза- ємодії можуть мати різну природу, призначення та матеріальний носій. Оскільки кожна мережа є структурою певної мережевої системи [4], то один і той же вузол мультиплексу є елементом багатьох систем і реалізує в них різні функції. Під час дослідження мультиплексів також використовується поняття k -серцевини [9, 10] як поєднання k -серцевин окремих шарів- мереж. Уводимо поняття ядра мультиплексу як структури та потокової сер- цевини мультиплексу як системи взаємодіючих у процесі свого функціону- вання шарів — мережевих систем. Ці поняття дозволяють спрощувати мо- делі системних взаємодій мультиплексного типу. Мета роботи — визначити, наскільки поняття потокової серцевини ме- режі дає змогу спростити дослідження мережевих систем і мультиплекс- систем та зменшити розмірності їх моделей без утрати адекватності. СЕРЦЕВИНИ СКЛАДНИХ МЕРЕЖ ТА МЕРЕЖЕВИХ СИСТЕМ Нехай до складу мережі входить N вузлів. У праці [4] визначено потокову матрицю суміжності мережевої системи N jiijf 1,}{ F за співвідношенням }{max/ ,1, ml Nlm ijij VVf   , ]1,0[ijf , де ijV — об’єм потоку, який проходить із вузла in у вузол jn за проміжок часу ],0[ T , Nji ,1,  . Позначимо N jiijf 1, }{ F , де 2/)( jiijjiij ffff  , ]1,0[ijf , Nji ,1,  . Визначимо потокову  -серцевину СМС як найбільшу підмережу вихідної мережі, для якої усі елементи матриці F мають значення, не менші за  , де ]1,0[ . Невеликий фрагмент реальної автотранспортної мережі великого міста схе- матично зображено на рис. 1, а; цей же фрагмент з відображенням об’ємів руху потоків, величина яких є пропорційною до товщини ліній, — на рис. 1, б, 4-серцевину фрагмента СМ та потокову 0,9-серцевину відповідної складової СМС — на рис.1, в, г. Очевидно, що структури цих серцевин істот- но відрізняються, причому потокова  -серцевина СМС містить значно важ- ливішу інформацію для системних досліджень, ніж k -серцевина її структу- ри. Так, вилучення вузла В зі структурним ступенем 3, який лежить на шляху інтенсивного руху великих об’ємів потоків, призведе до значно біль- О.Д. Поліщук, М.С. Яджак ISSN 1681–6048 System Research & Information Technologies, 2018, № 3 40 ших проблем у функціонуванні транспортної системи (перерозподілу пото- ків альтернативними шляхами), ніж вилучення вузла А зі структурним сту- пенем 4. Зазначимо, що розмірність  -серцевини зі значеннями  , близь- кими до 1, зазвичай значно менша за розмірність k-серцевини з великим значенням k. Вирішення проблеми розмірності моделей великих СМ можна спрости- ти, досліджуючи не всю мережу, а лише її  -серцевину. При цьому, чим більшою є питома вага  -серцевини в системі, тим адекватніший результат дослідження. Можна використовувати різні способи визначення питомої ваги  -серцевини у вихідній мережі, наприклад, рівні покриття  -серцевиною її вузлів та/або зв’язків. Уведемо потокову матрицю суміжності  -серцевини N jiijf 1, , }{    F за співвідношенням        ;якщо,0 ;якщо, * ** , ij ijij ij f ff f , Nji ,1,  . Для визначення питомої ваги  -серцевини використовуватимемо пара- метр  , що визначає відношення об’ємів потоків, які проходять  -серце- виною, до об’ємів потоків, які проходять мережею загалом за період ],0[ T , тобто          N i N j ij N i N j ij ff 1 1 1 1 , . Оскільки основною метою більшості мережевих систем є забезпечення руху певного типу потоків [4], то параметр  кількісно визначає наскільки  -серцевина забезпечує реалізацію цієї мети. Якщо замість моделі всієї сис- теми досліджувати модель її  -серцевини, то значення параметра  мож- на інтерпретувати як міру адекватності цієї моделі. Позначимо через min мінімальне, відмінне від 0, значення ijf , Nji ,1,  . Якщо значення min близьке до 1, то це означає, що потоки рівномірно розподілені мережею, тобто її min -серцевина загалом збігається з вихідною СМ. Чим більше зна- чення  наближене до 1 за значень  , близьких до 1, тим меншою є час- тина СМС, у якій зосереджені основні об’єми потоків. У цьому випадку до- слідження можна зосередити насамперед на цій частині системи (рис. 2). Рис. 1. Фрагмент складної мережі (a), мережевої системи (б), їх 4-серцевини (в) та потокової 0,9-серцевини (г) B A а б в г Мережеві структури та системи: II. Cерцевини мереж та мультиплексів Системні дослідження та інформаційні технології, 2018, № 3 41 Зв’язки мережі впорядковані за ознакою збільшення об’ємів потоків. Лінія 1 відповідає випадку, коли потоки рівномірно розподілені ребрами мережі, лінії 2–4 — випадкам, коли потоки нерівномірно розподілені ребра- ми мережі, зокрема лінія 4 визначає, що основна маса потоків рухається у невеликій підмережі вихідної мережі. Таким чином, виділення та дослідження потокової серцевини CМС по- рівняно з дослідженням усієї мережі дозволяє зменшити розмірність задачі завдяки відкиданню функціонально найменш важливих вузлів та зв’язків, що не призводить до значних збоїв у роботі системи. Унаслідок цього дослі- дження мережі зводиться до аналізу або математичного моделювання най- більш пріоритетних її підструктур. У людському організмі серцево-судинна система включає в себе як основні, так і периферійні вени та артерії. Розрив однієї з основних судин може призвести до швидкого летального кінця. У великому місті перекриття основних автомагістралей може спричинити колапс усієї його транспортної системи. Аварії на магістральних лініях еле- ктропередач під час стихійних лих часто призводили до відключення від електроенергії цілих регіонів країни. Однак це не означає, що зв’язки з ма- лим значенням  можна повністю ігнорувати. Невеликі населені пункти також потрібно забезпечувати продуктами, транспортом, фінансовими, ме- дичними, освітніми та іншими послугами, незважаючи на незначні об’єми потоків. Наприклад, перекриття периферійних судин зумовлює розвиток некротичних явищ в органах людського тіла. У людському соціумі та у фі- зичному світі важливими є слабкі взаємодії, завдяки яким можливе існуван- ня мереж «тісного світу» [11]. Для кожної реальної СМС можна знайти таке значення i , яке поділяє множину всіх зв’язків мережі на підмножини си- льних та слабких взаємодій ( i -серцевину та її доповнення) і досліджувати Рис. 2. Графіки розподілу об’ємів потоків у  -серцевинах мережевих систем: V — об’єм потоків; netV — сумарний об’єм потоків у мережі; FN — кількість зв’язків  -серцевини мережі (кількість ненульових елементів потокової матриці суміжності  -серцевини); FN — сумарна кількість зв’язків мережі (кількість не- нульових елементів потокової матриці суміжності мережі) V Vnet 1 2 3 4 0 NF FN О.Д. Поліщук, М.С. Яджак ISSN 1681–6048 System Research & Information Technologies, 2018, № 3 42 реальний вплив слабких взаємодій на процес функціонування системи. Іте- раційне дослідження потокових серцевин СМС із послідовним зменшенням значення  дозволяє спростити цей процес, зосереджуючись насамперед на найбільш важливих ділянках системи. Інший шлях визначення потокової серцевини СМС полягає у включенні до її структури лише тих вузлів мере- жі, які мають потоковий ступінь не менший за наперед визначене значення [4]. Недоліком такого підходу в окремих випадках є неоднозначність визна- чення зв’язків між вузлами такої серцевини. РОЗМІРНІСТЬ ТА АДЕКВАТНІСТЬ МОДЕЛЕЙ ПОТОКОВИХ СЕРЦЕВИН СКЛАДНИХ МЕРЕЖЕВИХ СИСТЕМ Модель СМС для дослідження найбільш пріоритетних її підсистем можна спрощувати шляхом вилучення не тільки фіктивних та найменш пріоритет- них з функціонального погляду вузлів і зв’язків, які входять до складу ме- режі, але й вузлів-посередників. Найпростішим прикладом вузла- посередника є вузол зі структурним ступенем 2, у якому не відбуваєть- ся відбору або додавання нових об’ємів потоків. Нехай маємо деяку вихідну мережу (рис. 3, а). Тоді, взявши її потокову 0,5-серцевину (рис. 3, б) та 3-серцевину цієї 0,5-серцевини (рис. 3, в), отримуємо підмережу вихідної СМ, яка містить лише ті елементи, які важливі для дослідження системи без вузлів-посередників. Такі структури називатимемо )(k -серцевинами (на рис. 3, в зображено 0,5(3)-серцевину вихідної СМС). Спрощуючи моделі систем, слід враховувати, що оброблення потоку у вузлі-посереднику може бути досить складним процесом [12]. Дестабілізація роботи такого вузла може зупинити рух усіх потоків на шляхах, які проходять через цей вузол. Однак загалом вилучення таких вузлів суттєво зменшує розмірність моделей СМС майже без утрати їх адекватності (17 вузлів та 33 ребра у моделі, зо- браженій на рис. 3, а, та 5 вузлів і 15 ребер у моделі — на рис. 3, в). Залізничну мережу західного регіону України без вузлів-посередників схематично зображено на рис. 4, а. Ця мережа містить 29 вузлів та 62 ребра (загалом у ній 354 вузли). На рис. 4, б зображено 0,7(3)-серцевину цієї сис- теми, яка забезпечує понад 80% усіх перевезень, на рис. 4, в — доповнення до цієї серцевини, яке забезпечує менше ніж 20% перевезень. Зазначимо, що 0,7(3)-серцевина цієї системи є зв’язною мережею, тоді як її доповнення — незв’язною мережею. При цьому розмірність 0,7(3)-серцевини СМС, яка нараховує 4 вузли та 12 зв’язків, є меншою, ніж розмірність її доповнення Рис. 3. Моделі фрагмента СМС та її  - і )(k -серцевин: a — вихідна мережа; б — 0,5-серцевина; в — 0,5(3)-серцевина а б в Мережеві структури та системи: II. Cерцевини мереж та мультиплексів Системні дослідження та інформаційні технології, 2018, № 3 43 (8 вузлів та 27 зв’язків). Подібне явище спостерігається у багатьох природ- них та штучних СМС. Утрата зв’язності  -серцевини зі зростанням значен- ня  дозволяє виділяти із СМС спільноти, рух потоків у яких, тобто сила зв’язку між елементами яких, є значно сильнішою, ніж між іншими складо- вими мережі. Очевидно, що видалення частини  -серцевини СМС з вели- ким значенням  значно більше дестабілізує роботу системи, ніж видалення частини її доповнення. При цьому недосяжність навіть невеликої частини  -серцевини може призвести до невирішуваних проблем (наприклад, втра- ти зв’язності мережі) з пошуку альтернативних шляхів руху потоків (рис. 4, г) [4]. Розмірність моделей СМС відіграє вагому роль у розв’язанні багатьох важливих задач моделювання складних мереж та мережевих систем: керо- ваності, спостережуваності, синхронізації [13–15] тощо. Серед найважливі- ших проблем керованості СМС можна назвати боротьбу з розгортанням так званих каскадних явищ або, навпаки, сприяння цьому процесу [16], спряму- вання потоків по альтернативних шляхах, динамічну синхронізацію руху потоків, швидку адаптацію до зміни графіка руху в системах із повністю або частково впорядкованим рухом, розширення та звуження мережі залежно від стадії її життєвого циклу тощо. Натепер задачі керованості та спостере- жуваності складних мереж обмежуються найпростішими лінійними моде- лями для орієнтованих щільних однорідних мереж [13, 14]. Навіть за допо- могою числових методів установити виконання критерію Калмана вдається лише для лінійних моделей СМ, кількість вузлів яких обмежується кількома десятками [17, 18]. Тому зменшення розмірності задач керованості та спо- стережуваності стає вирішальним для можливого їх розв’язання, яке доціль- но починати з )(k -серцевини СМС з великими значеннями k і  . Так, для наведеного вище прикладу залізничної мережі, до складу якої входить 354 вузли, задачі керованості та спостережуваності розв’язати не вдається. Од- нак для її 0,7(3)-серцевини, яка складається лише з 4 вузлів та 12 зв’язків, розв’язок цих задач знайти досить просто. Ще однією важливою пробле- мою, пов’язаною із задачами керованості та спостережуваності, є визначен- ня таких значень C і O , для яких C -серцевина та/або O -серцевина СМС втрачають свою повну керованість або спостережуваність відповідно. Очевидно, що якщо некерованою (неспостережуваною) є певна )(k - серцевина СМС, то некерованою (неспостережуваною) є і система загалом. а б в г Рис. 4. Фрагмент залізничної мережі та її 3(0,7)-серцевини О.Д. Поліщук, М.С. Яджак ISSN 1681–6048 System Research & Information Technologies, 2018, № 3 44 Аналітичні або геометричні методи розв’язання задач керованості та спостережуваності СМ обмежуються пошуком мінімальної кількості вузлів, управління якими є достатнім для забезпечення повної або часткової керо- ваності мережі, або мінімальної кількості вузлів-сенсорів, які забезпечують її спостережуваність. У праці [13] припускається, що такими СМ можуть керувати вузли з високим структурним ступенем, тобто їх k-серцевини з ве- ликим значенням k. Ці вузли також пропонується розглядати як вузли спо- стереження [14]. Однак з функціонального погляду та самої постановки за- дачі випливає, що як вузли керування доцільно обирати вузли-генератори потоків, а як вузли спостереження — вузли-приймачі потоків. Найпрості- шою ознакою вузла-генератора є переважання об’ємів вихідних потоків над об’ємами вхідних, а вузла-приймача – навпаки. Однак таке визначення є да- леко неоднозначним. Наприклад, у великих металургійних центрах об’єми вхідних потоків (сировини) значно перевищують об’єми вихідних (готової продукції). Подібну ситуацію можна спостерігати у містах-виробниках ви- сокотехнологічної продукції. З огляду на наведене визначення ці вузли є приймачами потоків. Але якщо за ознаку «об’єму потоку» вважати йо- го вартість, то згадані вище вузли стають генераторами потоків. Таким чи- ном, залежно від заданої ознаки об’єму потоку один і той же вузол може бути як генератором, так і приймачем потоків, тобто як вузлом керування, так і вузлом спостереження. Рух потоків у мережі є динамічним процесом і потребує динамічної синхронізації. При цьому синхронізація СМ є необхідною, але не достат- ньою умовою для синхронізації мережевої системи. У відомих моделях синхронізації [19–21] зазвичай використовують сам факт взаємозв’язку між вузлами, який визначається елементами матриці суміжності мережі. Утім не менш важливою для адекватності моделі синхронізації є точність визначен- ня сили цього взаємозв’язку. Потокові характеристики СМС та врахування впорядкованості руху потоків дозволяють удосконалити відомі моделі син- хронізації складних мереж [22]. У таких моделях синхронізація системи за- безпечується синхронізацією об’ємів потоків, які рухаються мережею, а си- ла зв’язку між вузлами набуває предметного змісту. Розповсюдження епідемій зазвичай відбувається на шляхах найбільш інтенсивного пересування великих мас людей, а розповсюдження комп’ютерних вірусів найбільш імовірне на шляхах найбільш інтенсивного інформаційного трафіку. Потокові серцевини СМС з великими значеннями  визначають найбільш імовірні шляхи поширення таких процесів. Тому, ізолюючи певні зони мережі [4], особливу увагу потрібно приділяти саме цим складовим СМС. МУЛЬТИПЛЕКС-СТРУКТУРИ ТА МУЛЬТИПЛЕКС-СИСТЕМИ Мультиплекси є найбільш поширеним видом міжсистемних взаємо- дій. Транспортна система країни — це відомий та зрозумілий приклад муль- типлексу. Окремі мережеві шари цієї структури утворюють транспортні сис- теми різного типу — залізничні, автомобільні, авіаційні, морські та річкові, вузлами яких є окремі населені пункти. Лінгвістичні (мовні) мультиплекси, вузлами яких є окремі особи, утворюють різномовні групи населення Землі. Мережеві структури та системи: II. Cерцевини мереж та мультиплексів Системні дослідження та інформаційні технології, 2018, № 3 45 Мультиплекси соціальних мереж, вузлами яких є окремі їх користувачі, є поєднанням глобальних (Facebook, Twitter, Linkedln, pinterest, Google Plus і т.ін.) та локальних (UkrOpen, ukrface, українці тощо) соціальних мереж. Му- льтиплекси є динамічними структурами. Поява нового виду взаємодій між вузлами мереж, які входять до складу мультиплексу, породжує новий його шар. Навпаки, якщо якийсь вид взаємодій зникає, то зникає і відповідний шар. Часто новий шар та відповідний вид взаємодій розширюють можливо- сті існуючих зв’язків у мультиплексі (стаціонарний та мобільний телефон- ний зв'язок, пошта та E-mail). Отже, у більшості випадків різні мережеві ша- ри мультиплексу мають різний склад вузлів та структуру зв’язків. Тому, узагальнюючи відоме визначення [8], мультиплексом або М-структурою на- зиватимемо поєднання кількох взаємодійних мереж, перетин множин вузлів яких є непорожнім. Ядром мультиплексу називатимемо мережу, яка склада- ється з вузлів та зв’язків, що входять до кожного мережевого шару М-структури (рис. 5 — чорним позначено вузли, які належать ядру мульти- плексу, сірим — вузли, які належать лише частині мережевих шарів). Кож- ний вузол ядра мультиплексу є «точкою переходу» з довільного шару- мережі на будь-який інший шар. Під час дослідження М-структур виникає багато важливих проблем: іс- нування шляху з довільного вузла одного шару у довільний вузол іншого шару, побудова найкоротших шляхів руху через мультиплекс (зміна видів транспорту може суттєво пришвидшити час руху пасажирів та вантажів); пошук альтернативних шляхів через інші мережеві шари під час ізоляції певної зони в окремому мережевому шарі (використання метрополітену у великих містах у разі виникнення заторів на автошляхах) [4]; протидія роз- повсюдженню епідемій, комп’ютерних вірусів тощо, які через мультиплекс- ні взаємодії можуть поширюватися значно швидше, ніж в одному шарі. Зда- тність переходу через вузли ядра з одного мережевого шару на інший і навпаки розширює можливості доступу до вузлів, недосяжних в окремих шарах-мережах, та дозволяє здійснювати зв’язок між незв’язними складо- вими таких шарів. Окремим питанням є явище «тісного світу» у мультипле- ксі, оскільки більшість реальних складних мереж мають цю властивість. Мережі «тісного світу» характеризуються малою середньою довжиною шляху l між вузлами та високим ступенем кластеризації С. Загалом залежно від типу мережі параметр l є обернено пропорційний, а параметр С прямо пропорційний деякій додатній монотонно зростаючій функції від середньої Рис. 5. Фрагмент мультиплексу та його ядра О.Д. Поліщук, М.С. Яджак ISSN 1681–6048 System Research & Information Technologies, 2018, № 3 46 кількості зв’язків вузла мережі [11]. Навіть не вважаючи міжшарові взаємо- дії додатковими зв’язками вузла та відкидаючи дублювальні його зв’язки у тих шарах мультиплексу, до яких він належить, отримуємо більшу середню кількість зв’язків вузла у М-структурі, ніж в окремо взятому шарі. Це озна- чає, що ефект «тісного світу» у мультиплексі лише посилюється. Нехай мультиплекс складається з M шарів-мереж, mS — множина вуз- лів його m-го шару, mN — їх кількість, Mm ,1 ; M m mSS 1 — загальна множина вузлів М-структури і SN — кількість цих вузлів. Різні вузли муль- типлексу зазвичай мають різне значення у М-структурі. В окремому мере- жевому шарі структурний ступінь вузла визначається кількістю його зв’язків з іншими вузлами цього шару. Cтруктурний мультиплексний сту- пінь вузла визначатимемо за кількістю мережевих шарів, до складу яких він входить. Позначимо через M m mM SK 1 множину вузлів ядра мультиплек- су, а через KN — кількість цих вузлів. Питому вагу ядра у m-му шарі ви- значаємо параметром mKm NN / , а питому вагу ядра у мультиплексі — параметром SKM NN / . Очевидно, що параметр m визначає кількісну міру можливості взаємодій m-го шару з іншими шарами М-структури, Mm ,1 , а параметр M – загальну кількісну міру можливості міжшарових взаємодій у мультиплексі. Можна ввести ще ряд інших параметрів мульти- плексу, які визначають структурні особливості його вузлів, мережевих ша- рів і М-структури загалом (переважне приєднання, кластеризація тощо). Кожний мережевий шар мультиплексу відображає структуру певної мережевої системи. Мультиплекс-системою (М-системою) називатимемо сукупність мережевих шарів-систем, структури яких поєднані у М-структуру, які спільно функціонують для забезпечення руху певного типу потоків. Та- ким чином, М-структура породжує М-систему лише у разі можливості пере- ходу потоку з довільного шару мультиплексу на інший і навпаки. Такою мультиплекс-системою є вже згадана вище транспортна система країни, по- токами в якій є пасажири та/або вантажі, М-систему породжує мультиплекс соціальних мереж і т. ін. Носії потоків у різних шарах М-системи можуть бути однотипними, як у соціальних мережах, або різнотипними, як у транс- портному мультиплексі. Як і у випадку мережевих систем [4], процес функціонування М-системи для загальної сукупності вузлів MS можна описати її потоковою матрицею суміжності SN jiijM 1,}{  FF . Блоки M mk km ijij f 1,}{ F , SNji ,1,  , цієї матриці визначаються таким чином. Для випадку ji  блоки M mk km iiii f 1,}{ F є потоковими матрицями суміжності міжшарових взаємодій для і-го вузла загальної сукупності вузлів М-системи, SNi ,1 . Ці блоки є нульовими матрицями, якщо вузол належить лише одному системному ша- ру. Оскільки зв’язки-петлі у М-структурі виключаються, то елементи mm iif , Mm ,1 , матриці iiF також є нульовими. Інші значення km iif дорівнюють об’ємам потоків, які з і-го вузла k-го шару надходять в і-й вузол m-го шару Мережеві структури та системи: II. Cерцевини мереж та мультиплексів Системні дослідження та інформаційні технології, 2018, № 3 47 М-системи за період ],0[ T , Mmk ,1,  , SNi ,1 . Для випадку ji  блоки M mk km ijij f 1,}{ F і jiF є потоковими матрицями суміжності вихідних та вхід- них внутрішньошарових взаємодій для і-го вузла загальної сукупності вуз- лів у різних шарах М-системи відповідно, SNji ,1,  . При цьому, оскільки у М-системі різні вузли різних шарів не взаємодіють, то km ijf =0 для mk  , Mmk ,1,  , тобто матриці ijF і jiF , SNji ,1,  , є діагональними. Елементи mm ijf потокової матриці суміжності m-го системного шару mN ji mm ij m f 1, )( }{ F , Mm ,1 , визначають об’єми потоків, які проходять між вузлами цього шару за період ],0[ T . Як і в разі формування потокової матриці суміжності мере- жевої системи [4], елементи матриці MF нормуються шляхом ділення на максимальне значення об’ємів потоків, які проходять між довільними двома вузлами М-системи за період ],0[ T , тобто ]1,0[km ijf , Mmk ,1,  , SNji ,1,  . Уведемо деякі потокові характеристики, які визначають особливості функціонування складових М-системи. Потоковий ступінь і-го вузла m i у m-му системному шарі визначається об’ємами потоків, які проходять через нього у цьому шарі за період ],0[ T [4], тобто    m N j mm ji mm ij m i Nffm 2)(1   , mNi ,1 , Mm ,1 . Потоковий мультиплексний ступінь і-го вузла i визначається об’ємами потоків, які проходять через нього в інші шари М-системи і у зво- ротному напрямку за період ],0[ T , тобто 2 1 1 / MfM k M m km iii    , ]1,0[i , SNi ,1 . Аналогічно [4] можемо визначити внутрішньошарову та міжшарову функціональну важливість вузлів і зв’язків М-системи, а також рівень їх критичної завантаженості. Для М-системи розглянемо підсистему, структура якої є яд- ром відповідної М-структури. Цю підсистему називатимемо К-системою. Потокова матриця суміжності К-системи KN jiijK 1,}{  FF легко визначається з описаної вище матриці MF . Визначаємо сумарні об’єми потоків MV , які проходять М-системою за період ],0[ T , за співвідношенням        S SN i N j M k M m km ijM fV 1 1 1 1 , а сумарні об’єми потоків KV , які проходять її ядром, — співвідношенням        K KN i N j M k M m km ijK fV 1 1 1 1 . Параметр MKKM VV / визначає питому вагу К-системи у процесі функціонування М-системи або, інакше кажучи, дозволяє відстежувати О.Д. Поліщук, М.С. Яджак ISSN 1681–6048 System Research & Information Technologies, 2018, № 3 48 кількісну міру адекватності моделі К-системи порівняно з моделлю всієї системи. Якщо значення KM близьке до 1, то замість моделі М-системи доцільно досліджувати модель К-системи, зменшуючи при цьому розмір- ність вихідної моделі без істотної втрати її адекватності. Якщо ж значення KM близьке до 0, то можна зробити висновок, що системні шари М-системи слабо взаємодіють, а отже, їх можна досліджувати незалежно, розділяючи вихідну модель на М моделей меншої розмірності. Визначаємо сумарні об’єми потоків mV , які проходять у m-му шарі М-системи за період ],0[ T , за співвідношенням    m mN i N j mm ijm fV 1 1 , а сумарні об’єми потоків mKV , , які проходять у m-му шарі К-системи за пе- ріод ],0[ T :    K KN i N j mm ijmK fV 1 1, , Mm ,1 . Параметр mmKm VV /, визначає питому вагу m-го шару К-системи у процесі функціонування цього шару в межах усієї системи. Зокрема, якщо значення m близьке до 1, то без істотної втрати адекватності можна замість моделі всього системного шару досліджувати модель його проекції на ядро. Якщо ж значення m , Mm ,1 , близьке до 0, то можна зробити висновок, що цей шар бере незначну участь у функціонуванні М-системи і його можна вилучити з її моделі. Сумарні об’єми потоків, які рухаються окремим шаром, є локальною характеристикою цього шару в М-системі. Глобальною характеристикою системного шару можна вважати сумарні об’єми потоків, які проходять че- рез його вузли в інші шари М-системи та у зворотному напрямку. Визначає- мо сумарні об’єми міжшарових потоків m-го шару mIV , за період ],0[ T за співвідношенням    mN i M k mk iimI fV 1 1, , а сумарні об’єми міжшарових потоків IV у М-системі за період ],0[ T :   M m mII VV 1 , . Параметр ImIm VV /, визначає питому вагу m-го шару у проце- сі міжшарових взаємодій М-системи. Якщо значення m близьке до 1, то цей шар є основою в процесі організації міжшарових взаємодій, якщо ж близьке до 0, то його без істотної втрати адекватності можна вилучити з мо- делі М-системи і досліджувати незалежно. Аналогічно на основі потокової матриці суміжності М-системи можемо виділяти шари-генератори та шари-приймачі потоків, визначати рівень пріоритетності для кожного шару внутрішньошарових та/або міжшарових взаємодій, обчислювати силу взаємозв’язку між окремими шарами тощо. Загалом уведені вище параметри дозволяють кількісно оцінювати окремі Мережеві структури та системи: II. Cерцевини мереж та мультиплексів Системні дослідження та інформаційні технології, 2018, № 3 49 складові у процесі функціонування М-системи і суттєво спрощувати її мо- дель. Для визначення особливостей М-структур та систем використано най- простіший метод лінійної агрегації. Для отримання більш точних висновків про питому вагу окремих складових у структурі і процесі функціонування системи та використання їх моделей для спрощення процесу дослідження доцільно враховувати пріоритетність цих складових і застосовувати методи зваженої лінійної, нелінійної або гібридної агрегації [23]. У праці [5] k-серцевина мультиплексу },...,,{ 21 Mkkkk визначається як поєднання mk -серцевин його шарів, Mm ,1 . У кожному системному шарі М-системи можемо визначити його потокову  -серцевину, ]1,0[ . λ -серцевиною М-системи називатимемо сукупність  -серцевин її шарів, пов’язаних міжшаровими потоками, об’єми яких за період ],0[ T є не мен- шими за значення  . Потокова матриця суміжності λ -серцевини М-системи визначається з матриці MF . Очевидно, що структури ядра та λ -серцевини М-системи можуть значно відрізнятися. Потокові характерис- тики λ -серцевини у процесі функціонування М-системи та окремих її шарів (питома вага λ -серцевини у М-системі, питома вага  -серцевини m-го шару у процесі функціонування цього шару в межах всієї системи, питома вага λ -серцевини у процесі міжшарових взаємодій тощо) визначаються ана- логічно до потокових характеристик К-системи і відіграють таку саму роль у спрощенні моделі вихідної системи. Очевидно, що нові вузли М-системи з більшою ймовірністю переважно приєднуються до вузлів ядра, оскільки це дозволяє швидше переходити до інших шарів мультиплексу. Серед вузлів ядра переважне приєднання більш імовірне до вузлів потокової λ -серцевини М-системи. Подальшим способом спрощення моделі М-системи є введення поняття її ),( lkλ -серцевини, тобто такої підсистеми вихідної системи, структурний ступінь вузлів якої є не меншим за значення k, мультиплексний ступінь вуз- лів є не меншим за значення l і елементи потокової матриці суміжності MF є не меншими за значення  , ]1,0[ . Очевидно, що MKMk ),(λ . Від- значимо також, що ),( lkλ -серцевина дозволяє без істотної втрати адекват- ності вилучити з моделі М-системи вузли-посередники та елементи, які бе- руть незначну участь у процесі її функціонування. ВИСНОВКИ Дослідження складних мережевих систем — складна проблема. Це насампе- ред зумовлено проблемою розмірності та адекватності моделей таких сис- тем. Поняття k-серцевини СМ та потокової серцевини СМС дозволяє при- наймні частково вирішити цю проблему, виділяючи найбільш важливі зі структурного та функціонального погляду складові системи. Ці поняття да- ють змогу на порядки зменшувати розмірність моделей реальних СМС, ро- зширюючи можливості розв’язання низки важливих прикладних задач: ке- рованості, спостережуваності, синхронізації тощо. Для мультиплекс-систем, О.Д. Поліщук, М.С. Яджак ISSN 1681–6048 System Research & Information Technologies, 2018, № 3 50 які є значно складнішими утвореннями, ніж СМС, проблема розмірності стає ще більш актуальною. Уведені в роботі поняття ядра та потокової сер- цевини М-системи дозволяють зменшувати розмірність моделі такої систе- ми, розщеплювати її на моделі окремих системних шарів, одночасно відсте- жуючи кількісну міру збереження їх адекватності. ЛІТЕРАТУРА 1. Barabási A.-L. Linked: the new science of networks / A.-L. Barabási, J. Frangos. — New York: Basic Books, 2002. — 280 p. 2. Polishchuk O. Issues of regional development and evaluation problems / O. Polish- chuk, D. Polishchuk, M. Tyutyunnyk, M. Yadzhak // AASCIT Communications. — 2015. — Vol. 2 (4). — P. 115–120. 3. Polishchuk D. Solution of some problems of evaluation of the complex systems / D. Polishchuk, O. Polishchuk, M. Yadzhak // Proc. of the 15th Int. conf. on auto- matic control, 23–26 September 2008. — Odesa: ONMA. — P. 968–976. 4. Поліщук О.Д. Мережеві структури та системи: І. Потокові характеристики складних мереж / О.Д. Поліщук, М.С. Яджак // Системні дослідження та інформаційні технології. — 2018. — № 2. – С. 42–54. 5. Dorogovtsev S.N. k-core organization of complex networks / S.N. Dorogovtsev, A.V. Goltsev, J.F.F. Mendes // Physical review letters. — 2006. — Vol. 96(4). — 040601. DOI: https:// doi.org/10.1103/PhysRevLett.96.040601. 6. Alvarez-Hamelin J.I. k-core decomposition: A tool for the visualization of large scale networks / J.I. Alvarez-Hamelin, L. Dall'Asta, A. Barrat, A. Vespignani // arXiv preprint. — arXiv: 0504107 [cs]. — 28 Apr 2005. — 13 p. 7. Scott W.R. Organizations and organizing: Rational, natural and open systems per- spectives / W.R. Scott, G.F. Davis. — London: Routledge, 2015. — 464 p. 8. Boccaletti S. Structure and Dynamics of Multilayer Networks / S. Boccaletti, G. Bianconi, R. Criado et al. // Physics Reports. — 2014. — Vol. 544(1). — P. 1–122. DOI: https://doi.org/10.1016/j.physrep. 2014.07.001. 9. Corominas-Murtra B. Detection of the elite structure in a virtual multiplex social system by means of a generalised K-core / B. Corominas-Murtra, B. Fuchs, S. Thurner // PloS one. — 2014. — Vol. 9 (12). — e112606. DOI: http://dx.doi.org/10.1371/journal.pone.0112606. 10. Azimi-Tafreshi N. k−core percolation on multiplex networks / N. Azimi-Tafreshi, J. Gómez-Gardeñes, S.N. Dorogovtsev // Physical Review E. — 2014. — Vol. 90. — 032816. DOI: https: //doi.org/10.1103/PhysRevE.90.032816. 11. Головач Ю. Складні мережі / Ю. Головач, О. Олємской, К. фон Фербер та ін. // Журнал фізичних досліджень. — 2006. — 10, №4. — С. 247–289. 12. Поліщук Д.О. Моніторинг потоку транспортних мереж із частково впорядкованим рухом / Д.О. Поліщук, О.Д. Поліщук // ХХІІІ наук.-техн. конф. молодих науковців Фізико-механічного інституту ім. Г.В. Карпенка НАНУ: зб. наук. праць. — 23–25 жовт., 2013. — Львів. — С. 326–329. 13. Liu Y.-Y. Controllability of complex networks / Y.-Y. Liu, J.-J. Slotine, A.- L. Barabaґsi // Nature. — 2011. — Vol. 473. — Р. 167–173. DOI: https://doi.org/10.1038/nature10011. 14. Liu Y.-Y. Observability of complex systems / Y.-Y. Liu, J.J. Slotine, A.L. Barabási // Proc. of the National Academy of Sciences. — 2013. — Vol. 110(7). — P. 2460–2465. DOI: https://doi.org/ 10.1073/pnas.1215508110. 15. Novikov A.V. Oscillatory neural networks based on the Kuramoto model for cluster analysis / A.V. Novikov, E.N. Benderskaya // Pattern Recognition and Image Мережеві структури та системи: II. Cерцевини мереж та мультиплексів Системні дослідження та інформаційні технології, 2018, № 3 51 Analysis. — 2014. — Vol. 24(3). — Р. 365–371. DOI: https://doi.org/10. 1134/S1054661814030146. 16. Buldyrev S.V. Catastrophic cascade of failures in interdependent networks / S.V. Buldyrev, R. Parshani, G. Paul et al. // Nature. — 2010. — Vol. 464(15). — P. 1025–1028. DOI: https://doi.org/10.1038/nature08932. 17. Lombardi A. Controllability analysis of networks / A. Lombardi, M. Hörnquist // Physical Review E. — 2007. — Vol. 75(5). — 056110. DOI: https://doi.org /10.1103/PhysRevE.75. 056110. 18. Sedoglavic A. A probabilistic algorithm to test local algebraic observability in poly- nomial time / A. Sedoglavic // Proc. of the 2001 Intern. Symp. on Symbolic and algebraic computation. — 23–29 July 2001. — P. 309–317. DOI: https://doi.org/10.1145/384101.384143. 19. Gomez-Gardennes J. Paths synchronization on complex networks / J. Gomez- Gardennes, Y. Moreno, A. Arenas // Physical Review Letters. — 2007. — Vol. 98. — 034101. DOI: https:// doi.org/10.1103/PhysRevLett.98.034101. 20. Kuramoto Y. Chemical oscillations waves, and turbulence / Y. Kuramoto. — Berlin: Springer-Verlag, 1984. — 157 p. 21. Daido H. Quasientrainment and slow relaxation in a population of oscillators with random and frustrated interactions / H. Daido // Physical Review Letters. — 1992. — Vol. 73. — P. 1073–1076. DOI: https://doi.org/10.1103/ PhysRevLett.68.1073. 22. Polishchuk O. Flows characteristics and cores of complex network and multiplex type systems / O. Polishchuk // arXiv preprint. — arXiv:1702.02730 [phys- ics.soc-ph]. — 9 Feb 2017. — 22 p. 23. Polishchuk D. Global network structures and problems of aggregative evaluations / D. Polishchuk, O. Polishchuk // International frontier science letters. — 2016. — Vol. 8. — P. 31–45. DOI: http://doi.org/10.18052/www.scipress.com/IFSL.8.31. Надійшла 08.02.2018
id	journaliasakpiua-article-122262
institution	System research and information technologies
keywords_txt_mv	keywords
language	Ukrainian
last_indexed	2025-07-17T10:23:24Z
publishDate	2018
publisher	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
record_format	ojs
resource_txt_mv	journaliasakpiua/24/409ed8d33e141ec52922be63ead9c524.pdf
spelling	journaliasakpiua-article-1222622019-01-17T13:31:43Z Network structures and systems: II. Network and multiplex cores Сетевые структуры и системы: ІI. Сердцевины сетей и мультиплексов Мережеві структури та системи: ІI. Сердцевини мереж та мультиплексів Polishchuk, O. D. Yadzhak, M. S. complex network network system flow multiplex model core kernel сложная сеть сетевая система поток мультиплекс модель сердцевина ядро складна мережа мережева система потік мультиплекс модель серцевина ядро The notion of the flow core of the network system is introduced and the functional advantages of its structure in comparison with the core of the complex network are analyzed. It has been shown that the flow cores allow us to construct a much more adequate with functional point of view the models of network systems than the cores of complex networks. This is demonstrated on the examples of practically important problems of controllability, observability and synchronization of complex networks. On the base of analysis of the structures of real systems, a generalized definition of the multiplex is proposed and the notion of its kernel is introduced. A few of modeling problems of multiplexes are considered and it is established that the effect of the "small world" in them increases. The flow adjacency matrix for the multiplex system is constructed. On its basis, a few of local and global characteristics of the multiplex system are determined and the properties of its flow core are investigated. Methods of reducing the dimension of models of multiplex systems with simultaneous monitoring of the quantitative measure of maintaining their adequacy are analyzed. Введено понятие потоковой сердцевины сетевой системы и проанализированы функциональные преимущества ее структуры сравнительно с сердцевиной сложной сети. Показано, что потоковые сердцевины позволяют строить существенно более адекватные с функциональной точки зрения модели сетевых систем, чем сердцевины сложных сетей. Это продемонстрировано на примере практически важных задач управляемости, наблюдаемости и синхронизации сложных сетей. На основании анализа структур реальных систем предложено обобщенное определение мультиплекса и введено понятие его ядра. Рассмотрен ряд задач моделирования мультиплексов и установлено, что эффект "тесного мира" в них усиливается. Построена потоковая матрица смежности системы мультиплексного типа. На ее основании определены некоторые локальные и глобальные характеристики мультиплекс-системы и исследованы свойства ее потоковой сердцевины. Проанализированы способы уменьшения размерности моделей мультиплекс-систем с одновременным отслеживанием количественной меры сохранения их адекватности. Уведено поняття потокової серцевини мережевої системи та проаналізовано функціональні переваги її структури порівняно із серцевиною складної мережі. Показано, що потокові серцевини дозволяють будувати значно адекватніші з функціонального погляду моделі мережевих систем, ніж серцевини складних мереж. Це продемонстровано на прикладі практично важливих задач керованості, спостережуваності та синхронізації складних мереж. На підставі аналізу структур реальних систем запропоновано узагальнене визначення мультиплексу та введено поняття його ядра. Розглянуто низку задач моделювання мультиплексів і встановлено, що ефект "тісного світу" у них посилюється. Побудовано потокову матрицю суміжності системи мультиплексного типу. На її основі визначено деякі локальні та глобальні характеристики мультиплекс-системи і досліджено властивості її потокової серцевини. Проаналізовано способи зменшення розмірності моделей мультиплекс-систем з одночасним відстеженням кількісної міри збереження їх адекватності. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2018-10-16 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/122262 10.20535/SRIT.2308-8893.2018.3.04 System research and information technologies; No. 3 (2018); 38-51 Системные исследования и информационные технологии; № 3 (2018); 38-51 Системні дослідження та інформаційні технології; № 3 (2018); 38-51 2308-8893 1681-6048 uk https://journal.iasa.kpi.ua/article/view/122262/149277 Copyright (c) 2021 System research and information technologies
spellingShingle	складна мережа мережева система потік мультиплекс модель серцевина ядро Polishchuk, O. D. Yadzhak, M. S. Мережеві структури та системи: ІI. Сердцевини мереж та мультиплексів
title	Мережеві структури та системи: ІI. Сердцевини мереж та мультиплексів
title_alt	Network structures and systems: II. Network and multiplex cores Сетевые структуры и системы: ІI. Сердцевины сетей и мультиплексов
title_full	Мережеві структури та системи: ІI. Сердцевини мереж та мультиплексів
title_fullStr	Мережеві структури та системи: ІI. Сердцевини мереж та мультиплексів
title_full_unstemmed	Мережеві структури та системи: ІI. Сердцевини мереж та мультиплексів
title_short	Мережеві структури та системи: ІI. Сердцевини мереж та мультиплексів
title_sort	мережеві структури та системи: іi. сердцевини мереж та мультиплексів
topic	складна мережа мережева система потік мультиплекс модель серцевина ядро
topic_facet	complex network network system flow multiplex model core kernel сложная сеть сетевая система поток мультиплекс модель сердцевина ядро складна мережа мережева система потік мультиплекс модель серцевина ядро
url	https://journal.iasa.kpi.ua/article/view/122262
work_keys_str_mv	AT polishchukod networkstructuresandsystemsiinetworkandmultiplexcores AT yadzhakms networkstructuresandsystemsiinetworkandmultiplexcores AT polishchukod setevyestrukturyisistemyíiserdcevinysetejimulʹtipleksov AT yadzhakms setevyestrukturyisistemyíiserdcevinysetejimulʹtipleksov AT polishchukod mereževístrukturitasistemiíiserdcevinimerežtamulʹtipleksív AT yadzhakms mereževístrukturitasistemiíiserdcevinimerežtamulʹtipleksív

Мережеві структури та системи: ІI. Сердцевини мереж та мультиплексів

Репозитарії

Схожі ресурси