Lean premixed combustors are highly susceptible to lean blowout flame instability, which can cause a fatal accident in aircrafts or expensive shutdown in stationary combustors. However, the lean blowout limit of a combustor may vary significantly depending on a number of variables that cannot be controlled in practical situations. Although a large literature exists on the lean blowout phenomena, a robust strategy for early lean blowout detection is still not available. To address this gap, we study a relatively unexplored route to lean blowout using a nonlinear dynamical tool, the recurrence network. Three recurrence network parameters: global efficiency, average degree centrality, and global clustering coefficient are chosen as metrics for an early prediction of the lean blowout. We observe that the characteristics of the time series near the lean blowout limit are highly dependent on the degree of premixedness in the combustor. Still, for different degrees of premixedness, each of the three recurrence network metrics increases during transition to lean blowout, indicating a shift toward periodicity. Thus, qualitatively, the recurrence network metrics show similar trends for different degrees of premixing showing their robustness. However, the sensitivities and absolute trends of the recurrence network metrics are found to be significantly different for highly premixed and partially premixed configurations. Thus, the results indicate that prior knowledge about (i) the degree of premixedness and (ii) the route to lean blowout may be required for accurate early prediction of the lean blowout. We show that the visible structural changes in the recurrence network can be linked to the changes in the recurrence network metrics, helping to better understand the dynamical transition to lean blowout. We observe the power law degree distribution of the recurrence network to break down close to the lean blowout limit due to the intermittent dynamics in the near-LBO regime.