Title: Correlation coefficient analysis: centrality vs. maximal clique size for complex real-world network graphs

Authors: Natarajan Meghanathan

Addresses: Jackson State University, Mailbox 18839, 1400 John R. Lynch Street, Jackson, Mississippi, MS 39217, USA

Abstract: The high-level contribution of this paper is correlation analysis between the centrality values observed for nodes (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. The real-world network graphs studied range from regular random network graphs to scale-free network graphs. The maximal clique size for a node is the size of the largest clique (in terms of the number of constituent nodes) the node is part of. We observe the degree-based centrality metrics such as the degree centrality and eigenvector centrality to be relatively better correlated with the maximal clique size compared to the shortest path-based centrality metrics such as the closeness centrality and betweenness centrality. As the real-world networks get increasingly scale-free, we observe the correlation between the centrality value and the maximal clique size to increase.

Keywords: assortativity index; centrality; maximal clique size; network graphs; random networks; scale-free networks; correlation coefficient analysis.

DOI: 10.1504/IJNS.2016.073560

International Journal of Network Science, 2016 Vol.1 No.1, pp.3 - 27

Received: 29 Jan 2015
Accepted: 08 Mar 2015
Published online: 12 Dec 2015 *