Network analysis under perturbations
András Faragó · 2012
It is a frequent situation that the idealized assumptions on which a network model is built do not hold with sufficient accuracy in practice. This motivates us to investigate what happens if some perturbations are introduced into the idealized conditions of a network model. Our goal is to find a general way to preserve most of the results from the analysis in situations when the conditions deviate from the ideal ones that were assumed in the derivation. Surprisingly, our goal can be achieved in a model-independent way. We present a method that does not depend on the specifics of a single model; rather, it applies to many. We illustrate the power of the method by applying it to two examples: (1) a random wireless network topology model, based on random unit disk graphs; and (2) a random web graph model that can exhibit any node degree distribution, and allows, among other things, to derive a closed formula for the average hop-distance in the network.