Node Centrality Inference via Hypothesis Testing

ABSTRACT Central nodes, also known as vital or critical nodes, play a unique role in networks of various domains. To date, numerous centrality evaluation methods have been proposed to identify central nodes from different types of networks. However, most of existing methods did not address this issue from a rigorous significance testing perspective. As a result, it is hard for us to judge whether an identified central node is true or not and control the quality of reported nodes in a statistically sound manner. In this paper, we propose a centrality evaluation method based on hypothesis testing, where the test statistic is the degree sum of the neighbors of the node. We further derive an analytical p value and its upper bound under the Erdös–Rényi model, which can be employed as the centrality score for vital node recognition. To demonstrate the effectiveness of our method, extensive experiments are conducted on both simulated and real networks. The experimental results show that (1) our testing‐based centrality measure in terms of p value is capable of distinguishing central nodes from non‐central ones effectively and (2) our method is able to identify central nodes more accurately than those classic centrality measures and state‐of‐the‐art (SOTA) centrality evaluation methods.