Analysis of clustering and degree index in random graphs and complex networks

Abstract The purpose of this paper is to analyze the degree index and the clustering index in dense random graphs. The degree index in our setup is a certain measure of degree irregularity whose basic properties are well studied in the literature, and the corresponding theoretical analysis in a random graph setup turns out to be tractable. On the other hand, the clustering index, based on a similar reasoning, is first introduced in this paper. Computing exact expressions for the expected clustering index turns out to be more challenging even in the case of Erdős–Rényi graphs, and our results are on obtaining relevant upper bounds. These are also complemented with observations based on Monte Carlo simulations. In addition to the Erdős–Rényi case, we also present a simulation-based analysis for random regular graphs, the Barabási–Albert model, and the Watts–Strogatz model.