文摘
The betweenness centrality (BWC) of a vertex is a measure of the fraction of shortest paths between any two vertices going through the vertex and is one of the widely used shortest path-based centrality metrics for the complex network analysis. However, it takes O(\(\vert V\vert ^{2}+\vert V\vert \vert E\vert )\) time (where V and E are, respectively, the sets of nodes and edges of a network graph) to compute the BWC of just a single node. Our hypothesis is that nodes with a high degree, but low local clustering coefficient, are more likely to be on the shortest paths of several node pairs and are likely to incur a larger BWC value. Accordingly, we define the local clustering coefficient-based degree centrality (LCCDC) for a node as the product of the degree centrality of the node and one minus the local clustering coefficient of the node. The LCCDC of a node can be computed based on just the knowledge of the two-hop neighborhood of a node and would take significantly lower time. We conduct an exhaustive correlation analysis and observe the LCCDC to incur the largest correlation coefficient values with BWC (compared to other centrality metrics under three different correlation measures) and to hold very strong levels of positive correlation with BWC for at least 14 of the 18 real-world networks analyzed. Hence, we claim the LCCDC to be an apt metric to rank the nodes or compare any two nodes of a real-world network graph in lieu of BWC.