  The notion of network connectivity is used to characterize the robustness and
failure tolerance of networks, with high connectivity being a desirable
feature. In this paper, we develop a novel approach to the problem of
identifying critical nodes in large-scale networks, with algebraic connectivity
(the second smallest eigenvalue of the graph Laplacian) as the chosen metric.
Employing a graph-embedding technique, we reduce the class of considered
weight-balanced graphs to spatial networks with uniformly distributed nodes and
nearest-neighbors communication topologies. Through a continuum approximation,
we consider the Laplace operator on a manifold (with the Neumann boundary
condition) as the limiting case of the graph Laplacian. We then reduce the
critical node set identification problem to that of finding a ball of fixed
radius, whose removal minimizes the second (Neumann) eigenvalue of the Laplace
operator on the residual domain. This leads us to consider two functional and
nested optimization problems. Resorting to the min-max theorem, we first treat
the problem of determining the second smallest eigenvalue for a fixed domain by
minimizing an energy functional. We then obtain a projected gradient flow that
converges to the set of points satisfying the KKT conditions and prove that the
only locally asymptotically stable critical point is the second eigenfunction
of the Laplace operator. Building on these results, we consider the critical
ball identification problem and construct a dynamics to converge asymptotically
to these points. Finally, we provide a characterization of the location of
critical nodes (for infinitesimally-small balls) as those points which belong
to the nodal set of the second eigenfunction of the Laplace operator.

Optimization and Control