\section{INTRODUCTION}

Network science has been used to predict many natural and technological phenomena. Examples include, the evolution of a scientist's impact \cite{sinatra_quantifying_2016}, forecast disease epidemics \cite{eubank_modelling_2004,colizza2006role,brockmann_hidden_2013}, predict the spatial development of urban areas~\cite{li_simple_2017} and 
forecast climate extreme events \cite{ludescher_very_2014,boers_prediction_2014,meng_percolation_2017,meng_forecasting_2018}.
Network approach demonstrated its potential as a useful tool in the study of real world systems, such as, physics, biology, and social systems \cite{newman2010networks,cohen2010complex,zhao_inducing_2013}. Recently,  a network approach has been applied to describe the instability in financial systems~\cite{bardoscia_pathways_2017}, and to study the relationship between the structure of the financial network and the likelihood of systemic failures due to contagion of risk~\cite{miura_effect_2012,acemoglu_systemic_2015}. 



In the present study, we use text-based analysis of SEC Form 10-K product descriptions to 
construct the network of product similarity between firms. The firms are regarded as network nodes, and the level of similarity between
the product descriptions of different firms represents the network links (strength). The 10-K product descriptions are obtained from
the Securities Exchange Commission (SEC) Edgar website (\url{https://www.sec.gov/}). We then analyze the topological structure of the network, and determined how measures such as, clustering coefficient
correlate with membership in the Standard \& Poor's 500 (S\&P 500). Furthermore, we also analysed the $K$-shell structure of the network \cite{carmi_model_2007,kitsak_identification_2010} and find that it reveals that firms in more outer shells have higher risk to collapse (or merge). Furthermore, we combine the network structure and machine learning methods to predict both the successful and collapsed firms. We find that the forecasting rates by using our combined method are significantly higher than random guessing and other methods \cite{breiman_random_2001}. 




\section{Data}
\subsection{Product Similarity Data}
In this study, we use text-based analysis of 10-K product descriptions to obtain the product similarity between firms, representing the links.
For any two firms $i$ and $j$, we have a product similarity, which is a real value in the
interval [0,1] describing the similarity of words used by firms $i$ and $j$ in their 10-K forms.
To compute the  ``product similarity'' between two firms using the basic cosine similarity method ~\cite{hoberg_product_2010,Hoberg2016jpe},
We first build the database for each year by taking the list of unique words used in all product descriptions in that year.
We then take the text from each firm's product description and construct a binary $N$-vector summarizing its word usage. A given element of this
$N$-vector is 1 if the given dictionary word is used in firm $i$'s product description. For each firm $i$, we denote this binary
$N$-vector as $\vec{P_{i}}$. We define the normalized vector $\vec{V_i}$ as,
\begin{equation}
\vec{V_{i} }= \frac{\vec{{P_{i}}}}{\sqrt{\vec{P_{i}}\cdot\vec{ P_{i}}}}.
\label{eqa1}
\end{equation}

To measure the similarity of products of firms $i$ and $j$, we compute the dot product of their normalized vectors, which is then the basic cosine similarity:

\begin{equation}
w_{i,j} = \frac{\vec{V_{i}}\cdot\vec{V_{j}}}{\mid V_{i} \mid \mid V_{j} \mid}.
\label{eqa2}
\end{equation}
In this study, we use 18 years (from 1996 to 2013) of data. For a more detailed description see Ref. \cite{hoberg_product_2010}.

\subsection{External Financial Data}
Apart from the product similarity data, we also compile some external information to construct financial variables. We download the daily closing price of the S\&P 500 index from the Center for Research in Security Prices (CRSP) (\url{ http://www.crsp.com/}). This time-series  can be used to measure the overall market dynamics. Several firm-specific variables are also taken to control the range of observed firm traits. Specifically, firm size is assumed to be the total market capitalization following as suggested in Ref. \cite{fama1992cross}; the book-to-market ratio is the book value of equity over the market value of equity and measures a firm's growth opportunities; leverage is a measure of capital structure defined by the ratio of long-term debt and other debt (current liabilities) to the sum of long-term debt, debt in current liabilities, and stockholders' equity; profitability is defined as income before extraordinary items over lagged total assets; prior year return is the return of the stock in the past year; investment is the year-over-year percent growth in total assets following \cite{cooper2008asset}; liquidity is a measure of firm liquidity found using reference \cite{amihud2002illiquidity}; and the Altman Z-score is a measure of default risk according to reference \cite{altman1968financial}. The data can be downloaded from the Compustat database (\url{http://www.compustat.com}).

\section{Methods}
\subsection{Product Similarity Network}
For each year, we construct a weighted undirected network based on the product similarity data where each firm or company is a node and the links have a given strength, $w$, representing the level of similarity between pairs of nodes.  The links are thresholding such that only links with a weight greater than significant value are kept in the network. Here, we only consider the similarity values that are above $10^{-4}$.  This threshold is calculated  based on the coarseness of the three-Digit Standard Industrial Classification (SIC). The level of coarseness thus matches 
that of three digit SIC codes, as both classifications result in the same number of firm pairs being deemed related \cite{hoberg_product_2010}.  We present a specific product similarity network for the year 2012 in Fig.~\ref{fig1}.

\subsection{Network topology measures for machine learning}
Multiple network topological measures have been used to predict the future gain of companies, as well as the probability of their collapse. The general approach is based on methods described in Rosen \textit{et. al} \cite{rosen_topological_2016} and Naaman \textit{et. al} \cite{naaman_edge_nodate}. In brief, a vector representing a set of topological features has been computed for each node, and this vector was then used in a machine learning framework as decribed below. The following features were used for the topological network attribute vector (NAV):
\begin{itemize}
\item Degree (number of neighbors).
\item Betweenness Centrality \cite{everett_centrality_1999}. Betweenness is a centrality measure of a node (or a link). It is defined as the number of shortest paths between all vertex pairs that pass through the node.
\item Closeness Centrality \cite{sabidussi_centrality_1966}. Closeness is a centrality measure of a node (or a link) defined as the average length of the shortest path between the vertex and all other vertices in the graph.
\item Distance distribution moments. We compute the distribution of distances from each node to all other nodes using a Dijkstra's algorithm \cite{dijkstra_note_1959}, and then take the first and second moments of this distribution. 
\item Flow \cite{rosen_directionality_2014}. We define the flow a node as the ratio between the directed and undirected distances between this node and all other nodes. 
\item Network motifs \cite{milo_network_2002}. Network motifs are patterns of small connected sub-graphs. We use an extension of the Itzchack  algorithm \cite{itzhack_optimal_2007} to calculate motifs. For each node, we compute the frequency of each motif in which this node participates. Note that the above algorithm is an extension of the concept to undirected graphs. 
\item  $K$-core \cite{batagelj_fast_2011}.  The $K$-core of a network is a maximal subgraph that contains only vertices with degree $k$ or more. Equivalently, it is the subgraph of $G$ formed by recursively deleting all nodes of degree less than $k$.

\end{itemize}
\subsection{Machine learning}
We computed for each node an NAV as described above. All nodes within a given year were then split into a training set composed of $70$\% of nodes and a test set composed of the remaining $30$\%. Each node was also associated with two binary valued tags representing whether the company collapsed in the following year and if it was within the top $5$\% of returns in the following year. The values of the tags were then learned using either a Random Forest (RF) \cite{ho_random_1995} classifier and a neural network with two internal layers. The Random Forest was trained with $200$ trees and a balanced loss matrix, where the error cost was inversely proportional to the training fraction of the appropriate tag (0 or 1). The trees were limited to $10$ samples per leave. All other parameters were the default parameters of the Matlab Treebagger. 
The neural network had a rectified linear unit (ReLU) activation functions and a cross entropy loss function.
The solver used was an ADAM optimizer \cite{kingma_adam:_2014}. L2 regularization has been also applied.  All other parameters were as in the default of the Keras python library: \url{https://keras.io}.

\section{Results}

\begin{figure}
\begin{centering}
\includegraphics[width=1\textwidth]{screenshot1.eps}
\caption{\label{fig1} A typical snapshot of the product similarity network for the year 2012.  The system size is $N = 3925$, average degree is $\<k\> = 94.78$. Different colors represent different shells.}
\par\end{centering}
\end{figure}

We first consider the probability density function (PDF) of links' strength, $p(w)$, for each network (year). The results for six specific years are shown in Fig.~\ref{fig2} (a). We find that $p(w)$ is robust and approximately follows an exponential distribution. The values of product similarity can reflect the product market synergies and competition of mergers and acquisitions \cite{hoberg_product_2010}, i.e., higher $w$ may mean the two firms are highly competitive or in cooperative relations. To better understand and explain the exponential distribution, we develop a competitive-cooperative model. For each node (firm) $i$, we set a score $x_{i}$, which follows a general mathematical function $f(x)$.
We define the weight/strength relation between nodes $i$ and $j$ as,
\begin{equation}
w_{i,j} = -\Lambda \log[1 - |x_{i} -x_{j}|],
\label{eqa3}
\end{equation}
where $|x_{i} -x_{j}|$ is the absolute difference between $i$ and $j$, i.e., high values indicating a large difference or low similarity. 
$\Lambda$ is a constant used to guarantee that $w_{i,j}$ is between $[0,1]$. If we assume that $f(x)$ follows an uniform random distribution, we can show in our model that $p(w)$ follows an exponential distribution (see more details in SI \cite{SI}).
Indeed,  Fig.~\ref{fig2}(b) shows our Monte Carlo simulations and theoretical results of the model, where we find that $p(w)$ agrees well with the real data. It suggests that our competitive-cooperative model can be used to accurately simulate/describe the real product similarity network. 




\begin{figure}
\begin{centering}
\includegraphics[width=1\textwidth]{Fig1.eps}
\caption{\label{fig2} The probability distribution functions of links weights (a) for real networks of different years, the dashed line is a fitting line using an exponential distribution; (b) Simulation and theoretical results for our competitive-cooperative model.}
\par\end{centering}
\end{figure}

Next, we consider two basic parameters to reveal the structure of the network: the weighted degree and clustering coefficient \cite{watts_collective_1998}. The weighted degree for node $i$ is defined as,
\begin{eqnarray}
s_{i} = \sum\limits_{j=1}^{N} a_{ij} w_{ij},
\label{eqa4}
\end{eqnarray}
where $a_{ij}$ is the adjacency matrix and $s_i$ quantifies the strength of node $i$ in terms of the total weight of its connections. In the case of the product similarity networks, it reflects the importance or impact of a firm $i$ in the network. We find, see Fig.~\ref{Fig:S1}, that the strength $s(k)$ of nodes with degree $k$ increases with $k$ as,
\begin{eqnarray}
s \sim k^{\beta}.
\label{eqa5}
\end{eqnarray}
We find that the
power-law fit for the real data gives an exponent $\beta \approx 1.5$. This value implies that the strength of nodes grows faster than their degree, i.e., the weight of edges belonging to highly connected nodes tends to have a higher value.
We notice that the universal power--law relationship is also observed in other real networks, e.g., the world-wide airport network, even with the same value of $\beta$ \cite{barrat_architecture_2004}.

For weighted networks, the clustering coefficient for node $i$ is defined as the geometric average of the subgraph edge weights \cite{saramaki_generalizations_2007},
\begin{eqnarray}
c_{i}  = \frac{1}{k_{i}(k_{i}-1)} \sum\limits_{j,k} (\hat{w}_{i,j} \hat{w}_{i,k} \hat{w}_{j,k})^{1/3},
\label{eqa6}
\end{eqnarray}
where the edge weight is normalized by the maximum weight in the network, $\hat{w}_{i,j} = w_{i,j}/max(w)$. The average clustering coefficient is $
C  = \frac{1}{N} \sum\limits_{i=1}^{N} c_{i}$, representing the presence of triplets in the network.
Fig.~\ref{fig3} (a) shows the dynamical evolution of $C$ with time (years), 
Fig.~\ref{fig3} (b) shows the S\&P 500 Index. We find that the behavior of $C$ (1 year ahead) and the S\&P 500 Index is highly correlated (see Fig.~\ref{Figs:S2}). In particular, we can see 3 local maxima $C$ (labeled by dashed blue lines) and 3 local minima S\&P 500 (labeled by red lines with  arrows), which stands for three financial crisis: the 1997-1998 Asian Financial Crisis, the 2002 dotcom bubble  and the 2008 global financial crisis. The maxima values are always one year before the minima. This suggests that our network 
index $C$ might be able to help in forecasting the following year's stock market returns.

\begin{figure}
\begin{centering}
\includegraphics[width=1\textwidth]{Fig2.eps}
\caption{\label{fig3} (a) Evolution of the clustering coefficient $C$ with years. (b) The evolution of the S\&P 500 Index.}
\par\end{centering}
\end{figure}




Given the relation between the evolved topology of the network of market, we tested whether the network contains enough information to predict at the single node level whether the company represented by this node will collapse or make exceptional gains in the following year.  We define the systemic risk as the disappeared firms (bankrupt or mergers and acquisitions) in the next year and the systemic return as the firms with the highest stock-market return ratio in the next year (we choose here the top $5\%$ of firms). Note that merger and bankrupt are obviously different. However,
most such events are bankruptcy and merger events. Thus, the events can be approximated as
bankruptcy.


To further show that network topology matters, we next analyze the $K$-shell structure of the network and find that the $K$-shell method is quite useful for predicting well above random, the disappeared firms. We present 
the receiver operating characteristic curve (ROC) using the $K$-shell method for predicting the disappeared firms of the 2012 network in Figs.~\ref{Figs:S3}. The area under the ROC curve (AUC) is significantly higher than the random case for all years (shown in Fig.~\ref{Figs:S4}). In particular, firms in the lower shells have higher market risk ratio. A possible reason is that the nodes in lower shells in the network are very fragile with higher risk. We present the scatter plot of risk ratio, $\rho$ (the ratio of disappeared firms at each shell), as a function of $K$-shell, see Fig.~\ref{Figs:S5} for three specific years, 1996, 2003 and 2012. Our results reveal that firms in more outer shells have higher risk to collapse.


Next a combined topological approach was tested to predict the same tags (collapsed or top) using a large set of topological measures and a Random Forest classifier. The combined features approach \cite{rosen_topological_2016} significantly  outperformed the $K$-Core based classification ( Fig.~\ref{fig5}). 
For both collapsed and top companies, we find that the topological information of our network provides significantly better predictions than the random case (the AUC is shown in Fig. \ref{fig5} upper and middle plots) for all 17 years. We also compared the AUC of machine learning using the network topology to the logistic regression based on the standard financial measures (non-network information): firm size, book-to-market ratio, leverage, profitability, prior year return, investment, liquidity, and Altman Z-score. The results are  shown in Fig. \ref{fig5} upper and middle plots.



\begin{figure}
\begin{centering}
\includegraphics[width=1\textwidth]{RF_Reg_fig.eps}
\caption{\label{fig5} (Upper and Middle) Comparison of AUC for logistic regression on external features and Random Forest Classifier on topological features for both collapsed and top companies. (Bottom) The gain in AUC for Random Forest on combined topological and external features for the collapsed and top companies.}
\par\end{centering}
\end{figure}



The topological classifier is approximately of equal quality and often outperforms the logistic regression methods (Fig. \ref{fig5} upper and middle plots). Moreover when topological features are combined with the external features, the precision accuracy of RF method is significantly higher in almost all years and in both categories (see gain AUC in Fig. \ref{fig5} bottom plot). This highly suggests that the network topological information plays a prominent role in the prediction of future collapsed and top companies, it can be complementary to the traditional logistic regression methods. 

\section{SUMMARY}
In summary, we developed a combined network and machine learning algorithm to predict both collapsed and top companies in the financial market. Our network is based on the 10-K product similarities. We find that multiple topological measures inherent in our networks can serve as good precursors for machine learning approach (Random Forest). The forecasting rates using our method are often higher than using well-known logistic regression techniques. Moreover, when combining the external features and network topological measures, we find that the accuracy of the machine learning is significantly higher in almost all years and in both categories (collapsed and top gain).
The proposed method and analysis can provide
a new perspective for prediction of individual companies in the financial product markets and can potentially be used as a template to study other financial systems.



\section*{Acknowledgements}
We acknowledge the Italy-Israel project OPERA, the Israel-Italian collaborative project NECST, the Israel Science Foundation, ONR, Japan
Science Foundation, BSF-NSF, and DTRA (Grant no.
HDTRA-1-10-1-0014), EPICC for financial support.
PIK is a Member of the Leibniz Association.
