A random graph model defines a distribution over graphs, and this distribution induces a distribution over certain measurements of graphs, such as the Von Neumann entropy. Interestingly, the Von Neumann entropy of an empirical network typically has a very small probability to be drawn from the distribution over the Von Neumann entropy of graphs generated by the Erdős–Rényi random graph model with the same number of vertices and edges. It has been shown that Erdős–Rényi random graph model may be inappropriate for modeling certain properties of real-world networks such as the small-world property [22] and scale-free property [2], and the Von Neumann entropy provides yet another, complementary way to measure how real-world networks differ from Erdős–Rényi random graphs. Subjecting the network to a random rewiring process offers another approach to measure how far it is from an Erdős–Rényi random graph. In particular, it can be shown using Markov chain theory that the ensemble of networks after many non-degree-preserving rewirings limits to the ensemble of Erdős–Rényi random graphs. In this paper, we develop a connection between these two approaches by studying the Von Neumann entropy of networks undergoing rewiring. More specifically, we are interested in the number of rewiring times needed until the Von Neumann entropy of the rewired graph is larger than some quantile of the distribution over the Von Neumann entropy of Erdős–Rényi random networks, as it can be used to quantify the difference between any given network and networks generated by the Erdős–Rényi random graph model. However, performing a large number of simulations to compute the expected number of rewiring times is not computationally efficient, and we apply matrix perturbation methods to derive an estimation by using a small perturbation to the adjacency matrix to approximate one random rewiring of a graph. The estimation can be computed directly for a given network without performing any numerical simulation.