  The connectivity structure of a network can be very sensitive to removal of
certain nodes in the network. In this paper, we study the sensitivity of the
largest component size to node removals. We prove that minimizing the largest
component size is equivalent to solving a matrix one-norm minimization problem
whose column vectors are orthogonal and sparse and they form a basis of the
null space of the associated graph Laplacian matrix. A greedy node removal
algorithm is then proposed based on the matrix one-norm minimization. In
comparison with other node centralities such as node degree and betweenness,
experimental results on US power grid dataset validate the effectiveness of the
proposed approach in terms of reduction of the largest component size with
relatively few node removals.

Social and Information Networks;Networking and Internet Architecture