On connectivity of conditional configuration graphs under destruction (Q6159088)

The configuration model for random graphs is the most robust model that permits the study of a random model for graphs with a given degree pattern. These are sometimes more relevant in contrast to the ubiquitous Erdős-Renyi model as many networks in real life (social networks, telecommunication networks, etc) are better modeled by `power-law' graphs. More precisely, suppose \(\tau>1\) is a real parameter, and consider the random variable \(\xi\) whose distribution is given by \(\mathbb{P}_{\tau}(\xi=k)=k^{-\tau}-(k+1)^{-\tau}\), for \(k\in\mathbb{N}\). Now consider the configuration model (of a multigraph with loops) with \(N\) vertices and degrees \(\xi_1,\ldots,\xi_N\) where \(\xi\) are i.i.d to the distribution \(\mathbb{P}_{\tau}\) described above. One of the main interests in these models is to see when these graphs are connected, and if so, how many `knocks' they can take before losing connectivity. In other words, suppose we sequentially delete vertices from a \(\mathbb{P}_{\tau}\)-random graph. The question of interest is: How many steps of deletions can we make before we end up with a graph that is no longer connected? The vertices to be deleted are again chosen randomly, and through one of two means; pick the largest degree vertex, or pick a random vertex. The current paper investigates these questions through some computer simulations, with a regression model. The author shows the results of these simulations for varying values of \(\tau\) and shows regression models for the probability of disconnecting the graph after deleting \(r\%\) of the vertices, under both these models of vertex selection for deletion.