Banks have become increasingly interconnected via interbank credit and other forms of liabilities. As a consequence of the increased interconnectedness, the failure of one node in the interbank network might constitute a threat to the survival of large parts of the entire system. How important this effect of 'too-big-too-fail' and 'too-interconnected-too-fail' is, depends on the exact topology of the network on which the supervisory authorities have typically very incomplete knowledge. We propose a probabilistic model to combine some important known quantities (like the size of the banks) with a realistic stochastic representation of the remaining structural elements. Our approach allows us to evaluate relevant measures for the contagion after default of one unit (i.e. number of expected subsequent defaults, or their probabilities). For some quantities we are able to derive closed form solutions, others can be obtained via computational mean-field approximations.