A comprehensive analysis of the correlation between maximal clique size and centrality metrics for complex network graphs

AbstractWe seek to identify one or more computationally light-weight centrality metrics that have a high correlation with that of the maximal clique size (the maximum size of the clique a node is part of) - a computationally hard measure. In this pursuit, we compute three well-known measures of evaluating the correlation between two datasets: Product-moment based Pearson's correlation coefficient, Rank-based Spearman's correlation coefficient and Concordance-based Kendall's correlation coefficient. We compute the above three correlation coefficient values between the maximal clique size and each of the four prominent node centrality metrics (degree, eigenvector, betweenness and closeness) for random network graphsand scale-free network graphs as well as for a suite of ten real-world network graphs whose degree distribution ranges from random to scale-free. We also explore the impact of the operating parameters of the theoretical models for generating random networks and scale-free networks on the correlation between maximal clique size and the centrality metrics