Аналіз кластерної структури Інтернет-мереж на основі випадкових матриць

Основна увага надається оцінці оптимальної кількості кластерів для системи, що задається матрицею суміжності A з N вузлами при N→∞ . Розглянуто асимптотичний розподіл власних значень стохастичної випадкової матриці без умов незалежності елементів, спектр якої можна розкласти на регулярну частину та...

Full description

Saved in:

Bibliographic Details
Published in:	Проблемы управления и информатики
Date:	2022
Main Authors:	Кириченко, О.Л., Малик, І.В, Остапов, С.Е.
Format:	Article
Language:	Ukrainian
Published:	Інститут кібернетики ім. В.М. Глушкова НАН України 2022
Subjects:	Стохастичні системи, нечіткі множини
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/210862
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Аналіз кластерної структури Інтернет-мереж на основі випадкових матриць / О.Л. Кириченко, І.В. Малик, С.Е. Остапов // Проблеми керування та інформатики. — 2022. — № 1. — С. 37-46. — Бібліогр.: 12 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1859460046351499264
author	Кириченко, О.Л. Малик, І.В Остапов, С.Е.
author_facet	Кириченко, О.Л. Малик, І.В Остапов, С.Е.
citation_txt	Аналіз кластерної структури Інтернет-мереж на основі випадкових матриць / О.Л. Кириченко, І.В. Малик, С.Е. Остапов // Проблеми керування та інформатики. — 2022. — № 1. — С. 37-46. — Бібліогр.: 12 назв. — укр.
collection	DSpace DC
container_title	Проблемы управления и информатики
description	Основна увага надається оцінці оптимальної кількості кластерів для системи, що задається матрицею суміжності A з N вузлами при N→∞ . Розглянуто асимптотичний розподіл власних значень стохастичної випадкової матриці без умов незалежності елементів, спектр якої можна розкласти на регулярну частину та викиди. На основі припущень про однотипність зв’язків у кластері зроблено висновок про оптимальну кількість кластерів для різних прикладних задач. Проведено моделювання мережі зв’язків, що розподілені за законом Пуассона, та знайдено оптимальну кількість кластерів. Результати моделювання вказують на високу точність визначення оптимальної кількості кластерів. У основній теоремі важливим є припущення про існування моменту вище другого для кожного елементу матриці A. Проте, з урахуванням нормалізації, цю умову можна послабити до існування математичного сподівання матриці. Дане послаблення умов збіжності дає можливість використання доведеного твердження на ширший клас прикладних задач, де наявність скінченної дисперсії не вимагається. Зазначимо, що викиди є дійсними власними значеннями для нормалізованої матриці, що дозволяє швидко локалізувати викиди зі складністю O(N), де N — кількість вузлів системи. Отже, вдалося послабити два важливі припущення щодо розподілу елементів випадкової матриці, а саме припущення про рівність нулю математичних сподівань елементів матриці та про незалежність елементів матриці. Крім того, незалежність елементів можна замінити слабкою незалежністю, яка зберігає збіжність до середнього значення в законі великих чисел. Основна увага надається оцінці оптимальної кількості кластерів для системи, що задається матрицею суміжності A з N вузлами при N→∞ . Розглянуто асимптотичний розподіл власних значень стохастичної випадкової матриці без умов незалежності елементів, спектр якої можна розкласти на регулярну частину та викиди. На основі припущень про однотипність зв’язків у кластері зроблено висновок про оптимальну кількість кластерів для різних прикладних задач. Проведено моделювання мережі зв’язків, що розподілені за законом Пуассона, та знайдено оптимальну кількість кластерів. Результати моделювання вказують на високу точність визначення оптимальної кількості кластерів. У основній теоремі важливим є припущення про існування моменту вище другого для кожного елементу матриці A. Проте, з урахуванням нормалізації, цю умову можна послабити до існування математичного сподівання матриці. Дане послаблення умов збіжності дає можливість використання доведеного твердження на ширший клас прикладних задач, де наявність скінченної дисперсії не вимагається. Зазначимо, що викиди є дійсними власними значеннями для нормалізованої матриці, що дозволяє швидко локалізувати викиди зі складністю O(N), де N — кількість вузлів системи. Отже, вдалося послабити два важливі припущення щодо розподілу елементів випадкової матриці, а саме припущення про рівність нулю математичних сподівань елементів матриці та про незалежність елементів матриці. Крім того, незалежність елементів можна замінити слабкою незалежністю, яка зберігає збіжність до середнього значення в законі великих чисел.
first_indexed	2026-03-12T12:41:28Z
format	Article
fulltext	© О.Л. КИРИЧЕНКО, І.В. МАЛИК, С.Е. ОСТАПОВ, 2022 Міжнародний науково-технічний журнал «Проблеми керування та інформатики», 2022, № 1 37 СТОХАСТИЧНІ СИСТЕМИ, НЕЧІТКІ МНОЖИНИ УДК 004.942, 519.177, 519.217 О.Л. Кириченко, І.В. Малик, С.Е. Остапов АНАЛІЗ КЛАСТЕРНОЇ СТРУКТУРИ ІНТЕРНЕТ-МЕРЕЖ НА ОСНОВІ ВИПАДКОВИХ МАТРИЦЬ Ключові слова: стохастична випадкова матриця, спектр матриці, власні зна- чення, оптимальне число кластерів, марковський алгоритм кластеризації. Keywords: stochastic random matrix, matrix spectrum, eigenvalues, optimal number of clusters, Markov clustering algorithm. Вступ Аналізу великих даних за допомогою розбиття на групи присвячено багато робіт. Основні роботи в даному напрямку зосереджені на задачах кластеризації та пошуку структури розумних мереж (Smart Grid) [1]. Для дослідження мереж Smart Grid за останні роки більшість робіт присвячено спектральному аналізу матриці переходів ,A матриці зв’язків або їхніх похідних [1, 2]. Основні роботи з аналізу матриць великих розмірностей з випадковими елементами ґрунтуються на осно- воположній роботі Марченка–Пастура [3], у якій основну увагу приділено аналізу матриць вигляду T ,A X X= (1) де X — випадкова матриця розмірності ,n N елементами якої є незалежні ви- падкові величини з нульовим середнім та скінченною дисперсією: 0,ijEX = 2 , 1,..., , 1,..., .ijDX i n j N=    = = (2) У результаті даного дослідження було знайдено, що власні значення матри- ці A підпорядковуються так званому розподілу Марченка–Пастура з щільністю розподілу власних значень [4] 2 1 ( ) ( )( ), ( , ), 2 Af x a x x a x a a c + − − += − −    де ,a − ,a + c — параметри розподілу, які визначаються наступними співвідно- шеннями: , n c N = 2 21 .a c=   У загальному випадку закони розподілу для власних значень (1) називаються напівколовими розподілами Вінгера [5–7]. Зрозуміло, що граничний розподіл за- лежить від перетворення матриці .X Основні перетворення та відповідні їм гра- ничні розподіли можна знайти в [8, 9]. Більшість робіт, у яких досліджуються властивості випадкових матриць, ґрунтується на понятті ермітової матриці, яке у 38 ISSN 1028-0979 випадку дійснозначних величин ijX визначає симетричну матрицю. Дане спро- щення ґрунтується на тому, що всі власні значення належать множині дійсних чи- сел, що суттєво полегшує дослідження. Крім того, припущення про рівність 0 ма- тематичних сподівань у (2) відіграє одну із ключових ролей при використанні ме- тоду моментів чи перетворення Стілтьєса [8, 10]. У нашому дослідженні розглянуті матриці не володіють цією властивістю. За рахунок цього спектр мат- риці не підпорядковується круговому розподілу в одиничному колі на комплекс- ній множині ,C оскільки містить викиди [8] порядку ( ).O N Постановка задачі Основна увага в даній роботі присвячена властивостям нормованих мат- риць ,N NA  де кожен елемент рівний ймовірності переходу із однієї вершини Ін- тернет-мережі в іншу [9, 10]. Основна проблема буде ґрунтуватися на спектраль- ному аналізі матриці перехідних ймовірностей. Точніше кажучи, ми будемо аналі- зувати викиди (власні значення поза основним носієм) та робити висновок про оптимальну кількість кластерів, ґрунтуючись на кількості викидів. Нормалізація матриці проводиться для того, щоб локалізувати потрібні нам викиди. Згідно з те- оремою Перрона–Фробеніуса [11] для довільної квадратної матриці A з не- від’ємними елементами, існує власне значення ( ),A таке що ( ) ( ).i A A   Крім того, дане власне значення задовольняє нерівності 1 1 1 1 max min , min ( ) min max , max . N N N N ij ji ij ji i i i ij j j j A A A A A = = = =                         Використовуючи означення стохастичної матриці, яку будемо досліджувати надалі в якості нормалізованої матриці, приходимо до висновку, що ( ) 1.A = Таким чином, нас будуть цікавити викиди, які знаходяться в околі точки 1,z = де радіус околу буде залежати від кількості елементів у кластері, тобто від .N Оскільки нас буде цікавити задача розбиття на підгрупи, тобто задача класте- ризації, будемо припускати, що всі зв’язки в одному кластері є однотипними. Да- не припущення будемо формалізувати наступним чином: елементи матриці сумі- жності A мають однаковий розподіл, тобто ,ijA F де F — розподіл з носієм (0, )S   та скінченним другим моментом та нену- льовим середнім: 2 1 2; .ij ijEA EA =  =   Тоді матрицю перехідних ймовірностей будемо визначати із наступних спів- відношень: 1 . ij ij N ij j A P A = =  Міжнародний науково-технічний журнал «Проблеми керування та інформатики», 2022, № 1 39 Тоді матриця ijP буде стохастичною; крім того, всі елементи матриці будуть мати той же розподіл, носієм якого є множина [0, 1]. Надалі для доведення основ- ного твердження даної роботи будемо використовувати наступний факт. Теорема 1 [7]. Нехай елементи матриці A є незалежними випадковими ве- личинами з нульовим математичним сподіванням та скінченною дисперсією: 0,ijEA = 2 .ijDA =    Тоді розподіл власних значень матриць 1 NM A N = при N → буде збігатися до рівномірного розподілу в одиничному крузі в ,C тобто 1 , 1, ( ) 0 в іншому випадку. z f z   =    Слід зауважити, що матриця вигляду (2) є «незручною» для дослідження, оскільки елементи в рядках не є залежними за рахунок 1 N ij j A =  у знаменнику. Да- ний факт означає, що елементи матриці ijP не є незалежними, що порушує основ- ні умови теореми для визначення асимптотики розподілу власних значень матри- ці .P Ще однією проблемою є той факт, що елементи матриці ijP мають носієм множину R+ та 1 .ijEP N = Таким чином, порушується і друга умова теореми. Для подолання першої проблеми використаємо закон великих чисел. Для цього поряд із матрицею P розглянемо матрицю 1 . ij ij A P N =  Зауважимо, що елементи матриці ijP є незалежними випадковими величина- ми; крім того, асимптотика власних значень матриць P та P є однаковою. Для цього розглянемо наступну лему. Лема. Спектр матриць P та P є асимптотично еквівалентним, тобто 1,..., lim max ( ) 0.i N i N P P → =  − = Доведення. Згідно з існуванням скінченного другого моменту для ,ijA отри- маємо, що 1 1 1 N ij j A N = → у середньому квадратичному. Використовуючи даний факт, отримаємо, що 40 ISSN 1028-0979 1 1 1 1 1 1 1 1 1 . N ij N ij ij ij j ij ij ij ijN N N j ij ij ij j j j N A A A A A P P A N N N A A A = = = = =  −    − = − = =  −          Таким чином, елементи різниці двох матриць будуть прямувати до 0. Врахо- вуючи той факт, що 1 ij N ij j A A =  мають однаковий розподіл для довільних ,i отримає- мо наступне співвідношення: 1 1 1 1 1 1 1 1 1 1 1 1 (1) (1) 0 N N N N N ij ij ij ij ijN N N i j i j i ij ij ij j j j A A A A A o o N N A A A= = = = = = = =     − = − = = →             у середньому квадратичному. Лему доведено. Зауваження. Можна посилити твердження леми та довести, що 1,..., lim max ( ) 0i N i N N P P → =  − = для [0,1). Отже, грунтуючись на лемі, надалі можемо зосередити увагу на дослідженні власних значень матриці ,P які задовольняють умові незалежності. Теорема 2. Розподіл власних значень матриці N P  має асимптотичний розподіл, який зосереджений в одиничному крузі { : 1}z C z  та володіє одним викидом (1). N o+  Доведення. Поряд із матрицею P розглянемо центровану матрицю , 1,..., . i j N P N =   =     Використаємо наступне співвідношення для :P .CP P P P P P= − + = + Основним фактом даного представлення є те, що матриця CP має вигляд 111 1 . N C N NN AA N N P A A N N −−       =    − −     Міжнародний науково-технічний журнал «Проблеми керування та інформатики», 2022, № 1 41 Отже, елементи матриці CP задовольняють умовам теореми 1, і можна стве- рджувати, що власні значення матриці 111 1 N C N NN AA N N N P A A N N −−        =    − −       будуть мати асимптотичний рівномірний розподіл у крузі { : 1}.z C z  Для остаточного доведення теореми залишилося знайти розподіл власних значень матриці P та її зв’язок із матрицею .CP Скористаємося поняттям норма- льної матриці. Враховуючи той факт, що елементи матриці CN P  є незалежни- ми випадковими величинами, отримаємо, що 2 1 ( )( ) N C C ik jk k ij N N N P P A A =     = − − =        .C C ji N N P P    =        З іншого боку, матриця N P  також є нормальною, оскільки 2 2 2 2 2 1 N k ij N N N P P N N=       = = =         .C C ji N N P P    =        Крім того, матриці CN P  та N P  є переставними, тобто 2 C CN N N P P P P=    рівна за розподілом матриці 2 .C CN N N P P PP=    Таким чином, можна вказати унітарну випадкову матрицю ,U для якої ,C C P N P UD U=  ,P N P UD U=  42 ISSN 1028-0979 де CP D та PD — діагональні матриці. У цьому випадку власні значення матриці ( )CN P P+  визначаються як сума власних значень CN P  та . N P  Власні значення матри- ці N P  дорівнюють 1 2, ... 0.N N N N N P P P        =  = =  =                   (3) Використовуючи властивості нормальних переставних матриць, приходимо до висновку, що власні значення матриці ( )CN P P+  будуть сумою власних значень матриці CN P  та . N P  Крім того, нас не цікавить порядок додавання на основі (3). Таким чином, власні значення матриці ( )CN P P+  будуть мати асимптотичний рівномірний розподіл в одиничному крузі { : 1},z C z  крім одного значення, яке дорівнює (1). N o+  Враховуючи даний факт, отрима- ємо, що власні значення P асимптотично розміщені в крузі :z C z N        та одне з власних значень даної матриці дорівнює 1 1 .o N   +     Теорему доведено. Моделювання Як приклад розглянемо задачу визначення оптимальної кількості кластерів для мережі, зв’язки між вузлами в одному кластері будемо моделювати за допо- могою розподілу Пуассона з параметром 1 2. + Крім того, шуми, які будуть ві- дображати міжкластерні зв’язки, будемо моделювати за допомогою розподілу Пуассона з параметром 2 , кількість кластерів при моделюванні дорівнює .k Та- ким чином, розподіл елемента матриці суміжності A буде мати вигляд 1 2 2 ( ), , в одному кластері, ( ) в іншому випадку. ij Poiss i j A Poiss  +   Для визначення оптимального значення кількості кластерів opt ,k як було за- значено в теоремі 2, будемо користатися викидами, тобто власними значеннями, близькими до одиниці. Точніше кажучи, Міжнародний науково-технічний журнал «Проблеми керування та інформатики», 2022, № 1 43 opt 1 opt 1 2max ( ,..., ) ( ) : ( ) , min ( ,..., ) optk i i k k P P N N     =         де iN — кількість елементів у i-му кластері, 2 i — дисперсія елементів у i-му кластері. Зауважимо, що в роботі [12] окреслено дещо інший підхід до визначення викидів, проте даний вибір викидів може породжувати невірні висновки для різ- них розмірностей кластерів, тобто для різних .iN Тому для розв’язання проблеми різних розмірностей будемо використовувати наступний критерій визначення ви- кидів: opt opt 1 opt opt 1 2max ( ,..., )0,2 ( ) : ( ) min , . min ( ,..., ) k i i k k P P k N N      =            Результати кластеризації можемо бачити в таблиці. З даної таблиці видно, що невірна оцінка може виникати у трьох випадках. • Кількість кластерів велика, тобто ( ).k o N= • Розміри кластерів дуже різняться, тобто значення співвідношення max ( ) min ( ) i i N r N = є великим. • Середнє значення шуму, за яким будуються міжкластерні зв’язки, має од- наковий порядок із усередненими зв’язками всередині кластерів, тобто ( ) ( ( )).ii ijE A o E A= Дані три критичні ситуації призводять до заниження значення оптимальної кількості кластерів opt .k Виконання двох сценаріїв можемо бачити в останньому випадку у таблиці. По-перше, в цьому випадку max ( ) 800 40, min ( ) 20 i i N r N = = = що свідчить про незбалансованість між розмірами кластерів. По-друге, середнє значення міжкластерного зв’язку дорівнює 8, в той же час середній зв’язок у кластері дорівнює 8 10 18,+ = тобто дані зв’язки задовольняють співвідношен- ню ( ) ( ( )).ii ijE A o E A= Як можемо бачити з рис. 1 (власні значення матриці P для випадку (10, 8) = та (500, 20, 300, 800,100, 400)),N = за виконання цих двох сценаріїв викиди «стягуються» до центру. В цьому випадку відбувається зани- ження оптимальної кількості кластерів opt .k Таблиця 1 2( , ) =   1( ,..., )kN N N= k kopt (20, 0,5) 500, 200, 300, 800, 100, 400 6 6 (20, 1) 500, 200, 300, 800, 100, 400 6 6 (20, 1) 1000, 200, 20 3 3 (20, 4) 200, 200, 200 3 3 (20, 10) 1000, 200, 200, 200, 200 5 5 (10, 8) 500, 20, 300, 800, 100, 400 6 5 44 ISSN 1028-0979 Рис. 1 Якщо жодна з критичних ситуацій не має місця, то всі викиди будуть близькими до 1, = як і зазначено в теоремі 2. Даний результат проілюстровано на рис. 2 при власних значеннях (10, 0,5) = матриці P та (500, 300, 800, 400, 400).N = Рис. 2 Висновок У даній роботі проведено спектральний аналіз власних значень матриці пере- ходу для випадку однотипного зв’язку для всіх елементів. Проаналізовано грани- чний розподіл власних значень матриці переходу на основі зв’язку викидів серед власних значень та оптимальної кількості кластерів opt .k У майбутніх роботах планується визначити взаємозв’язок між помилкою кластеризації та величинами, що можуть породжувати дану помилку, — спів- відношення між максимальним та мінімальним розмірами кластерів max ( ) , min ( ) i i N N співвідношення між середнім значенням шуму та середнім значенням зв’язку в кластерах min max ij ii EP EP та співвідношення між розмірністю даних N та кількіс- тю кластерів .k – 1 0 1 1 0 – 1 – 1 0 1 1 0 – 1 Міжнародний науково-технічний журнал «Проблеми керування та інформатики», 2022, № 1 45 О.Л. Кириченко, І.В. Малик, С.Е. Остапов АНАЛІЗ КЛАСТЕРНОЇ СТРУКТУРИ ІНТЕРНЕТ-МЕРЕЖ НА ОСНОВІ ВИПАДКОВИХ МАТРИЦЬ Основна увага надається оцінці оптимальної кількості кластерів для сис- теми, що задається матрицею суміжності A з N вузлами при .N → Роз- глянуто асимптотичний розподіл власних значень стохастичної випадкової матриці без умов незалежності елементів, спектр якої можна розкласти на регулярну частину та викиди. На основі припущень про однотипність зв’язків у кластері зроблено висновок про оптимальну кількість кластерів для різних прикладних задач. Проведено моделювання мережі зв’язків, що розподілені за законом Пуассона, та знайдено оптимальну кількість клас- терів. Результати моделювання вказують на високу точність визначення оптимальної кількості кластерів. У основній теоремі важливим є припу- щення про існування моменту вище другого для кожного елементу матри- ці .A Проте, з урахуванням нормалізації, цю умову можна послабити до існування математичного сподівання матриці. Дане послаблення умов збі- жності дає можливість використання доведеного твердження на ширший клас прикладних задач, де наявність скінченної дисперсії не вимагається. Зазначимо, що викиди є дійсними власними значеннями для нормалізова- ної матриці, що дозволяє швидко локалізувати викиди зі складністю ( ),O N де N — кількість вузлів системи. Отже, вдалося послабити два важливі припущення щодо розподілу елементів випадкової матриці, а саме припу- щення про рівність нулю математичних сподівань елементів матриці та про незалежність елементів матриці. Крім того, незалежність елементів можна замінити слабкою незалежністю, яка зберігає збіжність до серед- нього значення в законі великих чисел. O.L. Kyrychenko, I.V. Malyk, S.E. Ostapov CLUSTER STRUCTURE ANALYSIS OF INTERNET NETWORKS BASED ON RANDOM MATRIXES The main attention is paid to the estimation of the optimal number of clusters for the system given by the node adjacency matrix .A Based on the assump- tions about the similarity of connections in the cluster, the conclusion was drawn about optimal number of clusters for different applications. Poisson's network of connections is modeled and the optimal number of clusters is found. The simulation results indicate high accuracy in determining the optimal num- ber of clusters. In the basic theorem, it is important to assume the existence of a moment above the second for each element of the matrix .A However, taking into account normalization, this condition can be reduced to the existence of a mathematical expectation of the matrix .A This weakening of the convergence conditions makes it possible to use a proven statement for a wider class of ap- plied problems, where the presence of a finite variance is not required. Note that the emissions are valid eigenvalues for the normalized matrix, which al- lows you to localize quickly emissions with complexity ( ),O N where N — the number of system nodes. Thus, we managed to weaken two important assump- tions about the distribution of elements of a random matrix, namely the as- sumption about the equality of 0 mathematical expectations of the elements of the matrix and the independence of the elements of the matrix. In addition, the independence of the elements can be replaced by weak independence, which maintains convergence to the mean value in the law of large numbers. 46 ISSN 1028-0979 REFERENCES 1. Li F., Qiao W., Sun H., Wan H., Wang J., Xia Y., Xu Z., Zhang P. Smart transmission grid: vi- sion and framework. IEEE Transactions on Smart Grid. 2010. 1, N 2. P. 168–177. 2. Liserre M., Sauter T., Hung J.-Y. Future energy systems: integrating renewable energy sources into the smart power grid through industrial electronics. IEEE Industrial Electronics Magazine. 2010. 4. P. 18–37. http://dx.doi.org/10.1109/MIE.2010.935861. 3. Марченко В.А., Пастур Л.А. Распределение собственных значений в некоторых ансамблях случайных матриц. Матем. сб. 1967. 72 (114), № 4. C. 507–536. 4. Lytova A., Pastur L. Central limit theorem for linear eigenvalue statistics of random matrices with independent entries. The Annals of Probability. 2009. 37 (5). P. 1778–1840. http://dx.- doi.org/10.1214/09-AOP452/. 5. Tao T., Vu V. Random matrices: sharp concentration of eigenvalues, random matrices. Theory and Applications. 2012. 02 (03). 28 p. http://dx.doi.org/10.1142/S201032631350007X. 6. Wigner Eugene P. On the distribution of the roots of certain symmetric matrices. The Annals of Mathematics, Second Series. 1958. 67, N 2. P. 325–327. 7. Wigner Eugene P. Characteristic vectors of bordered matrices with infinite dimensions. The An- nals of Mathematics, Second Series. 1955. 62, N 3. P. 548–564. https://doi.org/10.2307/1970079. 8. Robert C. Qiu, Paul Antonik. Smart grid using big data analytics. A random matrix theory approach. Wiley Online Library. 2017. 632 p. 9. Terence Tao. Topics in random matrix theory. University of California, Graduate studies in mathematics. 2012. 132. 340 p. Includes bibliographical references and index. ISBN 978-0-8218- 7430-1. 10. Geronimo J.S., Hill T.P. Necessary and sufficient condition that the limit of Stieltjes transforms is a Stieltjes transform. Journal of Approximation Theory. 2003. 121 (1). P. 54–60. 11. Гантмахер Ф.Р. Теория матриц. М. : Наука, 1966. 576 с. 12. Кириченко О.Л., Малик І.В., Остапов С.Е. Стохастичні моделі в задачах штучного інтелек- ту. Вісник Київського національного університету імені Тараса Шевченка. Серія «Фізико- математичні науки». 2021. Вип. 2. С. 53–57. Отримано 31.01.2022
id	nasplib_isofts_kiev_ua-123456789-210862
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	0572-2691
language	Ukrainian
last_indexed	2026-03-12T12:41:28Z
publishDate	2022
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
record_format	dspace
spelling	Кириченко, О.Л. Малик, І.В Остапов, С.Е. 2025-12-19T14:38:59Z 2022 Аналіз кластерної структури Інтернет-мереж на основі випадкових матриць / О.Л. Кириченко, І.В. Малик, С.Е. Остапов // Проблеми керування та інформатики. — 2022. — № 1. — С. 37-46. — Бібліогр.: 12 назв. — укр. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/210862 004.942,519.177, 519.217 10.34229/1028-0979-2022-1-4 Основна увага надається оцінці оптимальної кількості кластерів для системи, що задається матрицею суміжності A з N вузлами при N→∞ . Розглянуто асимптотичний розподіл власних значень стохастичної випадкової матриці без умов незалежності елементів, спектр якої можна розкласти на регулярну частину та викиди. На основі припущень про однотипність зв’язків у кластері зроблено висновок про оптимальну кількість кластерів для різних прикладних задач. Проведено моделювання мережі зв’язків, що розподілені за законом Пуассона, та знайдено оптимальну кількість кластерів. Результати моделювання вказують на високу точність визначення оптимальної кількості кластерів. У основній теоремі важливим є припущення про існування моменту вище другого для кожного елементу матриці A. Проте, з урахуванням нормалізації, цю умову можна послабити до існування математичного сподівання матриці. Дане послаблення умов збіжності дає можливість використання доведеного твердження на ширший клас прикладних задач, де наявність скінченної дисперсії не вимагається. Зазначимо, що викиди є дійсними власними значеннями для нормалізованої матриці, що дозволяє швидко локалізувати викиди зі складністю O(N), де N — кількість вузлів системи. Отже, вдалося послабити два важливі припущення щодо розподілу елементів випадкової матриці, а саме припущення про рівність нулю математичних сподівань елементів матриці та про незалежність елементів матриці. Крім того, незалежність елементів можна замінити слабкою незалежністю, яка зберігає збіжність до середнього значення в законі великих чисел. Основна увага надається оцінці оптимальної кількості кластерів для системи, що задається матрицею суміжності A з N вузлами при N→∞ . Розглянуто асимптотичний розподіл власних значень стохастичної випадкової матриці без умов незалежності елементів, спектр якої можна розкласти на регулярну частину та викиди. На основі припущень про однотипність зв’язків у кластері зроблено висновок про оптимальну кількість кластерів для різних прикладних задач. Проведено моделювання мережі зв’язків, що розподілені за законом Пуассона, та знайдено оптимальну кількість кластерів. Результати моделювання вказують на високу точність визначення оптимальної кількості кластерів. У основній теоремі важливим є припущення про існування моменту вище другого для кожного елементу матриці A. Проте, з урахуванням нормалізації, цю умову можна послабити до існування математичного сподівання матриці. Дане послаблення умов збіжності дає можливість використання доведеного твердження на ширший клас прикладних задач, де наявність скінченної дисперсії не вимагається. Зазначимо, що викиди є дійсними власними значеннями для нормалізованої матриці, що дозволяє швидко локалізувати викиди зі складністю O(N), де N — кількість вузлів системи. Отже, вдалося послабити два важливі припущення щодо розподілу елементів випадкової матриці, а саме припущення про рівність нулю математичних сподівань елементів матриці та про незалежність елементів матриці. Крім того, незалежність елементів можна замінити слабкою незалежністю, яка зберігає збіжність до середнього значення в законі великих чисел. uk Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Стохастичні системи, нечіткі множини Аналіз кластерної структури Інтернет-мереж на основі випадкових матриць Cluster structure analysis of Internet networks based on random matrices Article published earlier
spellingShingle	Аналіз кластерної структури Інтернет-мереж на основі випадкових матриць Кириченко, О.Л. Малик, І.В Остапов, С.Е. Стохастичні системи, нечіткі множини
title	Аналіз кластерної структури Інтернет-мереж на основі випадкових матриць
title_alt	Cluster structure analysis of Internet networks based on random matrices
title_full	Аналіз кластерної структури Інтернет-мереж на основі випадкових матриць
title_fullStr	Аналіз кластерної структури Інтернет-мереж на основі випадкових матриць
title_full_unstemmed	Аналіз кластерної структури Інтернет-мереж на основі випадкових матриць
title_short	Аналіз кластерної структури Інтернет-мереж на основі випадкових матриць
title_sort	аналіз кластерної структури інтернет-мереж на основі випадкових матриць
topic	Стохастичні системи, нечіткі множини
topic_facet	Стохастичні системи, нечіткі множини
url	https://nasplib.isofts.kiev.ua/handle/123456789/210862
work_keys_str_mv	AT kiričenkool analízklasternoístrukturiínternetmerežnaosnovívipadkovihmatricʹ AT malikív analízklasternoístrukturiínternetmerežnaosnovívipadkovihmatricʹ AT ostapovse analízklasternoístrukturiínternetmerežnaosnovívipadkovihmatricʹ AT kiričenkool clusterstructureanalysisofinternetnetworksbasedonrandommatrices AT malikív clusterstructureanalysisofinternetnetworksbasedonrandommatrices AT ostapovse clusterstructureanalysisofinternetnetworksbasedonrandommatrices

Аналіз кластерної структури Інтернет-мереж на основі випадкових матриць

Institution

Similar Items