Плотные подграфы в рыночном графе для России, в частности квази-клик - Дипломная работа

Графы, состоящие из вершин и ребер, представляют удобный инструмент моделирования для изучения различных сетевых структур, в том числе, социальных сетей, сети Интернет, естественных экосистем, телекоммуникационных сетей и других. Хорошим описанием таких структур является клика, определенная как множество вершин, в котором любые две вершины связаны ребром. Поиску максимальной клики в графе посвящены многие работы [1][8][9]. Для российского рынка наблюдается интересная особенность - структура максимальной клики рыночного графа сильно перекликается с набором акций, торгующихся в наибольшем объеме. Целью моей работы стало определить, оправдано ли применение поиска максимальных квази-клик вместо максимальных клик для российского рынка.Правительства, банки, фирмы владеют акциями, облигациями и долгами друг друга, что ведет к росту оборота ценных бумаг на мировом рынке. Первоначальное увеличение диверсификации в сети позволяет «инфекции» распространяться дальше, но последующее увеличение позволяет сделать организации менее зависимыми друг от друга и остановить распространение. В последние годы популярным методом исследования фондовых рынков является построение и анализ графа рынка, вершинами которого являются акции, торгующиеся на бирже, а вес ребра определяет степень зависимости двух акций друг от друга. Далее рассчитываются коэффициенты корреляции между акциями по формуле: , где отражает доходность ценной бумаги i в день t по отношению к предыдущему дню t-1 и рассчитывается как , - цена акции, показывает среднюю доходность акции i за n дней , а определяет дисперсию доходности i-ой акции за n дней Первичный - рынок, на котором происходит первичное размещение ценных бумаг, вторичный рынок позволяет инвесторам свободно покупать и продавать ценные бумаги.Клика C - представляет собой такое подмножество вершин из V, что подграф G[C] графа G, построенный на множестве C, является полным. Клика называется максимальной по включению, если она не является подмножеством большей клики, и максимальной по размеру, если не существует большей клики в графе. В некоторых случая для решения задач, опирающихся на экспериментальные данные, в том числе экономических задач, логично заменить клику на квази-клику, то есть использовать вместо клики ее релаксацию [17]. Подмножество вершин Q называется ?-квази-кликой или просто ?-кликой, если плотность ребер графа G[Q], рассчитанная как отношение числа ребер, вошедших в граф, к числу всех возможных ребер на подмножестве Q, по меньшей мере равна ?. Плотность ребер в графе можно вычислить следующим образом: где E - количество существующих ребер в графе, V - количество вершин графа.В статье Network approach for the Russian stock market авторы анализируют данные фондового рынка для России, в том числе используют поиск максимальной клики для выделения и дальнейшего изучения сильно связных акций [19]. Стоит заметить, что граф рынка может содержать несколько клик максимального размера, поэтому авторы рассматривают динамику множества, представляющего объединение всех максимальных клик в графе. Ожидается, что квази-клика с некоторым фиксированным порогом плотности будет содержать объединение всех максимальных клик графа. Таким образом, мы сможем сделать вывод о том, что доминирующие акции российского рынка представляют собой квази-клику, которую можно получить, используя некоторый заданный порог плотности. Для того, чтобы проанализировать правильность подхода с применением квази-клики, необходимо проанализировать те же данные и те же периоды, что и описанные в работе Network approach for the Russian stock market [19].} public static MULTIVALUEMAP[] PARSECSV(String filename, String STARTDATE1, String ENDDATE1, String STARTDATE2, String ENDDATE2, String STARTDATE3, String ENDDATE3, String STARTDATE4, String ENDDATE4, String STARTDATE5, String ENDDATE5, String STARTDATE6, String ENDDATE6, String STARTDATE7, String ENDDATE7, String STARTDATE8, String ENDDATE8, String STARTDATE9, String ENDDATE9, String STARTDATE10, String ENDDATE10, String STARTDATE11, String ENDDATE11) throws PARSEEXCEPTION {log("Parsing CSV file"); csv.read(filename, new CSVREADPROC() {public void PROCROW(int ROWINDEX, String... values) {try {if (sdf.parse(values[1]).COMPARETO(DATESTART1) >= 0 && sdf.parse(values[1]).COMPARETO(DATEEND1) <= 0) { } if (sdf.parse(values[1]).COMPARETO(DATESTART2) >= 0 && sdf.parse(values[1]).

Графы, состоящие из вершин и ребер, представляют удобный инструмент моделирования для изучения различных сетевых структур, в том числе, социальных сетей, сети Интернет, естественных экосистем, телекоммуникационных сетей и других. Не является исключением и финансовый сектор, представляющий огромные сетевые структуры, как в масштабах страны, так и по всему миру. Одной из наиболее интересных задач в таком моделировании является поиск кластеров, иными словами, сильно связанных подмножеств. Хорошим описанием таких структур является клика, определенная как множество вершин, в котором любые две вершины связаны ребром. Основной проблемой является то, что задача нахождения точного решения является NP-сложной.

Поиску максимальной клики в графе посвящены многие работы [1][8][9]. Также существует мнение, что требование любых двух вершин быть связанными слишком строго, когда мы опираемся на реальные экспериментальные данные [17]. Поэтому ряд работ рассматривает "релаксацию" клики, где используется понятие квази-клики, допускающей отсутствие некоторых ребер в решении [9][13][16][17][20].

Ряд кризисных потрясений последних десятилетий затронул практически все страны, в том числе и Россию. Кризисные явления, как правило, проявляются во всех сферах экономической и финансовой жизни страны, это можно объяснить наличием сетевых структур, сильных зависимостей различных институтов между собой. Фондовый рынок не является исключением, поэтому прогнозирование тенденций его поведения является актуальной задачей на все время его существования.

Данная выпускная работа посвящена исследованию плотных подграфов в рыночном графе для России, в частности квази-клик. Для российского рынка наблюдается интересная особенность - структура максимальной клики рыночного графа сильно перекликается с набором акций, торгующихся в наибольшем объеме.

Целью моей работы стало определить, оправдано ли применение поиска максимальных квази-клик вместо максимальных клик для российского рынка. Иными словами, возможно ли с помощью квази-клик определить тенденции на российском рынке более репрезентативно, чем с применением максимальных клик.

Для достижения поставленной цели были определены следующие задачи: · Изучить теоретические аспекты применения графа-рынка;

· Осуществить программную реализацию алгоритма поиска максимальных квази-клик в графе;

· Проанализировать результаты работы алгоритма и сравнить с результатами полученными для максимальных клик.

Работа носит исследовательских характер. Объектом исследования является фондовый рынок России. Предметом исследования является возможность применения квази-клик для получения лучших характеристик тенденций присутствующих на рынке. Квази-клика, как инструмент для анализа фондового рынка, впервые применяется к Российскому рынку и детально сравнивается с кликой, этим обусловлена новизна работы.

1. Abello J., Pardalos P. M., Resende M. G. C. On maximum clique problems in very large graphs //AT&T labs Research Technical Report: TR98. - 1998. - Т. 32.

2. Allen F., Babus A. Networks in finance. - 2008.

3. Balaji S., Swaminathan V., Kannan K. A simple algorithm to optimize maximum independent set //Advanced Modeling and Optimization. - 2010. - Т. 12. - №. 1. - С. 107-118.

4. Bautin G. A., Kalyagin V.A., Koldanov A.P., Koldanov P., Pardalos P.M.. Simple measure of similarity for the market graph construction //Computational Management Science. - 2013. - Т. 10. - №. 2-3. - С. 105-124.

5. Boginski V., Butenko S., Pardalos P. M. On structural properties of the market graph //Innovations in financial and economic networks. - 2003. - С. 29-45.

6. Boginski V., Butenko S., Pardalos P. M. Statistical analysis of financial networks //Computational statistics & data analysis. - 2005. - Т. 48. - №. 2. - С. 431-443.

7. Boginski V., Butenko S., Pardalos P. M. Mining market data: a network approach //Computers & Operations Research. - 2006. - Т. 33. - №. 11. - С. 3171-3184.

8. Bomze I. M. et al. The maximum clique problem //Handbook of combinatorial optimization. - Springer US, 1999. - С. 1-74.

9. Brunato M., Hoos H. H., Battiti R. On effectively finding maximal quasi-cliques in graphs //Learning and Intelligent Optimization. - Springer Berlin Heidelberg, 2008. - С. 41-55.

10. Elliott M., Golub B., Jackson M. O. Financial networks and contagion //Available at SSRN 2175056. - 2014.

11. Gai P., Kapadia S. Contagion in financial networks //Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences. - The Royal Society, 2010. - С. rspa20090410.

12. Koldanov A. P. et al. Statistical procedures for the market graph construction //Computational Statistics & Data Analysis. - 2013. - Т. 68. - С. 17-29.

13. Liu G., Wong L. Effective pruning techniques for mining quasi-cliques //Machine Learning and Knowledge Discovery in Databases. - Springer Berlin Heidelberg, 2008. - С. 33-49.

14. Mantegna R., Stanley H. E. An Introduction to Econophysics: Correlations and Complexity in Finance, 2000 //Cambridge University Press, Cambridge. Citado. - 2005. - Т. 7. - С. 26-34.

15. Michael R. G., David S. J. Computers and intractability: a guide to the theory of NP-completeness //WH Freeman & Co., San Francisco. - 1979.

16. Pajouh F. M., Miao Z., Balasundaram B. A branch-and-bound approach for maximum quasi-cliques //Annals of Operations Research. - 2014. - Т. 216. - №. 1. - С. 145-161.

17. Pattillo J. et al. On the maximum quasi-clique problem //Discrete Applied Mathematics. - 2013. - Т. 161. - №. 1. - С. 244-257.

18. Soffer S. N., Vazquez A. Network clustering coefficient without degree-correlation biases //PHYSICAL REVIEW-SERIES E-. - 2005. - Т. 71. - №. 5. - С. 057101.

19. Vizgunov A. et al. Network approach for the Russian stock market //Computational Management Science. - 2014. - Т. 11. - №. 1-2. - С. 45-55.

20. Zeng Z. et al. Coherent closed quasi-clique discovery from large dense graph databases //Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. - ACM, 2006. - С. 797-802.

21. Буренин А.Н. Рынок ценных бумаг и производных финансовых инструментов: учеб. пособие / А. Н. Буренин; Ин-т "Открытое общество". - М.: 1 Федеративная Книготорговая Компания, 1998. - 348 с. - ISBN 5-7814-0070-2.

22. Визгунов А.Н., Трифонов Ю. В. Применение модели графа доходностей для анализа фондового рынка //ВЕСТНИК НИЖЕГОРОДСКОГО УНИВЕРСИТЕТА ИМ. НИ ЛОБАЧЕВСКОГО. - 2013. - №. 6-1.

23. Задача о клике // Википедия. [2013-2013]. Дата обновления: 14.03.2013. URL: http://ru.wikipedia.org/?oldid=53537169 (дата обращения: 14.03.2013).

24. Кудрин А., Правительства РФ З. П. Россия и мировой финансовый кризис //Вопросы экономики. - 2009. - №. 1. - С. 7-10.

25. Медвежье царство Ведомости (FT) № 193 (2215) 13 октября 2008

26. НИЯЗБЕКОВА Ш. У. Становление и развитие фондового рынка в Российской Федерации и Республике Казахстан //ИЗВЕСТИЯ ОРЕНБУРГСКОГО ГОСУДАРСТВЕННОГО АГРАРНОГО УНИВЕРСИТЕТА. - 2014. - №. 1.