Спільноти у багатошарових мережевих системах
The paper investigates the problem of finding communities in multilayer network systems (MLNS), the detection of which allows for a better understanding the processes of intersystem interactions. To solve this problem, an approach based on the use of concepts of a flow aggr...
Збережено в:
| Дата: | 2023 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України
2023
|
| Теми: | |
| Онлайн доступ: | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/310 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Physico-mathematical modeling and informational technologies |
| Завантажити файл: |  |
Репозитарії
Physico-mathematical modeling and informational technologies| _version_ | 1867479682900819968 |
|---|---|
| author | Polishchuk, Olexandr |
| author_facet | Polishchuk, Olexandr |
| author_institution_txt_mv | [
{
"author": "Olexandr Polishchuk",
"institution": "д.т.н., пров.н.с., Інститут прикладних проблем механіки і математики ім. Я.С. Підстригача НАН України, вул. Наукова, 3б, 79061"
}
] |
| author_sort | Polishchuk, Olexandr |
| baseUrl_str | http://www.fmmit.lviv.ua/index.php/fmmit/oai |
| collection | OJS |
| datestamp_date | 2025-02-21T17:31:10Z |
| description | The paper investigates the problem of finding communities in multilayer network systems (MLNS), the detection of which allows for a better understanding the processes of intersystem interactions. To solve this problem, an approach based on the use of concepts of a flow aggregate-network and a flow core of MLNS, which are defined on the basis of a flow model of intersystem interactions, is proposed. Based on the proposed approach, reliable criteria for community search are formulated and effective algorithms for their detection in multilayer network systems are developed. Indicators of the importance of identified communities in the process of intersystem interactions are determined. It is shown that the proposed methods allow us to distinguish communities in cases where existing numerical and visual approaches are ineffective. |
| first_indexed | 2026-06-09T01:10:09Z |
| format | Article |
| fulltext |
82
УДК 519.711.7:519.816
doi.org/10.15407/fmmit2023.37.082
Спільноти у багатошарових мережевих системах
Олександр Поліщук
д.т.н., пров.н.с., Інститут прикладних проблем механіки і математики ім. Я.С. Підстригача НАН України,
вул. Наукова, 3б, 79061, м. Львів, e-mail: od_polishchuk@ukr.net
У роботі досліджується проблема пошуку спільнот у багатошарових мережевих системах
(БШМС), виявлення яких дозволяє краще зрозуміти процеси міжсистемних взаємодій. Для
вирішення цієї проблеми пропонується підхід, що базується на використанні понять
потокової агрегат-мережі та потокової серцевини БШМС, які визначаються на підставі
потокової моделі міжсистемних взаємодій. На основі запропонованого підходу
сформульовані достовірні критерії пошуку спільнот та розроблені ефективні алгоритми їх
виявлення у багатошарових мережевих системах. Визначені показники важливості
виявлених спільнот у процесі міжсистемних взаємодій. Показано, що пропоновані методи
дають змогу виділяти спільноти у випадках, у яких існуючі числові та візуальні підходи
виявляються непрацездатними.
Ключові слова: мережева система; міжсистемні взаємодії; потокова
модель; агрегат-мережа; потокова серцевина; спільнота
Вступ. Однією з важливих проблем, яка досліджується у теорії складних мереж, є
пошук груп взаємопов’язаних вузлів, ідентифікація яких сприяє кращому розу-
мінню принципів організації структури та процесів функціонування мережевих
систем (МС). У реальних мережевих системах найбільш поширеними групами є
так звані спільноти – підмережі, зв’язки між вузлами яких є чисельнішими та
сильнішими, ніж між ними та іншими вузлами мережі [1]. Прикладами спільнот у
людському соціумі є громадські організації, політичні партії, релігійні конфесії,
національні діаспори, групи в соціальних мережах і т. ін. Чимало спільнот також
існує у біологічних та фізичних системах [2]. Натепер основна увага приділяється
розробленню методів пошуку спільнот, які базуються на структурних ха-
рактеристиках складних мереж (СМ) – найменшому розрізі, ієрархічній класте-
ризації, оцінці модулярності або ентропії, спектральних властивостях мережі то-
що [1]. Не менш важливою та складною є задача пошуку спільнот у БШМС, які
описують процеси міжсистемних взаємодій у надсистемних утвореннях різних
типів [3]. Велика кількість існуючих методів свідчить про неабиякий інтерес до
цієї проблематики та її важливість. Основним недоліком цих методів поряд із об-
числювальною складністю та ресурсоємністю є відсутність достовірного теоре-
тично обгрунтованого критерію того, що визначена будь-яким із них група вузлів
дійсно утворює спільноту. У статті [4] на підставі потокової моделі МС було за-
пропоновано два підходи до пошуку спільнот, які базуються на застосуванні по-
токових характеристик складових мережі. Перший із цих підходів полягав в об-
численні параметрів впливу окремих підсистем мережевої системи, виділених за
принципами впорядкування або підпорядкування, а другий – у використанні
поняття її потокової серцевини. На основі запропонованих підходів були сфор-
mailto:od_polishchuk@ukr.net
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 37, 82-87
83
мульовані достовірні критерії пошуку спільнот та розроблені ефективні алгорит-
ми їх виявлення у складних мережевих системах. Мета цієї статті полягає у роз-
робленні на підставі потокової моделі міжсистемних взаємодій критеріїв та ме-
тодів пошуку спільнот у багатошарових мережевих системах.
1. Структурна та потокова моделі багатошарової мережевої системи
Структурна модель міжсистемних взаємодій описується багатошаровими
мережами (БШМ) та відображається у вигляді [5]
M
km
mk
M
m
m
M kmEGG
1,1
,, , (1)
де ),( mmm EVG визначає структуру m-го мережевого шару БШМ; mV – множи-
на вузлів мережі mG ; mE – множина зв’язків мережі mG , mkE – множина зв’яз-
ків між вузлами множин mV та kV , km , Mkm ,1, , М – кількість шарів (взає-
модіючих систем) БШМ. Множину
M
m m
M VV
1
називатимемо загальною сукупністю вузлів, а множину
M
kmkm mk
M
m m
M EEE
,1,1
загальною сукупністю ребер багатошарової мережі, MN , ML – кількості елеме-
нтів множин
MV та ME відповідно. Зі структурного погляду найбільш загаль-
ним видом БШМ можна вважати частково покриті (ЧП) багатошарові мережі, пе-
ретин множин вузлів окремих шарів яких є непорожнім (рис. 1).
Рис. 1. Приклад структури частково покритої багатошарової мережі
Більшість реально існуючих систем та міжсистемних взаємодій є багатоці-
льовими та багатофункціональними. Це насамперед виражається у мультипото-
ковості таких утворень, тобто забезпеченні руху різних типів потоків. У теорії
складних мереж структура подібних міжсистемних взаємодій відображається так
званими багатовимірними мережами [6]. Структура багатовимірної мережі має
вигляд БШМ, у якій кожний шар відображає структуру системи, що забезпечує
рух заданого типу потоку. Розглянемо у якості прикладу загальну транспортну
систему (ЗТС), яка забезпечує рух двох основних видів потоків – пасажирських
та вантажних, тобто її структуру можна зобразити у вигляді двовимірної мережі.
Особливістю цієї структури, як і більшості багатовимірних мереж, є неможли-
вість переходу потоку з одного шару на інший (перетворення пасажирів у ванта-
жі і навпаки). Для спрощення подальшого аналізу процесу міжсистемних взаємо-
Олександр Поліщук
Спільноти в багатошарових мережевих системах
84
дій у двовимірній ЗТС її можна поділити на дві чотиришарові монопотокові
БШМС, шари якої (залізничний, автомобільний, авіаційний та водний) забезпе-
чує рух лише одного типу потоку – пасажирського або вантажного. Характерною
рисою монопотокових (МП) транспортних БШМС є відмінність носіїв потоків у
кожному шарі (поїзди, автотранспортні засоби, літаки, кораблі). Загалом під час
деталізації структури реальних багатовимірних мереж спочатку доцільно виділя-
ти шари, які забезпечують рух різних типів потоків, а потім кожний із таких мо-
нопотокових шарів зображати у вигляді БШМС кожний шар якої забезпечує рух
цих потоків специфічним носієм. У цій статті ми розглядаємо випадок, коли між-
шарові зв’язки можливі лише між вузлами з однаковими номерами загальної су-
купності вузлів БШМС, тобто кожний вузол може входити до складу кількох
систем та виконувати в них одну функцію але різними способами. Вузли, у яких
можливий перехід потоку з одного шару на інший, називатимемо точками пере-
ходу БШМС.
Потокову модель монопотокової багатошарової мережевої системи зобра-
зимо у вигляді потокової матриці суміжності V
М
(t), елементи якої визначаються
об’ємами потоків, які пройшли ребрами БШМ (1) за період ],[ tTt до поточного
моменту часу Tt :
,
)}(
~
{maxmax
)(
~
)(,)}({)(
,1,,1,
1,1,
tV
tV
tVtVt
sg
lp
NplMgs
km
ijkm
ij
M
mk
N
ji
km
ij
M
M
V
(2)
де
t
Tt
km
ij
km
ij dvtV )()(
~
; ;),()(
),(
m
j
k
i nn
km
ij
km
ij dlttv x
M
mk
N
ji
km
ij
M
txt 1,1, ,)},({),( xρ
і ),( xtkm
ij – щільність потоку, який пересувається ребром ),( m
j
k
i nn БШМС у по-
точний момент часу 0t , ...,3,2,),( nRnn nm
j
k
ix , MmkNji M ,1,,,1, .
Елементи потокової матриці суміжності БШМС визначаються на підставі емпі-
ричних даних про рух потоків її ребрами. Натепер за допомогою сучасних засобів
відбору інформації такі дані достатньо легко отримати для багатьох природних та
переважної більшості створених людиною систем (транспортних, енергетичних,
фінансових, інформаційних тощо) [7]. Матриця V
M
(t) має блочну структуру, у
якій діагональні блоки )(tmm
V описують об’єми руху внутрішньо шарових
потоків у m-му шарі, а позадіагональні блоки )(tkm
V – об’єми руху потоків між
m-тим та k-тим шарами БШМС, km , Mkm ,1, . Для виявлення спільнот у
кожному шарі БШМС можна скористатися одним із методів, розроблених у [4].
2. Потокові агрегат-мережі та серцевини багатошарових мережевих систем
Визначимо поняття потокової агрегат-мережі БШМС, яка, окрім зменшення
розмірності вихідної потокової моделі (2) у М разів, що сприяє подоланню
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 37, 82-87
85
проблеми складності системних досліджень, дозволяє суттєво спрощувати роз-
в’язання багатьох задач дослідження поведінки багатошарових мережевих систем
[5]. Оскільки ми розглядаємо випадок, коли міжшарові зв’язки можливі лише між
вузлами з однаковими номерами загальної сукупності вузлів БШМС, то
структуру потокової агрегат-мережі можна описати у вигляді
),(
1
M
m m
MM
ag EVG
.
Для довільної МП ЧП БШМ матриця суміжності
MN
jiij tft 1,)}({)( F , елемен-
ти якої обчислюються за формулами
MtVtf
M
m
mm
ijij /)()(
1
, ji , MNji ,1, ,
MtVtVtf
M
kmkm
km
ii
mk
iiii 2/))()(()(
,1,
, MNi ,1 , Tt .
повністю визначає динамічну в сенсі залежності від часу зважену мережу, яку
називатимемо потоковою агрегат-мережею цієї багатошарової системи. Елементи
матриці F(t) визначають інтегральні потокові характеристики ребер та точок
переходу багатошарової мережевої системи.
Потокову )(tλ -серцевину монопотокової БШМС можна визначити двома
способами. Перший із них полягає у формуванні матриці суміжності
MN
kmji
mk
ij
M
N
tVtV 1,1,, )}({)( у якій
].1,0[,,,1,,,1,,)(якщо,0
,)(якщо),(
)(,
TtMkmNjitV
tVtV
tV
Mmk
ij
mk
ij
mk
ijmk
ij (3)
Аналогічно [4] матриця )(tV M
із збільшенням значення )(tλ дозволяє бу-
дувати ефективні алгоритми виділення спільнот в окремих шарах БШМС.
Другий спосіб побудови потокової серцевини багатошарової системи поля-
гає у визначенні )(tλag
-серцевини її потокової агрегат-мережі, яка описується
матрицею суміжності
MN
jiij tft 1,)}({)(
F у якій
].1,0[,,,1,,)(,0
,)(),(
)(
TtNjitfякщо
tfякщоtf
tf
M
ij
ijij
ij
Очевидно, що )(tλ -серцевина монопотокової БШМС входить до складу тієї
частини багатошарової системи, на підставі якої побудована )(tλag
-серцевина її
потокової агрегат-мережі.
3. Виділення спільнот у багатошарових мережевих системах
Очевидно, що одним із найбільш об’єктивних показників сили зв’язку між двома
вузлами мережі є об’єми потоків, які проходять через поєднуюче їх ребро
протягом певного періоду часу ],[ tTt , Tt . Тому у якості функціонального
Олександр Поліщук
Спільноти в багатошарових мережевих системах
86
критерію наявності спільноти у потоковій )(tλag -серцевині можна використати
параметр відносної сили взаємозв’язків у ній, який обчислюється за співвідно-
шенням
))((/))(()( tststM
FF
,
у якому параметр
M
N
ji ij Ltfts
M
/)())((
1,
F
визначає усереднений об’єм потоків, які проходять ребром БШМС, а параметр
MN
ji ij Ltfts
M
/)())((
1,
F ,
де
MN ,
ML – кількість вузлів та ребер )(tλag
-серцевини відповідно, визначає
усереднений об’єм потоків ребром )(tλag
-серцевини багатошарової системи.
На рис. 2а)–2в) схематично відображені об’єми потоків, які пройшли реб-
рами 1-го, 2-го та 3-го шарів подібної зображеній на рис.1 тришарової мережевої
системи протягом певного періоду часу (товщина ліній пропорційна об’ємам по-
токів), а рис. 2г) містить зображення потокової агрегат-мережі цієї тришарової
системи. Рис. 2д) та 2е) відображають перші два кроки алгоритму виділення спі-
льнот у потоковій )(tλag
-серцевині БШМС, який полягає в наступному. Прийма-
ємо значення 0λ та поступово його збільшуємо, поки при певному 1λ по-
токова )(tλag
-серцевина не поділиться принаймні на дві незв’язні складові (рис.
2д). Таким чином виділено найбільші за своїм розміром спільноти в системі,
структури яких очевидним чином визначаються із матриці )(1 t
F , Tt . Якщо з
подальшим зростанням при певному 2 виділені на попередньому кроці
спільноти знову поділяються на незв’язні складові, отримуємо підспільноти цих
спільнот (рис. 2е) і т. д. Очевидно, що застосування потокових серцевин агрегат-
мережі БШМС дозволяє не тільки ідентифікувати певну її підсистему, як спіль-
ноту, а здійснювати глобальний пошук усіх спільнот у мережі. Зазначимо також,
що жодний із існуючих чисельних алгоритмів не дає можливості виявити наяв-
ність спільноти у зображеній на рис. 2а-2в найпростішій тришаровій регулярній
мережі.
а) б) в) г) д) е)
Рис. 2. Застосування потокових -серцевин для виділення спільнот у мережі
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 37, 82-87
87
Аналогічно можна здійснювати пошук спільнот у БШМС, використовуючи
визначене формулою (3) поняття її )(tλ -серцевини. Перевагою наведеного вище
алгоритму є можливість виявленням спільнот, які існують у різних шарах багато-
шарової системи та у поєднанні взаємно посилюють одна одну, утворюючи бага-
тошарову групу вузлів, зв’язки між якими є значно сильнішими, ніж у середньо-
му по БШМС.
Висновки. У статті на підставі потокової моделі міжсистемних взаємодій
введено поняття агрегат-мережі багатошарової мережевої системи. Визначено
достовірний кількісний критерій того, що певна група взаємопов’язаних вузлів
агрегат-мережі утворює спільноту. Цей критерій базується на тому, що об’єми
потоків, які рухаються між вузлами спільноти, є суттєво більшими, ніж у сере-
дньому по агрегат-мережі БШМС. На підставі поняття потокової серцевини аг-
регат-мережі побудовано ефективний алгоритм виділення спільнот у багатоша-
ровій системі. Показана надійність роботи цього алгоритму навіть у випадках,
коли складові таких спільнот в окремих шарах БШМС виявляються слабо.
Література
[1] Labatu V., Balasque J. M. Detection and Interpretation of Communities in Complex Networks:
Practical Methods and Application // Computational Social Networks (Eds. by Abraham A.,
Hassanien A. E.). – Springer, London, 2012.
[2] Javed M. A. et al. Community detection in networks: A multidisciplinary review // Journal of
Network and Computer Applications. – 2018. – Vol. 108, P. 87-111.
[3] Huang, X. et al. A survey of community detection methods in multilayer networks // Data Mining
and Knowledge Discovery.– 2021.– Vol. 35.– P. 1–45.
[4] Поліщук О.Д. Потокові підходи до виділення спільнот у складних мережевих системах //
Фізико-математичне моделювання та інформаційні технології.– 2021.– Вип. 33.– С. 122-127.
[5] Polishchuk O. Flow Model of Intersystem Interactions and Influence of Components of Multilayer
Network Systems // ArXiv: 2302.02134 [physics.soc-ph] .– 4 Feb 2023.
[6] Berlingerio M. et al. Multidimensional networks: foundations of structural analysis // World Wide
Web.– 2013.– no. 16.– P. 567–593.
[7] Barabasi A.-L. The architecture of complexity // IEEE Control Systems Magazine.– 2007.– Vol.
27.– no. 4.– P. 33-42.
Communities in multilayer network systems
Olexandr Polishchuk
The paper investigates the problem of finding communities in multilayer network systems (MLNS),
the detection of which allows for a better understanding the processes of intersystem interactions.
To solve this problem, an approach based on the use of concepts of a flow aggregate-network and
a flow core of MLNS, which are defined on the basis of a flow model of intersystem interactions, is
proposed. Based on the proposed approach, reliable criteria for community search are formulated
and effective algorithms for their detection in multilayer network systems are developed. Indicators
of the importance of identified communities in the process of intersystem interactions are
determined. It is shown that the proposed methods allow us to distinguish communities in cases
where existing numerical and visual approaches are ineffective.
Отримано 03.03.23
|
| id | oai:ojs2.www.fmmit.lviv.ua:article-310 |
| institution | Physico-mathematical modeling and informational technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-06-09T01:10:09Z |
| publishDate | 2023 |
| publisher | Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України |
| record_format | ojs |
| resource_txt_mv | wwwfmmitlvivua/10/891df3a9a1e60d4018c60cc5abeca910.pdf |
| spelling | oai:ojs2.www.fmmit.lviv.ua:article-3102025-02-21T17:31:10Z Communities in multilayer network systems Спільноти у багатошарових мережевих системах Polishchuk, Olexandr мережева система; міжсистемні взаємодії; потокова модель; агрегат-мережа; потокова серцевина; спільнота The paper investigates the problem of finding communities in multilayer network systems (MLNS), the detection of which allows for a better understanding the processes of intersystem interactions. To solve this problem, an approach based on the use of concepts of a flow aggregate-network and a flow core of MLNS, which are defined on the basis of a flow model of intersystem interactions, is proposed. Based on the proposed approach, reliable criteria for community search are formulated and effective algorithms for their detection in multilayer network systems are developed. Indicators of the importance of identified communities in the process of intersystem interactions are determined. It is shown that the proposed methods allow us to distinguish communities in cases where existing numerical and visual approaches are ineffective. У роботі досліджується проблема пошуку спільнот у багатошарових мережевих системах (БШМС), виявлення яких дозволяє краще зрозуміти процеси міжсистемних взаємодій. Для вирішення цієї проблеми пропонується підхід, що базується на використанні понять потокової агрегат-мережі та потокової серцевини БШМС, які визначаються на підставі потокової моделі міжсистемних взаємодій. На основі запропонованого підходу сформульовані достовірні критерії пошуку спільнот та розроблені ефективні алгоритми їх виявлення у багатошарових мережевих системах. Визначені показники важливості виявлених спільнот у процесі міжсистемних взаємодій. Показано, що пропоновані методи дають змогу виділяти спільноти у випадках, у яких існуючі числові та візуальні підходи виявляються непрацездатними. Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України 2023-06-27 Article Article application/pdf https://www.fmmit.lviv.ua/index.php/fmmit/article/view/310 PHYSICO-MATHEMATICAL MODELLING AND INFORMATIONAL TECHNOLOGIES; No. 37 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 82-87 ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; № 37 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 82-87 2617-5258 1816-1545 10.15407/fmmit2023.37 uk https://www.fmmit.lviv.ua/index.php/fmmit/article/view/310/279 Авторське право (c) 2023 Олександр Поліщук (Автор) |
| spellingShingle | мережева система міжсистемні взаємодії потокова модель агрегат-мережа потокова серцевина спільнота Polishchuk, Olexandr Спільноти у багатошарових мережевих системах |
| title | Спільноти у багатошарових мережевих системах |
| title_alt | Communities in multilayer network systems |
| title_full | Спільноти у багатошарових мережевих системах |
| title_fullStr | Спільноти у багатошарових мережевих системах |
| title_full_unstemmed | Спільноти у багатошарових мережевих системах |
| title_short | Спільноти у багатошарових мережевих системах |
| title_sort | спільноти у багатошарових мережевих системах |
| topic | мережева система міжсистемні взаємодії потокова модель агрегат-мережа потокова серцевина спільнота |
| topic_facet | мережева система міжсистемні взаємодії потокова модель агрегат-мережа потокова серцевина спільнота |
| url | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/310 |
| work_keys_str_mv | AT polishchukolexandr communitiesinmultilayernetworksystems AT polishchukolexandr spílʹnotiubagatošarovihmereževihsistemah |