应用中介中心性分析

图的中介中心性是一种基于最短路径的中心性度量。对于连通图中的每对节点，至少存在一条最短路径使得路径经过的边缘数量最小化。给定图中某个节点的中介中心性是指经过该节点的这些最短路径的数量。

定义为：

\[c_B(v) =\sum_{s,t \in V} \frac{\sigma(s, t|v)}{\sigma(s, t)}\]

其中\(V\)是节点集合，\(\sigma(s, t)\)是最短 \((s, t)\)路径的数量，而\(\sigma(s, t|v)\)是通过 除了\(s, t\)之外的某个节点\(v\)的那些路径的数量。 如果\(s = t\)，则\(\sigma(s, t) = 1\)，并且如果\(v \in {s, t}\)， 则\(\sigma(s, t|v) = 0\)

本教程将引导您完成计算图的介数中心性并进行可视化的过程。

生成一个图

开始时我们需要生成一个图：

import rustworkx as rx
from rustworkx.visualization import mpl_draw

graph = rx.generators.hexagonal_lattice_graph(4, 4)
mpl_draw(graph)

计算介数中心性

betweenness_centrality()函数可用于计算图中每个节点的中介中心性。

import pprint

centrality = rx.betweenness_centrality(graph)
# Print the centrality value for the first 5 nodes in the graph
pprint.pprint({x: centrality[x] for x in range(5)})

{0: 0.007277212457600987,
 1: 0.02047046385621779,
 2: 0.07491079688119466,
 3: 0.04242324126690451,
 4: 0.09205321351482312}

betweenness_centrality()的输出是一个 CentralityMapping，这是一个自定义的 映射类型，它将节点索引映射为浮点数形式的中心性值。这是一个映射而不是序列， 因为节点索引（以及边索引，这里不相关）在有删除操作的情况下不能保证是连续序列。

可视化介数中心性

现在我们已经找到了graph的介数中心性，接下来让我们进行可视化。 我们将使用计算得到的中心性为输出可视化中的每个节点上色：

import matplotlib.pyplot as plt

# Generate a color list
colors = []
for node in graph.node_indices():
    colors.append(centrality[node])
# Generate a visualization with a colorbar
plt.rcParams['figure.figsize'] = [15, 10]
ax = plt.gca()
sm = plt.cm.ScalarMappable(norm=plt.Normalize(
    vmin=min(centrality.values()),
    vmax=max(centrality.values())
))
plt.colorbar(sm, ax=ax)
plt.title("Betweenness Centrality of a 4 x 4 Hexagonal Lattice Graph")
mpl_draw(graph, node_color=colors, ax=ax)

另外，您可以使用graphviz_draw()：

from rustworkx.visualization import graphviz_draw
import matplotlib

# For graphviz visualization we need to assign the data payload for each
# node to its centrality value so that we can color based on this
for node, btw in centrality.items():
    graph[node] = btw

# Leverage matplotlib for color map
colormap = matplotlib.colormaps["magma"]
norm = matplotlib.colors.Normalize(
    vmin=min(centrality.values()),
    vmax=max(centrality.values())
)

def color_node(node):
    rgba = matplotlib.colors.to_hex(colormap(norm(node)), keep_alpha=True)
    return {
        "color": f"\"{rgba}\"",
        "fillcolor": f"\"{rgba}\"",
        "style": "filled",
        "shape": "circle",
        "label": "%.2f" % node,
    }

graphviz_draw(graph, node_attr_fn=color_node, method="neato")