
_START_ARTICLE_
介数中心性
_START_SECTION_
算法
_START_PARAGRAPH_
在一个网络图中，计算所有节点的介数中心性和接近中心性需要涉及到计算图中所有节点对的最短路径。如果使用改进的弗洛伊德算法需要花费的时间，其中需将两点间的最短路径修改为图中所有节点对之间的最短路径。 在稀疏网络图中，约翰逊算法或布兰德斯算法效率更高，都需要花费的时间。 在无权重网络图中，用布兰德斯的算法计算介数中心性需要花费的时间。_NEWLINE_计算一个网络图所有节点的介数中心性和接近中心性时，图是无向的且可以由环形边（节点自己连自己）或重复边（两个节点多条边）连接组成的。当专门处理网络图时，通常网络图是没有环形边或重复边而只有简单的关系（其中边表示两个节点之间的连接）在这种情况下，使用布兰德斯算法计算时需要将最终结果除以2，因为每个最短路径都被计算了两次。_NEWLINE_另一个算法通过引入超参数来控制探索与利用之间的平衡，从而涵盖了可计算测地线的Freeman介数与可计算所有路径的Newman介数。其时间复杂度为网络图中边的数量乘上节点的数量。_NEWLINE_中心性的概念也被扩展到评定一个团队的级别。 团队介数中心性表示通过一组节点连接非该组节点的测地线的比例。能计算所有节点介数中心性的布兰德斯算法被修改为计算一组具有相同渐近运行时间的节点的团队介数中心性。
_START_SECTION_
相关概念
_START_PARAGRAPH_
介数中心性与网络的连接度相关，介数高的节点如果在被移除以后有很大可能性使网络图不完全连接。_NEWLINE_路由介数中心性使介数中心性适用于任何循环较少的简单路径定义方案而不局限于最短路径标准。