Major cyber attacks against the cyber networks of organizations has become a common phenomenon nowadays. Cyber attacks are carried out both through the spread of malware and also through multi-stage attacks known as hacking. A cyber network can be represented directly as a simple directed or undirected network (graph) of nodes and arcs. It can also be represented by a transformed network such as the attack graph which uses information about network topology, attacker profile, and existing vulnerabilities to represent all the potential attack paths from readily accesible vulnerabilities to valuable target nodes. Then, interdicting or hardening a subset of arcs in the network naturally maps into deploying security countermeasures on the associated devices or connections. In this dissertation, we develop network interdiction models and algorithms to optimally select a subset of arcs which upon interdiction minimizes the spread of infection or minimizes the loss from multi-stage attacks. In particular, we define four novel network connectivity-based metrics and develop interdiction models to optimize the metrics. Direct network representation of the physical cyber network is used as the underlying network in this case. Two of the interdiction models prove to be very effective arc removal methods for minimizing the spread of infection. We also develop multi-level network interdiction models that remove a subset of arcs to minimize the loss from multi-stage attacks. Our models capture the defenderattacker interaction in terms of stackelberg zero-sum games considering the attacker both as a complete rational and bounded rational agents. Our novel solution algorithms based on constraint and column generation and enhanced by heuristic methods efficiently solve the difficult multi-level mixed-integer programs with integer variables in all levels in reasonable times.