Maximal Clique Size Versus Centrality: A Correlation Analysis for Complex Real-World Network Graphs

The paper presents the results of correlation analysis between node centrality (a computationally lightweight metric) and the maximal clique size (a computationally hard metric) that each node is part of in complex real-world network graphs, ranging from regular random graphs to scale-free graphs. The maximal clique size for a node is the size of the largest clique (number of constituent nodes) the node is part of. The correlation coefficient between the centrality value and the maximal clique size for a node is observed to increase with increase in the spectral radius ratio for node degree (a measure of the variation of node degree in the network). As the real-world networks get increasingly scale-free, the correlation between the centrality value and the maximal clique size increases. The degree-based centrality metrics are observed to be relatively better correlated with the maximal clique size compared to the shortest path-based centrality metrics.