Quantum networks can display stronger connectivity than classical percolation predicts. This work studies how nonshortest paths contribute to quantum-network connectivity and develops tools for approximating concurrence percolation thresholds in large-scale quantum networks.