Changes in vegetation patterns in semi-arid regions can precede the abrupt transition to bare soil. Here, complex network techniques are used to develop novel early-warning indicators for these desertification transitions. These indicators are applied to results from a local positive feedback vegetation model and are compared to classical indicators, such as the autocorrelation and variance of biomass time series. A quantitative measure is also introduced to evaluate the quality of the early-warning indicators. Based on this measure, the network-based indicators are superior to the classical ones, being more sensitive to the presence of the transition point.