A computationally lightweight and localized centrality metric in lieu of betweenness centrality for complex network analysis
详细信息 查看全文
- 作者：Natarajan Meghanathan
- 关键词：Betweenness centrality ; Degree centrality ; Local clustering coefficient ; Correlation coefficient ; Complex network graphs
- 刊名：Vietnam Journal of Computer Science
- 出版年：2017
- 出版时间：February 2017
- 年：2017
- 卷：4
- 期：1
- 页码：23-38
- 全文大小：2810KB
- 刊物类别：Information Systems and Communication Service; Artificial Intelligence (incl. Robotics); Computer Ap
- 刊物主题：Information Systems and Communication Service; Artificial Intelligence (incl. Robotics); Computer Applications; e-Commerce/e-business; Computer Systems Organization and Communication Networks; Computa
- 出版者：Springer Berlin Heidelberg
- ISSN：2196-8896
- 卷排序：4
文摘
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.