In these last years, water utilities have recognized the importance of evaluating the safety of water distribution networks from potential risks of contamination, arising from accidents or from intentional or random attacks. Research literature has been recently focused on the optimal design of efficient detection systems, generally expressed as the problem of the optimal placement of monitoring sensors. In this paper, we introduce a methodology for calculating the distribution function of the number of potentially contaminated nodes, with the aim of providing an evaluation of vulnerability under adverse circumstances. Results show how such distribution is overall fitted by an exponential law, in its first part being better represented by a power-law. The comparison with an auto-similar, tree-like network shows how ‘far’ the behavior of a given system deviates from pure scale-freeness, and provides an alternative way of evaluating its robustness against accidental or intentional water contamination. Different networks can then be directly compared, in order to prioritize control measures and interventions for reducing vulnerability.