更改
跳到导航
跳到搜索
第118行：
第118行： + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
→中介中心性/中间中心性
===中介中心性/中间中心性===
===中介中心性/中间中心性===
Betweenness is a centrality measure of a vertex within a graph (there is also edge betweenness, which is not discussed here). Betweenness centrality quantifies the number of times a node acts as a bridge along the shortest path between two other nodes. It was introduced as a measure for quantifying the control of a human on the communication between other humans in a social network by Linton Freeman[21] In his conception, vertices that have a high probability to occur on a randomly chosen shortest path between two randomly chosen vertices have a high betweenness.
The betweenness of a vertex
v
v in a graph
G
:=
(
V
,
E
)
G:=(V,E) with
V
V vertices is computed as follows:
For each pair of vertices (s,t), compute the shortest paths between them.
For each pair of vertices (s,t), determine the fraction of shortest paths that pass through the vertex in question (here, vertex v).
Sum this fraction over all pairs of vertices (s,t).
More compactly the betweenness can be represented as:[22]
C
B
(
v
)
=
∑
s
≠
v
≠
t
∈
V
σ
s
t
(
v
)
σ
s
t
C_B(v)= \sum_{s \neq v \neq t \in V}\frac{\sigma_{st}(v)}{\sigma_{st}}
where
σ
s
t
\sigma_{st} is total number of shortest paths from node
s
s to node
t
t and
σ
s
t
(
v
)
\sigma_{st}(v) is the number of those paths that pass through
v
v. The betweenness may be normalised by dividing through the number of pairs of vertices not including v, which for directed graphs is
(
n
−
1
)
(
n
−
2
)
(n-1)(n-2) and for undirected graphs is
(
n
−
1
)
(
n
−
2
)
/
2
(n-1)(n-2)/2. For example, in an undirected star graph, the center vertex (which is contained in every possible shortest path) would have a betweenness of
(
n
−
1
)
(
n
−
2
)
/
2
(n-1)(n-2)/2 (1, if normalised) while the leaves (which are contained in no shortest paths) would have a betweenness of 0.
From a calculation aspect, both betweenness and closeness centralities of all vertices in a graph involve calculating the shortest paths between all pairs of vertices on a graph, which requires
O
(
V
3
)
{\displaystyle O(V^{3})} time with the Floyd–Warshall algorithm. However, on sparse graphs, Johnson's algorithm may be more efficient, taking
O
(
V
2
log
V
+
V
E
)
O(V^2 \log V + V E) time. In the case of unweighted graphs the calculations can be done with Brandes' algorithm[22] which takes
O
(
V
E
)
O(V E) time. Normally, these algorithms assume that graphs are undirected and connected with the allowance of loops and multiple edges. When specifically dealing with network graphs, often graphs are without loops or multiple edges to maintain simple relationships (where edges represent connections between two people or vertices). In this case, using Brandes' algorithm will divide final centrality scores by 2 to account for each shortest path being counted twice.[22]
===特征向量中心性===
===特征向量中心性===