Аналіз кластерної структури Інтернет-мереж на основі випадкових матриць
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 assumptions about the similarity of connections in the cluster, the conclusion was drawn about optimal number of clusters for different applications. Poiss...
Збережено в:
| Дата: | 2023 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
V.M. Glushkov Institute of Cybernetics of NAS of Ukraine
2023
|
| Теми: | |
| Онлайн доступ: | https://jais.net.ua/index.php/files/article/view/84 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Problems of Control and Informatics |
Репозитарії
Problems of Control and Informatics| id |
oai:ojs2.jais.net.ua:article-84 |
|---|---|
| record_format |
ojs |
| institution |
Problems of Control and Informatics |
| baseUrl_str |
|
| datestamp_date |
2024-03-12T11:58:21Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
стохастична випадкова матриця спектр матриці власні значення оптимальне число кластерів марковський алгоритм кластеризації |
| spellingShingle |
стохастична випадкова матриця спектр матриці власні значення оптимальне число кластерів марковський алгоритм кластеризації Kyrychenko, Oksana Malyk, Igor Ostapov, Sergey Аналіз кластерної структури Інтернет-мереж на основі випадкових матриць |
| topic_facet |
стохастична випадкова матриця спектр матриці власні значення оптимальне число кластерів марковський алгоритм кластеризації stochastic random matrix matrix spectrum eigenvalues optimal number of clusters Markov clustering algorithm стохастическая случайная матрица спектр матрицы собственные значения оптимальное число кластеров марковский алгоритм кластеризации |
| format |
Article |
| author |
Kyrychenko, Oksana Malyk, Igor Ostapov, Sergey |
| author_facet |
Kyrychenko, Oksana Malyk, Igor Ostapov, Sergey |
| author_sort |
Kyrychenko, Oksana |
| title |
Аналіз кластерної структури Інтернет-мереж на основі випадкових матриць |
| title_short |
Аналіз кластерної структури Інтернет-мереж на основі випадкових матриць |
| title_full |
Аналіз кластерної структури Інтернет-мереж на основі випадкових матриць |
| title_fullStr |
Аналіз кластерної структури Інтернет-мереж на основі випадкових матриць |
| title_full_unstemmed |
Аналіз кластерної структури Інтернет-мереж на основі випадкових матриць |
| title_sort |
аналіз кластерної структури інтернет-мереж на основі випадкових матриць |
| title_alt |
Анализ кластерной структуры Интернет-сетей на основе случайных матриц Анализ кластерной структуры Интернет-сетей на основе случайных матриц |
| description |
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 assumptions 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 number 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 applied problems, where the presence of a finite variance is not required. Note that the emissions are valid eigenvalues for the normalized matrix, which allows you to localize quickly emissions with complexity O(N), where N — the number of system nodes. Thus, we managed to weaken two important assumptions about the distribution of elements of a random matrix, namely the assumption 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. |
| publisher |
V.M. Glushkov Institute of Cybernetics of NAS of Ukraine |
| publishDate |
2023 |
| url |
https://jais.net.ua/index.php/files/article/view/84 |
| work_keys_str_mv |
AT kyrychenkooksana analizklasternojstrukturyinternetsetejnaosnoveslučajnyhmatric AT malykigor analizklasternojstrukturyinternetsetejnaosnoveslučajnyhmatric AT ostapovsergey analizklasternojstrukturyinternetsetejnaosnoveslučajnyhmatric AT kyrychenkooksana analízklasternoístrukturiínternetmerežnaosnovívipadkovihmatricʹ AT malykigor analízklasternoístrukturiínternetmerežnaosnovívipadkovihmatricʹ AT ostapovsergey analízklasternoístrukturiínternetmerežnaosnovívipadkovihmatricʹ |
| first_indexed |
2025-10-30T02:48:37Z |
| last_indexed |
2025-10-30T02:48:37Z |
| _version_ |
1847373350659162112 |
| spelling |
oai:ojs2.jais.net.ua:article-842024-03-12T11:58:21Z Анализ кластерной структуры Интернет-сетей на основе случайных матриц Анализ кластерной структуры Интернет-сетей на основе случайных матриц Аналіз кластерної структури Інтернет-мереж на основі випадкових матриць Kyrychenko, Oksana Malyk, Igor Ostapov, Sergey стохастична випадкова матриця спектр матриці власні значення оптимальне число кластерів марковський алгоритм кластеризації stochastic random matrix matrix spectrum eigenvalues optimal number of clusters Markov clustering algorithm стохастическая случайная матрица спектр матрицы собственные значения оптимальное число кластеров марковский алгоритм кластеризации 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 assumptions 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 number 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 applied problems, where the presence of a finite variance is not required. Note that the emissions are valid eigenvalues for the normalized matrix, which allows you to localize quickly emissions with complexity O(N), where N — the number of system nodes. Thus, we managed to weaken two important assumptions about the distribution of elements of a random matrix, namely the assumption 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. Основное внимание уделяется оценке оптимального количества кластеров для системы, задаваемой матрицей смежности A с N узлами при N→∞. Рассмотрено асимптотическое распределение собственных значений стохастической случайной матрицы без условий независимости элементов, спектр которой можно разложить на регулярную часть и выбросы. На основе предположений об однотипности связей в кластере сделан вывод об оптимальном количестве кластеров для различных прикладных задач. Проведено моделирование сети связей, распределенных по закону Пуассона, и найдено оптимальное количество кластеров. Результаты моделирования указывают на высокую точность определения оптимального количества кластеров. В основной теореме важно предположение о существовании момента выше второго для каждого элемента матрицы А. Однако, с учетом нормализации, это условие можно ослабить до существования математического ожидания матрицы. Данное ослабление условий сходимости дает возможность использования доказанного утверждения на более широкий класс прикладных задач, где наличие конечной дисперсии не требуется. Отметим, что выбросы являются действительными собственными значениями для нормализованной матрицы, что позволяет быстро локализовать выбросы со сложностью O(N), где N - количество узлов системы. Итак, удалось ослабить два важных предположения относительно распределения элементов случайной матрицы, а именно предположение о равенстве нуля математических ожиданий элементов матрицы и независимости элементов матрицы. Кроме того, независимость элементов можно заменить слабой независимостью, сохраняющей сходимость к среднему значению в законе больших чисел. Основна увага надається оцінці оптимальної кількості кластерів для системи, що задається матрицею суміжності A з N вузлами при N→∞ . Розглянуто асимптотичний розподіл власних значень стохастичної випадкової матриці без умов незалежності елементів, спектр якої можна розкласти на регулярну частину та викиди. На основі припущень про однотипність зв’язків у кластері зроблено висновок про оптимальну кількість кластерів для різних прикладних задач. Проведено моделювання мережі зв’язків, що розподілені за законом Пуассона, та знайдено оптимальну кількість кластерів. Результати моделювання вказують на високу точність визначення оптимальної кількості кластерів. У основній теоремі важливим є припущення про існування моменту вище другого для кожного елементу матриці A. Проте, з урахуванням нормалізації, цю умову можна послабити до існування математичного сподівання матриці. Дане послаблення умов збіжності дає можливість використання доведеного твердження на ширший клас прикладних задач, де наявність скінченної дисперсії не вимагається. Зазначимо, що викиди є дійсними власними значеннями для нормалізованої матриці, що дозволяє швидко локалізувати викиди зі складністю O(N), де N — кількість вузлів системи. Отже, вдалося послабити два важливі припущення щодо розподілу елементів випадкової матриці, а саме припущення про рівність нулю математичних сподівань елементів матриці та про незалежність елементів матриці. Крім того, незалежність елементів можна замінити слабкою незалежністю, яка зберігає збіжність до середнього значення в законі великих чисел. V.M. Glushkov Institute of Cybernetics of NAS of Ukraine 2023-08-03 Article Article application/pdf https://jais.net.ua/index.php/files/article/view/84 10.34229/1028-0979-2022-1-4 Міжнародний науково-технічний журнал "Проблеми керування та інформатики"; Том 67 № 1 (2022): Міжнародний науково-технічний журнал "Проблеми керування та інформатики"; 37-46 International Scientific Technical Journal "Problems of Control and Informatics; Том 67 № 1 (2022): International Scientific Technical Journal "PROBLEMS OF CONTROL AND INFORMATICS"; 37-46 International Scientific Technical Journal "Problems of Control and Informatics"; Vol. 67 No. 1 (2022): International Scientific Technical Journal "PROBLEMS OF CONTROL AND INFORMATICS"; 37-46 2786-6505 2786-6491 10.34229/1028-0979-2022-1 uk https://jais.net.ua/index.php/files/article/view/84/164 Copyright (c) 2022 Oksana Kyrychenko, Igor Malyk, Sergey Ostapov https://creativecommons.org/licenses/by-nc-nd/4.0/ |