On the Degree Distribution of k-Connected Random Networks

摘要

In performance evaluations of communication and computer networks the underlying topology is sometimes modeled as a random graph. To avoid unwanted side effects, some researchers force the simulated topologies to be connected. Consequently, the resulting distribution of the node degrees does then no longer correspond to that of the underlying random graph model. Being not aware of this change in the degree distribution might result in a simulation pitfall. This paper addresses the question as to how serious this pitfall might be. We analyze the node degree distribution in connected random networks, deriving an approximation for large networks and an upper bound for networks of arbitrary order. The tightness of these expressions is evaluated by simulation. The analysis of the distribution for large networks is extended to k-connected graphs. Results show that specific restricted binomial distributions match the actual degree distribution better than the random graph degree distribution does. Nevertheless, the pitfall of not being aware of the change in the distribution seems not to be a serious mistake in typical setups with large networks.