Protected areas (PAs) are recognized as the flagship tool to offset biodiversity loss on Earth. Spatial conservation planning seeks optimal designs of PAs that meet multiple targets such as biodiversity representation and population persistence. Since connectivity between PAs is a fundamental requirement for population persistence, several methods have been developed to include connectivity into PA design algorithms. Among these, the eigenvalue decomposition of the connectivity matrix allows for identifying clusters of strongly connected sites and selecting the sites contributing the most to population persistence. So far, this method was only suited to optimize an entire network of PAs without considering existing PAs in the new design. However, a more cost-effective and realistic approach is to optimize the design of an extended network to improve its connectivity and thus population persistence. Here, we develop a flexible algorithm based on eigenvalue decomposition of connectivity matrices to extend existing networks of PAs while optimizing connectivity and population growth rate. We also include a splitting algorithm to improve cluster identification. The new algorithm accounts for the change in connectivity due to the increased biological productivity often observed in existing PAs. We illustrate the potential of our algorithm by proposing an extension of the network of ∼100 Mediterranean marine PAs to reach the targeted 10% surface area protection from the current 1.8%. We identify differences between the clean slate scenario, where all sites are available for protection, irrespective of their current protection status, and the scenario where existing PAs are forced to be included into the optimized solution. By integrating this algorithm to existing multi-objective and multi-specific algorithms of PA selection, the demographic effects of connectivity can be explicitly included into conservation planning.