A Pseudo-Boolean Approach to the Market Graph Analysis by Means of the P-Median Model

P. 77–89.

Goldengorin B. I., Kocheturov A. A., Pardalos P. M.

In the course of recent ten years algorithms and technologies for network structures analysis have been applied to financial markets among other approaches. The first step of such an analysis is to describe the considered financial market via the correlation matrix of stocks prices over a certain period of time. The second step is to build a graph in which vertices represent stocks and edge weights represent correlation coefficients between the corresponding stocks. In this paper we suggest a new method of analyzing stock markets based on dividing a market into several substructures (called stars) in which all stocks are strongly correlated with a leading (central, median) stock. The method is based on the p-median model a feasible solution to which is represented by a collection of stars. Our method is able to find an exact solution for relatively small-sized markets (less than 1000 stocks) and a high-quality solution for large-sized (many thousands of stocks) markets. We observed an important ``median nesting" property of returned solutions: the p leading stocks, or medians, of the stars are repeated in the solution for p+1 stars.

Keywords: p-median problem, pseudo-Boolean polynomial, financial markets

In book

Clusters, orders, trees: methods and applications. In Honor of Boris Mirkin's 70th Birthday

Vol. 92. , Berlin: Springer, 2014.