Machine learning dynamical phase transitions in complex networks

Recent years have witnessed a growing interest in using machine learning to predict and identify critical dynamical phase transitions in physical systems (e.g., many-body quantum systems). The underlying lattice structures in these applications are generally regular. While machine learning has been adopted to complex networks, most existing works concern about the structural properties. To use machine learning to detect phase transitions and accurately identify the critical transition points associated with dynamical processes on complex networks thus stands out as an open and significant problem. Here we develop a framework combining supervised and unsupervised learning, incorporating proper sampling of training data set. In particular, using epidemic spreading dynamics on complex networks as a paradigmatic setting, we start from supervised learning alone and identify situations that degrade the performance. To overcome the difficulties leads to the idea of exploiting confusion scheme, effectively a combination of supervised and unsupervised learning. We demonstrate that the scheme performs well for identifying phase transitions associated with spreading dynamics on homogeneous networks, but the performance deteriorates for heterogeneous networks. To strive to meet this challenge leads to the realization that sampling the training data set is necessary for heterogeneous networks, and we test two sampling methods: one based on the hub nodes together with their neighbors and another based on $k$-core of the network. The end result is a general comprehensive machine learning framework for detecting phase transition and accurately identifying the critical transition point, which is robust, computationally efficient, and universally applicable to complex networks of arbitrary size and topology. Extensive tests using synthetic and empirical networks verify the virtues of the articulated framework, opening the door to exploiting machine learning for understanding, detection, prediction, and control of complex dynamical systems in general.

Figure 1

Illustration of the neural network structure in our deep learning framework. Labeled data set is used as input and the learning process as illustrated is supervised. There is a hidden layer of 100 neurons and a single-neuron output layer to generate the probability of the identified phase of the dynamical process on a complex network.

Figure 2

Identifying phase transition on a random regular network through supervised learning. (a) The output of the neural network averaged over a test set versus the effective infection rate $\lambda$ for different preset threshold values of the SIS spreading dynamics. For relatively smaller (larger) value of $\lambda$ than the preset threshold value as marked by a vertical dashed line, the corresponding label will be zero (1). (b) The relationship between the identified and preset threshold values. The neural network's prediction depends on the preset threshold value. The structural parameters of the random regular network are $N=1000$ and $〈k〉=10$.

Figure 3

Identification of phase transition through supervised learning with truncated training data set on a random regular network. (a) Threshold of phase transition identified via supervised learning with truncated data sets. Data points in the yellow area are artificially removed from the training set and the neural network makes the judgment only by learning the data in the blue area. The three curves show that the output shifts when the center $\lambda$ value of the training set changes from 0.1 to 0.1095. (b) Robustness against asymmetry of data set. Shown is the relationship between the predicted threshold value and the center of the training set. When the range of the training set is shifted while keeping the number of data points in the training set unchanged, the identified threshold will change.

Figure 4

Robustness of threshold identification via supervised learning against noise. For a random regular network, (a) the output curve (output of the neural network versus the effective infection rate) under different noisy inputs. Noise has little effect on the curve. (b) The relationship between the identified threshold and the error rate of the training labels. The predicted value oscillates about the output value with zero noise and exhibits a slightly upward trend as the labeling error rate is increased.

Figure 5

Schematic illustration of the working of confusion scheme to detect a phase transition and to identify the transition point. For a range of tentatively assigned threshold values, the curve of classification accuracy of supervised learning versus the threshold value will exhibit a $\mathsf{W}$ shape if there is a phase transition associated with epidemic dynamics on the network. The location of the middle peak gives an accurate prediction of the true threshold value. If the network dynamics do not exhibit a phase transition, then the curve would exhibit a $\mathsf{U}$ shape (see text for a detailed reasoning).

Figure 6

Learning phase transition by confusion scheme on homogeneous and heterogeneous networks. (a) For a random regular network of size $N=1000$ and average degree $\langle k\rangle =10$, the confusion scheme generates an overall $\mathsf{W}$-shaped curve of the classification accuracy versus the assumed threshold value. The peak of susceptibility is at 0.105, as indicated by the green vertical line (the same legend holds below). (b) For a scale-free network of size $N=1000$ and structural parameter $m=m_0=3$ generated by the preferential attachment rule, the neural network fails to yield a $\mathsf{W}$-shaped accuracy curve: The accuracy has a $\mathsf{U}$ shape. (c) For a scale-free network of parameters $N=10000$ and $m=m_0=3$, the accuracy curve obtained by incorporating a hub sampling procedure into the confusion scheme. In this case, the accuracy curve exhibits a $\mathsf{W}$ shape, rendering detectable the phase transition. The transition point can also be identified accurately. (d) For scale-free networks generated by the uncorrelated configuration model of size $N=10000$ with the value of the power-law exponent in the range $\gamma \in [2.0,3.0]$, output of the confusion scheme, where the solid circles correspond to the maximum susceptibility, the triangles and crosses indicate the predictions given by neural network incorporating two sampling methods: hub-and-neighbors and max-$k$-core, respectively.

Figure 7

Performance analysis of the confusion scheme for spreading dynamics on heterogeneous networks. The network is scale free with the degree exponent $\gamma =2.2$. Symmetry analysis of accuracy incorporating (a) hub-and-neighbors and (b) max-$k$-core sampling methods. Different markers indicate different ranges of the training set. [(c) and (d)] Robustness analysis of the two sampling methods. Solid circles, crosses, and triangles represent the results for error rates of $2\%$, $10\%$, and $20\%$, respectively.

Figure 8

Test on two representative real-world networks. [(a) and (b)] Output of the neural network under supervised learning incorporating max-$k$-core sampling for the corporative association for internet data analysis (CAIDA) and Brightkite data sets, respectively. Circles and triangles correspond to the results with max-$k$-core and hub-and-neighbors sampling, respectively. [(c) and (d)] Accuracy curves of executing the confusion scheme for the CAIDA and Brightkite data sets, respectively. For the CAIDA (Brightkite) network, the size of the subgraph sampled is 2628 (1135) with hub-and-neighbors sampling and 64 (154) with max-$k$-core sampling. Both sampling methods give essentially the same accuracy result.

Figure 9

Performance analysis with small data set. (a) Barabasi-Albert model with $N=1000$ and $m=m_0=3$. (b) U.S. power grid network with 4941 nodes. In each panel, dotted, dashed, and dash-dot curves, respectively, represent the susceptibility values of data set with 10, 50, and 100 realizations for each $\lambda$, and blue circles, orange crosses, and green triangles, respectively, represent output values of data set with 10, 50, and 100 configurations for each $\lambda$ by using confusion scheme.