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

• Дата: 2023
• Автори: Kyrychenko, Oksana, Malyk, Igor, Ostapov, Sergey
• Формат: Стаття
• Мова: 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

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.