中心性算法

Ⅰ betweeness（中间中心性或中介中心性）

中间中心性，即betweenness，是基于节点在图中作为其他节点之间最短路径中必经路径的次数来衡量节点的重要性。这一概念建立在最短路径搜索算法之上，如Dijkstra算法，通过扩展到全图，即对每个节点执行一次Dijkstra算法，然后使用并行计算来提高效率。最常用的是所有点对最短路径算法（APSP algorithm），用于计算图中任意两点间的最短路径。在图中，桥节点（如大圆中的女生或渣男角色）在连接独立社交圈中起着关键作用，其通过的最短路径数量往往较多，因为这些独立圈间直接连接较少，通过桥节点实现连接。中间中心性定义为：对于每个节点u，计算所有节点s和t之间最短路径总数p，以及通过节点u的最短路径数量p(u)。计算过程涉及遍历所有节点，找出通过它们的最短路径，计算最短路径占所有可能最短路径的百分比，最后将这些值相加得到节点的中间中心性得分。

在某些特定场景，如涉及非法交易的黑中介，中间中心性计算显示出较高的效率。在这种情况下，黑中介作为不同用户群体（如国外教授A、国内学生C和黑中介B）之间的连接点，其中间中心性得分显着高于其他参与者。由于黑中介在非法业务中扮演的关键角色，它连接了原本独立的社交圈，使得在图中其作为关键节点的重要性突出。

原中间中心性算法计算复杂度高，难以在大型图中实现高效计算。为解决这一问题，出现了近似中间中心性计算方法，如RA-Brandes算法。该算法通过考虑节点的子集而非所有可能的节点对，以减少计算复杂度。在Neo4j中，RA-Brandes算法用于提高中间中心性计算的效率。此外，还需注意，中间中心性算法在非联通图中的应用存在误差问题。解决方法包括分别计算每个连通分量的中间中心性，对计算结果进行惩罚以考虑不同连通分量的节点数量大小，或过滤掉节点数量较少的连通分量，对每个节点数量较多的连通分量进行独立分析。

在具体实现方面，网络分析库networkit提供了两种近似中间中心性计算方法。其中一种方法涉及计算图的直径和一个超参数r，然后在每次迭代中随机采样节点对，并计算它们之间的最短路径集合。通过这一过程，算法估计了每个节点的中间中心性得分。第二种方法则直接关注于提高中间中心性计算的效率和准确性，通过优化采样过程和迭代算法，提供了更精确的中间中心性估计。