更改

[[File:Graph betweenness.svg|thumb|upright=1.3|An [[undirected graph]] colored based on the betweenness centrality of each vertex from least (red) to greatest (blue).]]

[[File:Graph betweenness.svg|thumb|upright=1.3|An [[undirected graph]] colored based on the betweenness centrality of each vertex from least (red) to greatest (blue).]]

In graph theory, betweenness centrality is a measure of centrality in a graph based on shortest paths. For every pair of vertices in a connected graph, there exists at least one shortest path between the vertices such that either the number of edges that the path passes through (for unweighted graphs) or the sum of the weights of the edges (for weighted graphs) is minimized. The betweenness centrality for each vertex is the number of these shortest paths that pass through the vertex.

In graph theory, betweenness centrality is a measure of centrality in a graph based on shortest paths. For every pair of vertices in a connected graph, there exists at least one shortest path between the vertices such that either the number of edges that the path passes through (for unweighted graphs) or the sum of the weights of the edges (for weighted graphs) is minimized. The betweenness centrality for each vertex is the number of these shortest paths that pass through the vertex.

在图论中，中间中心性是基于最短路径的图中中心性的一种度量。对于连通图中的每一对顶点，在顶点之间至少存在一条最短路径，使得路径通过的边数(对于未加权图)或者边权重的和(对于加权图)最小。每个顶点的中心性是通过该顶点的最短路径的数量。

在图论中，'''<font color="#ff8000"> 介数中心性Betweenness centrality</font>'''是基于最短路径的图中中心性的一种度量。对于连通图中的每一对顶点，在顶点之间至少存在一条最短路径，使得路径通过的边数(对于未加权图)或者边权重的和(对于加权图)最小。每个顶点的中心性是通过该顶点的最短路径的数量。

Betweenness centrality was devised as a general measure of centrality: it applies to a wide range of problems in network theory, including problems related to social networks, biology, transport and scientific cooperation. Although earlier authors have intuitively described centrality as based on betweenness,  gave the first formal definition of betweenness centrality.

Betweenness centrality was devised as a general measure of centrality: it applies to a wide range of problems in network theory, including problems related to social networks, biology, transport and scientific cooperation. Although earlier authors have intuitively described centrality as based on betweenness,  gave the first formal definition of betweenness centrality.

介于中心性被设计为中心性的一般衡量标准: 它适用于网络理论中的广泛问题，包括与社会网络、生物学、交通和科学合作有关的问题。尽管早期的作者直观地将中心性描述为基于中间性，但给出了中间性中心性的第一个正式定义。

'''<font color="#ff8000"> 介数中心性Betweenness centrality</font>'''被设计为中心性的一般衡量标准: 它适用于网络理论中的广泛问题，包括与社会网络、生物学、交通和科学合作有关的问题。尽管早期的作者直观地将中心性描述为基于中间性，但给出了'''<font color="#ff8000"> 介数中心性Betweenness centrality</font>'''的第一个正式定义。

Betweenness centrality finds wide application in network theory; it represents the degree to which nodes stand between each other. For example, in a telecommunications network, a node with higher betweenness centrality would have more control over the network, because more information will pass through that node.

Betweenness centrality finds wide application in network theory; it represents the degree to which nodes stand between each other. For example, in a telecommunications network, a node with higher betweenness centrality would have more control over the network, because more information will pass through that node.

== Definition ==

== Definition定义 ==

The betweenness centrality of a node <math>v</math> is given by the expression:

The betweenness centrality of a node <math>v</math> is given by the expression:

一个节点 < math > v </math > 的中间中心性是通过表达式给出的:

一个节点 < math > v </math > 的'''<font color="#ff8000"> 介数中心性Betweenness centrality</font>'''通过以下表达式给出:

Note that the betweenness centrality of a node scales with the number of pairs of nodes as suggested by the summation indices. Therefore, the calculation may be rescaled by dividing through by the number of pairs of nodes not including <math>v</math>, so that <math>g \in [0,1]</math>. The division is done by <math>(N-1)(N-2)</math> for directed graphs and <math>(N-1)(N-2)/2</math> for undirected graphs, where <math>N</math> is the number of nodes in the giant component. Note that this scales for the highest possible value, where one node is crossed by every single shortest path. This is often not the case, and a normalization can be performed without a loss of precision

Note that the betweenness centrality of a node scales with the number of pairs of nodes as suggested by the summation indices. Therefore, the calculation may be rescaled by dividing through by the number of pairs of nodes not including <math>v</math>, so that <math>g \in [0,1]</math>. The division is done by <math>(N-1)(N-2)</math> for directed graphs and <math>(N-1)(N-2)/2</math> for undirected graphs, where <math>N</math> is the number of nodes in the giant component. Note that this scales for the highest possible value, where one node is crossed by every single shortest path. This is often not the case, and a normalization can be performed without a loss of precision

注意，一个节点的中心性与节点对的数量成比例，如总和索引所示。因此，计算可以通过除以不包括 < math > v </math > 的节点对数来重新标度，这样 < math > g 在[0,1] </math > 中。有向图的除法是通过 < math > (N-1)(N-2) </math > 来完成的，而 < math > (N-1)(N-2)/2 </math > 的除法是通过无向图来完成的，其中 < math > n </math > 是巨型组件中的节点数。请注意，这可以缩放最大可能值，其中一个节点由每个最短路径交叉。事实往往并非如此，可以在不损失精度的情况下执行规范化

注意，如总和索引所示，一个节点的'''<font color="#ff8000"> 介数中心性Betweenness centrality</font>'''与节点对的数量成比例缩放。因此，计算可以通过除以不包括 < math > v </math > 的节点对数来重新标度，以使< math > g 在[0,1] </math > 中。有向图的除法是通过 < math > (N-1)(N-2) </math > 来完成的，而 < math > (N-1)(N-2)/2 </math > 的除法是通过无向图来完成的，其中 < math > n </math > 是巨型组件中的节点数。请注意，这可以缩放最大可能值，一个节点由每个最短路径交叉。事实往往并非如此，可以在不损失精度的情况下执行规范化

:<math>\mbox{normal}(g(v)) = \frac{g(v) - \min(g)}{\max(g) - \min(g)}</math>

:<math>\mbox{normal}(g(v)) = \frac{g(v) - \min(g)}{\max(g) - \min(g)}</math>

Note that this will always be a scaling from a smaller range into a larger range, so no precision is lost.

Note that this will always be a scaling from a smaller range into a larger range, so no precision is lost.

<!--

<!--

<!--

<!--

== The load distribution in real and model networks ==

== The load distribution in real and model networks 真实网络和模型网络中的负荷分配==

=== Model networks ===

=== Model networks 模型网络===

-->

-->

It has been shown that the load distribution of a scale-free network follows a power law given by a load exponent <math>\delta</math>,

It has been shown that the load distribution of a scale-free network follows a power law given by a load exponent <math>\delta</math>,

已经证明，无尺度网络的负荷分布遵循一个由负荷指数给出的幂律,

已经证明，无标度网络的负荷分布遵循一个由负荷指数给出的幂律,

:<math>P(g) \approx g^{-\delta}</math>      (1)

:<math>P(g) \approx g^{-\delta}</math>      (1)

this implies the scaling relation to the degree of the node,

this implies the scaling relation to the degree of the node,

这意味着缩放关系的节点度,

这意味着与节点度的缩放关系,

:<math>g(k) \approx k^\eta</math>.

:<math>g(k) \approx k^\eta</math>.

Where <math>g(k)</math> is the average load of vertices with degree <math>k</math>. The exponents <math>\delta</math> and <math>\eta</math> are not independent since equation (1) implies  

Where <math>g(k)</math> is the average load of vertices with degree <math>k</math>. The exponents <math>\delta</math> and <math>\eta</math> are not independent since equation (1) implies  

其中 < math > g (k) </math > 是程度 < math > k </math > 的顶点的平均负载。指数 < math > delta </math > 和 < math > eta </math > 不是独立的，因为方程(1)暗示

其中 < math > g (k) </math > 是度为 < math > k </math > 的顶点的平均负载。指数 < math > delta </math > 和 < math > eta </math > 不是独立的，因为方程(1)指出

:<math>P(g)= \int P(k) \delta (g-k^\eta) dk</math>

:<math>P(g)= \int P(k) \delta (g-k^\eta) dk</math>

The important exponent appears to be <math>\eta</math> which describes how the betweenness centrality depends on the connectivity. The situation which maximizes the betweenness centrality for a vertex is when all shortest paths are going through it, which corresponds to a tree structure (a network with no clustering). In the case of a tree network the maximum value of <math>\eta = 2</math> is reached.

The important exponent appears to be <math>\eta</math> which describes how the betweenness centrality depends on the connectivity. The situation which maximizes the betweenness centrality for a vertex is when all shortest paths are going through it, which corresponds to a tree structure (a network with no clustering). In the case of a tree network the maximum value of <math>\eta = 2</math> is reached.

重要的指数似乎是 < math > eta </math > ，它描述了两者之间的中心性如何依赖于连通性。当所有的最短路径都经过一个顶点时，这种情况最大化顶点的中心性，这相当于一个树结构(一个没有聚类的网络)。在树形网络的情况下，达到了 < math > eta = 2 </math > 的最大值。

重要的指数似乎是 < math > eta </math > ，它描述了两者之间的'''<font color="#ff8000"> 介数中心性Betweenness centrality</font>'''如何依赖于连通性。当所有的最短路径都经过一个顶点时，这种情况使顶点的'''<font color="#ff8000"> 介数中心性Betweenness centrality</font>'''最大化，这相当于一个树结构(一个没有聚类的网络)。在树形网络的情况下，达到了 < math > eta = 2 </math > 的最大值。

:<math>\eta = 2 \rarr \delta = \frac{\gamma +1}{2} </math>

:<math>\eta = 2 \rarr \delta = \frac{\gamma +1}{2} </math>

This maximal value of <math>\eta</math> (and hence minimum of <math>\delta</math>) puts bounds on the load exponents for networks with non-vanishing clustering.

This maximal value of <math>\eta</math> (and hence minimum of <math>\delta</math>) puts bounds on the load exponents for networks with non-vanishing clustering.

这个 < math > eta </math > 的最大值(因此是 < math > delta </math > 的最小值)为具有非消失集群的网络的负载指数设置了界限。

这个 < math > eta </math > 的最大值(因此是 < math > delta </math > 的最小值)为具有'''<font color="#32CD32"> 非消失聚类Non-vanishing clustering</font>'''的网络的负载指数设置了界限。

:<math>\eta \le 2 \rarr \delta \ge \frac{\gamma +1}{2} </math>

:<math>\eta \le 2 \rarr \delta \ge \frac{\gamma +1}{2} </math>

=== Real networks ===

=== Real networks 真实网络===

== Weighted networks  ==

== Weighted networks  加权网络==

In a weighted network the links connecting the nodes are no longer treated as binary interactions, but are weighted in proportion to their capacity, influence, frequency, etc., which adds another dimension of heterogeneity within the network beyond the topological effects. A node's strength in a weighted network is given by the sum of the weights of its adjacent edges.

In a weighted network the links connecting the nodes are no longer treated as binary interactions, but are weighted in proportion to their capacity, influence, frequency, etc., which adds another dimension of heterogeneity within the network beyond the topological effects. A node's strength in a weighted network is given by the sum of the weights of its adjacent edges.

Analogous to the power law distribution of degree found in scale free networks, the strength of a given node follows a power law distribution as well.

Analogous to the power law distribution of degree found in scale free networks, the strength of a given node follows a power law distribution as well.

A study of the average value <math>s(b)</math> of the strength for vertices with betweenness <math>b</math> shows that the functional behavior can be approximated by a scaling form  

A study of the average value <math>s(b)</math> of the strength for vertices with betweenness <math>b</math> shows that the functional behavior can be approximated by a scaling form  

:<math>s(b)\approx b^{\alpha} </math>

:<math>s(b)\approx b^{\alpha} </math>

==Percolation centrality==

=='''<font color="#ff8000"> Percolation centrality渗流中心性</font>'''==

Percolation centrality is a version of weighted betweenness centrality, but it considers the 'state' of the source and target nodes of each shortest path in calculating this weight.  Percolation of a ‘contagion’ occurs in complex networks in a number of scenarios. For example, viral or bacterial infection can spread over social networks of people, known as contact networks. The spread of disease can also be considered at a higher level of abstraction, by contemplating a network of towns or population centres, connected by road, rail or air links. Computer viruses can spread over computer networks. Rumours or news about business offers and deals can also spread via social networks of people. In all of these scenarios, a ‘contagion’ spreads over the links of a complex network, altering the ‘states’ of the nodes as it spreads, either recoverably or otherwise. For example, in an epidemiological scenario, individuals go from ‘susceptible’ to ‘infected’ state as the infection spreads. The states the individual nodes can take in the above examples could be binary (such as received/not received a piece of news), discrete (susceptible/infected/recovered), or even continuous (such as the proportion of infected people in a town), as the contagion spreads. The common feature in all these scenarios is that the spread of contagion results in the change of node states in networks. Percolation centrality (PC) was proposed with this in mind, which specifically measures the importance of nodes in terms of aiding the percolation through the network. This measure was proposed by Piraveenan et al.

Percolation centrality is a version of weighted betweenness centrality, but it considers the 'state' of the source and target nodes of each shortest path in calculating this weight.  Percolation of a ‘contagion’ occurs in complex networks in a number of scenarios. For example, viral or bacterial infection can spread over social networks of people, known as contact networks. The spread of disease can also be considered at a higher level of abstraction, by contemplating a network of towns or population centres, connected by road, rail or air links. Computer viruses can spread over computer networks. Rumours or news about business offers and deals can also spread via social networks of people. In all of these scenarios, a ‘contagion’ spreads over the links of a complex network, altering the ‘states’ of the nodes as it spreads, either recoverably or otherwise. For example, in an epidemiological scenario, individuals go from ‘susceptible’ to ‘infected’ state as the infection spreads. The states the individual nodes can take in the above examples could be binary (such as received/not received a piece of news), discrete (susceptible/infected/recovered), or even continuous (such as the proportion of infected people in a town), as the contagion spreads. The common feature in all these scenarios is that the spread of contagion results in the change of node states in networks. Percolation centrality (PC) was proposed with this in mind, which specifically measures the importance of nodes in terms of aiding the percolation through the network. This measure was proposed by Piraveenan et al.

渗透中心性是一种加权的介于中心性之间的中心性，但它在计算这个权重时考虑了每条最短路径的源节点和目标节点的状态。在许多情况下，复杂网络中都会出现“传染”现象。例如，病毒或细菌感染可以通过人们的社交网络传播，也就是所谓的接触网络。还可以在更高的抽象层次上考虑疾病的传播问题，设想通过公路、铁路或空中连接起来的城镇或人口中心网络。计算机病毒可以通过计算机网络传播。关于商业活动和交易的谣言或新闻也可以通过人们的社交网络传播。在所有这些情况下，一种“传染病”在一个复杂网络的链接上传播，随着它的传播，无论是可恢复的还是不可恢复的，都会改变节点的“状态”。例如，在流行病学方案中，随着感染扩散，个人从”易感”状态转变为”受感染”状态。在上面的例子中，每个节点可以采取的状态可以是二进制的(例如接收/没有接收到一条新闻)、离散的(易感/受感染/康复) ，甚至是连续的(例如一个城镇中受感染的人的比例) ，随着传染的扩散。这些情景的共同特点是，传染的扩散导致网络中节点状态的改变。渗滤中心性(PC)就是基于这个思想而提出的，它特别地衡量了节点在协助网络渗滤方面的重要性。这项措施是由 piraveanan 等人提出的。

'''<font color="#ff8000"> Percolation centrality渗流中心性</font>'''是一种加权的介数中心性，但它在计算这个权重时考虑了每条最短路径的源节点和目标节点的状态。在许多情况下，复杂网络中都会出现“传染”现象。例如，病毒或细菌感染可以通过人们的社交网络传播，也就是所谓的接触网络。还可以在更高的抽象层次上考虑疾病的传播问题，设想通过公路、铁路或空中连接起来的城镇或人口中心网络。计算机病毒可以通过计算机网络传播。关于商业活动和交易的谣言或新闻也可以通过人们的社交网络传播。在所有这些情况下，一种“传染病”在一个复杂网络的链接上传播，随着它的传播，无论是可恢复的还是不可恢复的，都会改变节点的“状态”。例如，在流行病学方案中，随着感染扩散，个人从”易感”状态转变为”受感染”状态。在上面的例子中，每个节点可以采取的状态可以是二进制的(例如接收/没有接收到一条新闻)、离散的(易感/受感染/康复) ，甚至是连续的(例如一个城镇中受感染的人的比例) ，随着传染的扩散。这些情景的共同特点是，传染的扩散导致网络中节点状态的改变。渗滤中心性(PC)就是基于这个思想而提出的，它特别地衡量了节点在协助网络渗滤方面的重要性。这项措施是由 piraveanan 等人提出的。