# 介数中心性

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.

Betweenness centrality was devised as a general measure of centrality:模板:Sfnp 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, 模板:Harvp 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.

 --小趣木木（讨论） 介数中心性Betweenness centrality'被设计为中心性的一般衡量标准:   这里不能照搬机器翻译 重新翻译


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.

 --小趣木木（讨论）应该统一名词表达  node节点/顶点  上文出现顶点，应该全文一致


## Definition定义

The betweenness centrality of a node $\displaystyle{ v }$ is given by the expression:

The betweenness centrality of a node $\displaystyle{ v }$ is given by the expression:

$\displaystyle{ g(v)= \sum_{s \neq v \neq t}\frac{\sigma_{st}(v)}{\sigma_{st}} }$

where $\displaystyle{ \sigma_{st} }$ is the total number of shortest paths from node $\displaystyle{ s }$ to node $\displaystyle{ t }$ and $\displaystyle{ \sigma_{st}(v) }$ is the number of those paths that pass through $\displaystyle{ v }$.

where $\displaystyle{ \sigma_{st} }$ is the total number of shortest paths from node $\displaystyle{ s }$ to node $\displaystyle{ t }$ and $\displaystyle{ \sigma_{st}(v) }$ is the number of those paths that pass through $\displaystyle{ v }$.

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 $\displaystyle{ v }$, so that $\displaystyle{ g \in [0,1] }$. The division is done by $\displaystyle{ (N-1)(N-2) }$ for directed graphs and $\displaystyle{ (N-1)(N-2)/2 }$ for undirected graphs, where $\displaystyle{ N }$ 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 $\displaystyle{ v }$, so that $\displaystyle{ g \in [0,1] }$. The division is done by $\displaystyle{ (N-1)(N-2) }$ for directed graphs and $\displaystyle{ (N-1)(N-2)/2 }$ for undirected graphs, where $\displaystyle{ N }$ 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 > (N-1)(N-2) </math > 来完成的，而 < math > (N-1)(N-2)/2 </math > 的除法是通过无向图来完成的，  两句可以采用相同的句式

$\displaystyle{ \mbox{normal}(g(v)) = \frac{g(v) - \min(g)}{\max(g) - \min(g)} }$

which results in:

which results in:

$\displaystyle{ \max(normal) = 1 }$

$\displaystyle{ \min(normal) = 0 }$

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.

-->

-->

--->

--->

## 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.

$\displaystyle{ s_{i} = \sum_{j=1}^{N} a_{ij}w_{ij} }$

With $\displaystyle{ a_{ij} }$ and $\displaystyle{ w_{ij} }$ being adjacency and weight matrices between nodes $\displaystyle{ i }$ and $\displaystyle{ j }$, respectively.

With $\displaystyle{ a_{ij} }$ and $\displaystyle{ w_{ij} }$ being adjacency and weight matrices between nodes $\displaystyle{ i }$ and $\displaystyle{ j }$, respectively.

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.

$\displaystyle{ s(k) \approx k^\beta }$

A study of the average value $\displaystyle{ s(b) }$ of the strength for vertices with betweenness $\displaystyle{ b }$ shows that the functional behavior can be approximated by a scaling form [1]

A study of the average value $\displaystyle{ s(b) }$ of the strength for vertices with betweenness $\displaystyle{ b }$ shows that the functional behavior can be approximated by a scaling form

$\displaystyle{ s(b)\approx b^{\alpha} }$

## Percolation centrality渗流中心性

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.[2]

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渗流中心性是加权的 介数中心性Betweenness centrality的一种形式，但它在计算该权重时考虑了每条最短路径的源节点和目标节点的“状态”。在许多情况下，复杂网络中都会出现“传染”的渗流现象。例如，病毒或细菌感染可以通过人们的社交网络传播，也就是所谓的接触网络。还可以在更高的抽象层次上考虑疾病的传播问题，设想通过公路、铁路或空中连接起来的城镇或人口中心网络。计算机病毒可以通过计算机网络传播。关于商业活动和交易的谣言或新闻也可以通过人们的社交网络传播。在所有这些情况下，一种“传染病”在一个复杂网络的链接上传播，随着它的传播，无论是可恢复的还是不可恢复的，都会改变节点的“状态”。例如，在流行病学情况下，随着传染病的扩散，个体从“易感”状态转变为“感染”状态。在上面的例子中，随着传染病的传播，每个节点的状态可以是二元的（如接收/没有接收到一条信息）、离散的（易感/受感染/康复），甚至是连续的（如一个城镇中受感染的人群比例）。这些情景的共同特点是，传染病的传播导致网络中节点状态的改变。 Percolation centrality渗流中心性(PC)就是基于这个思想而提出的，它衡量了节点在帮助网络渗流方面的重要性。这个测度是由 Piraveenan 等人提出的。[2]

 --小趣木木（讨论）在所有这些情况下，一种“传染病”在一个复杂网络的链接上传播，随着它的传播，无论是可恢复的还是不可恢复的，都会改变节点的“状态”。例如，在流行病学方案中，随着感染扩散，个人从”易感”状态转变为”受感染”状态。 在上面的例子中，每个节点可以采取的状态可以是二进制的(例如接收/没有接收到一条新闻)、离散的(易感/受感染/康复) ，甚至是连续的(例如一个城镇中受感染的人的比例) ，随着传染的扩散。这些情景的共同特点是，传染的扩散导致网络中节点状态的改变。 该段还可以再精简优化一下。


Percolation centrality is defined for a given node, at a given time, as the proportion of ‘percolated paths’ that go through that node. A ‘percolated path’ is a shortest path between a pair of nodes, where the source node is percolated (e.g., infected). The target node can be percolated or non-percolated, or in a partially percolated state.

Percolation centrality is defined for a given node, at a given time, as the proportion of ‘percolated paths’ that go through that node. A ‘percolated path’ is a shortest path between a pair of nodes, where the source node is percolated (e.g., infected). The target node can be percolated or non-percolated, or in a partially percolated state.

Percolation centrality渗流中心性定义了在给定时间内，通过一个给定节点的渗流路径的比例。“渗流路径”是一对节点之间的最短路径，其中源节点被渗流的（例如，被感染）。目标节点可以是渗流的或非渗流的，或处于部分渗流状态。

$\displaystyle{ PC^t(v)= \frac{1}{N-2}\sum_{s \neq v \neq r}\frac{\sigma_{sr}(v)}{\sigma_{sr}}\frac{{x^t}_s}{{\sum {[{x^t}_i}]}-{x^t}_v} }$

where $\displaystyle{ \sigma_{sr} }$ is total number of shortest paths from node $\displaystyle{ s }$ to node $\displaystyle{ r }$ and $\displaystyle{ \sigma_{sr}(v) }$ is the number of those paths that pass through $\displaystyle{ v }$. The percolation state of the node $\displaystyle{ i }$ at time $\displaystyle{ t }$ is denoted by $\displaystyle{ {x^t}_i }$ and two special cases are when $\displaystyle{ {x^t}_i=0 }$ which indicates a non-percolated state at time $\displaystyle{ t }$ whereas when $\displaystyle{ {x^t}_i=1 }$ which indicates a fully percolated state at time $\displaystyle{ t }$. The values in between indicate partially percolated states ( e.g., in a network of townships, this would be the percentage of people infected in that town).

where $\displaystyle{ \sigma_{sr} }$ is total number of shortest paths from node $\displaystyle{ s }$ to node $\displaystyle{ r }$ and $\displaystyle{ \sigma_{sr}(v) }$ is the number of those paths that pass through $\displaystyle{ v }$. The percolation state of the node $\displaystyle{ i }$ at time $\displaystyle{ t }$ is denoted by $\displaystyle{ {x^t}_i }$ and two special cases are when $\displaystyle{ {x^t}_i=0 }$ which indicates a non-percolated state at time $\displaystyle{ t }$ whereas when $\displaystyle{ {x^t}_i=1 }$ which indicates a fully percolated state at time $\displaystyle{ t }$. The values in between indicate partially percolated states ( e.g., in a network of townships, this would be the percentage of people infected in that town).

The attached weights to the percolation paths depend on the percolation levels assigned to the source nodes, based on the premise that the higher the percolation level of a source node is, the more important are the paths that originate from that node. Nodes which lie on shortest paths originating from highly percolated nodes are therefore potentially more important to the percolation. The definition of PC may also be extended to include target node weights as well. Percolation centrality calculations run in $\displaystyle{ O(NM) }$ time with an efficient implementation adopted from Brandes' fast algorithm and if the calculation needs to consider target nodes weights, the worst case time is $\displaystyle{ O(N^3) }$.

The attached weights to the percolation paths depend on the percolation levels assigned to the source nodes, based on the premise that the higher the percolation level of a source node is, the more important are the paths that originate from that node. Nodes which lie on shortest paths originating from highly percolated nodes are therefore potentially more important to the percolation. The definition of PC may also be extended to include target node weights as well. Percolation centrality calculations run in $\displaystyle{ O(NM) }$ time with an efficient implementation adopted from Brandes' fast algorithm and if the calculation needs to consider target nodes weights, the worst case time is $\displaystyle{ O(N^3) }$.

## Algorithms 算法

Calculating the betweenness and closeness centralities of all the vertices in a graph involves calculating the shortest paths between all pairs of vertices on a graph, which takes $\displaystyle{ \Theta(|V|^3) }$ time with the Floyd–Warshall algorithm, modified to not only find one but count all shortest paths between two nodes. On a sparse graph, Johnson's algorithm or Brandes' algorithm may be more efficient, both taking $\displaystyle{ O(|V|^2 \log |V| + |V| |E|) }$ time. On unweighted graphs, calculating betweenness centrality takes $\displaystyle{ O(|V| |E|) }$ time using Brandes' algorithm.模板:Sfnp

Calculating the betweenness and closeness centralities of all the vertices in a graph involves calculating the shortest paths between all pairs of vertices on a graph, which takes ^3)[/itex] time with the Floyd–Warshall algorithm, modified to not only find one but count all shortest paths between two nodes. On a sparse graph, Johnson's algorithm or Brandes' algorithm may be more efficient, both taking )[/itex] time. On unweighted graphs, calculating betweenness centrality takes )[/itex] time using Brandes' algorithm.

In calculating betweenness and closeness centralities of all vertices in a graph, it is assumed 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.模板:Sfnp

In calculating betweenness and closeness centralities of all vertices in a graph, it is assumed 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.

Another algorithm generalizes the Freeman's betweenness computed on geodesics and Newman's betweenness computed on all paths, by introducing a hyper-parameter controlling the trade-off between exploration and exploitation. The time complexity is the number of edges times the number of nodes in the graph.模板:Sfnp

Another algorithm generalizes the Freeman's betweenness computed on geodesics and Newman's betweenness computed on all paths, by introducing a hyper-parameter controlling the trade-off between exploration and exploitation. The time complexity is the number of edges times the number of nodes in the graph.

The concept of centrality was extended to a group level as well.[3] Group betweenness centrality shows the proportion of geodesics connecting pairs of non-group members that pass through a group of nodes. Brandes' algorithm for computing the betweenness centrality of all vertices was modified to compute the group betweenness centrality of one group of nodes with the same asymptotic running time.[3]

The concept of centrality was extended to a group level as well. Group betweenness centrality shows the proportion of geodesics connecting pairs of non-group members that pass through a group of nodes. Brandes' algorithm for computing the betweenness centrality of all vertices was modified to compute the group betweenness centrality of one group of nodes with the same asymptotic running time.

## Related concepts相关概念

Betweenness centrality is related to a network's connectivity, in so much as high betweenness vertices have the potential to disconnect graphs if removed (see cut set) .

Betweenness centrality is related to a network's connectivity, in so much as high betweenness vertices have the potential to disconnect graphs if removed (see cut set) .

## Notes 备注

1. A. Barrat, M. Barthelemy, R. Pastor-Satorras, and A. Vespignani. The architecture of complex weighted networks. PNAS (2004) vol. 101 no. 11
2. Piraveenan, Mahendra (2013). "Percolation Centrality: Quantifying Graph-Theoretic Impact of Nodes during Percolation in Networks". PLOS ONE. 8 (1): e53095. Bibcode:2013PLoSO...853095P. doi:10.1371/journal.pone.0053095. PMC 3551907. PMID 23349699.
3. Puzis, R., Yagil, D., Elovici, Y., Braha, D. (2009)Collaborative attack on Internet users’ anonymity -{zh-cn:互联网档案馆; zh-tw:網際網路檔案館; zh-hk:互聯網檔案館;}-存檔，存档日期2013-12-07., Internet Research 19(1)

## References 参考文献

• Mantrach, Amin; et al. (2010). "The sum-over-paths covariance kernel: A novel covariance measure between nodes of a directed graph". IEEE Transactions on Pattern Analysis and Machine Intelligence. 32 (6): 1112–1126. doi:10.1109/tpami.2009.78.
• Moxley, Robert L.; Moxley, Nancy F. (1974). "Determining Point-Centrality in Uncontrived Social Networks". Sociometry. 37 (1): 122–130. doi:10.2307/2786472. JSTOR 2786472.
• Newman, M. E. J. (2010). Networks: An Introduction. Oxford, UK: Oxford University Press. ISBN 978-0199206650.

• Dolev, Shlomi; Elovici, Yuval; Puzis, Rami (2010). "Routing betweenness centrality". J. ACM. 57 (4): 25:1–25:27. doi:10.1145/1734213.1734219.

This page was moved from wikipedia:en:Betweenness centrality. Its edit history can be viewed at 介数中心性/edithistory