КЛАСТЕРИЗАЦIЯ: МАРКОВСЬКИЙ АЛГОРИТМ
Анотація
У данiй роботi розглянуто проблему кластеризацiї на графах на основi власних значень стохастичної матрицi графа. Доведено, що власнi значення стохастичної матрицi для
великих графiв (N > 100) подiляються на три групи, одна iз яких є визначальною для числа кластерiв у графi. Використовуючи теорiю випадкових матриць, вдалося показати, що
асимптотичний розподiл пiдгрупи дiйсних частин власних значень стохастичної матрицi
графу описується напiвколовим розподiлом Вiгнера, причому параметр даного розподiлу є O . Використання стохастичних матриць дало змогу точно локалiзувати власнi
значення, що вiдповiдають за кiлькiсть кластерiв, чого не вдавалося зробити для матриць
сумiжностi. Основнi припущення моделi пов’язанi з властивостями дискретних ланцюгiв
Маркова, що дозволяє розширити область застосування отриманих результатiв на бiльш
ширший клас об’єктiв. Теоретичнi результати перевiренi на кластеризацiї часових рядiв,
що описують вартостi N = 470 акцiй S&P500 в перiод 2013 –2018 рр. Результати кластеризацiї даних часових рядiв показали наявнiсть 5 чiтко виражених груп, якi узгоджується
iз використаними даними.
Завантаження
Посилання
REFERENCES
Bagherikaram G., Motahari A., Khandani A. The Secrecy Capacity Region of the Gaussian MIMO
Broadcast Channel. Information Theory 2013, 59, 2673-2682.
https://doi.org/10.1109/TIT.2012.2236972
Bai Z., Fang Z., Liang Y. Spectral Theory of Large Dimensional Random Matrices and Its Applications
to Wireless Communications and Finance Statistics : Random Matrix Theory and Its Applications,
World Scientific Publishing Company, 2014.
Bender E.A., Williamson S.G. Lists, Decisions and Graphs - With an Introduction to Probability.
University of California at San Diego, San Diego, 2010.
Biely С., Thurner S. Random matrix ensembles of time-lagged correlation matrices: Derivation of eigenvalue spectra and analysis of financial time-series. Quantitative Finance 2008. 8, 705-722.
https://doi.org/10.1080/14697680701691477
Bolch G., Greiner S., Meer H., Trivedi K. Queueing Networks and Markov Chains. John Wiley, 2nd
edition 2006, 40 (5), 567-568.
https://doi.org/10.1097/00004836-200608000-00001
Crisan D., Del Moral P., Lyons T. Discrete filtering using branching and interacting particle systems.
Markov Processes and Related Fields 1999, 5 (4), 293-318.
Dongen S. Graph Clustering by Flow Simulation. PhD thesis, University of Utrecht, 2000.
Girvan M., Newman M. Community structure in social and biological networks. Proc. Natl Acad. Sci. USA 2002, 99 (12), 7821-7826.
https://doi.org/10.1073/pnas.122653799
Qiu R., Antonik P. Smart Grid using Big Data Analytics. A Random Matrix Theory Approach. Wiley
Online Library, 2017.
Knignitska T.V. Estimate of time series similarity based on models. Problems of Control and Informatics 2019, 51 (4), 94-104.
Marchenko V.A., Pastur L.A. Distribution of eigenvalues for some sets of random matrices. Mat. Sb. N.S. 1967, 72(114) (4), 507--536.
Автори, які публікуються у цьому журналі, погоджуються з наступними умовами:
1. Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.
2. Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.
3. Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису роботи, як до подання цього рукопису до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).
