“介数中心性”的版本间的差异
| 第1行： | 第1行： | ||
| − | + | 此词条暂由水流心不竞初译，未经审校，带来阅读不便，请见谅。已由Zcy初次审校 | |
[[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).]] | ||
| 第5行： | 第5行： | ||
An [[undirected graph colored based on the betweenness centrality of each vertex from least (red) to greatest (blue).]] | 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 (discrete mathematics)|graph]] based on [[Shortest path problem|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 (graph theory)|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 (discrete mathematics)|graph]] based on [[Shortest path problem|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 (graph theory)|vertex]] is the number of these shortest paths that pass through the vertex. | ||
| 第11行： | 第11行： | ||
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>'''是基于最短路径的图中心性的一种度量。对于连通图中的每一对节点，在节点之间至少存在一条最短路径，使得路径通过的边数(对于未加权图)或者边权重的和(对于加权图) | + | 在图论中，'''<font color="#ff8000"> 介数中心性Betweenness centrality</font>'''是基于最短路径的图中心性的一种度量。对于连通图中的每一对节点，在节点之间至少存在一条最短路径，使得路径通过的边数(对于未加权图)或者边权重的和(对于加权图)最小。节点的中心性是经过该节点的最短路径的数量。 |
| 第19行： | 第19行： | ||
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"> | + | '''<font color="#ff8000"> 介数中心性Betweenness centrality</font>'''的提出为中心性的衡量提供了一般的标准: 它适用于网络理论中广泛的问题，包括与社会网络、生物学、交通和科学合作有关的问题。尽管早期的学者直观地将中心性描述为基于介数，但是给出了'''<font color="#ff8000"> 介数中心性Betweenness centrality</font>'''的第一个正式定义。 |
| − | + | --[[用户:小趣木木|小趣木木]]（[[用户讨论:小趣木木|讨论]]）''<font color="#ff8000"> 介数中心性Betweenness centrality</font>'''被设计为中心性的一般衡量标准: 这里不能照搬机器翻译 重新翻译 | |
| 第27行： | 第27行： | ||
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. | ||
| − | '''<font color="#ff8000"> | + | '''<font color="#ff8000"> 介数中心性Betweenness centrality</font>'''在网络理论中有着广泛的应用，它代表了节点之间相互独立的程度。例如，在远程通信网络中，具有较高'''<font color="#ff8000"> 介数中心性Betweenness centrality</font>'''的节点将对网络有更多的控制，因为有更多的信息会通过该节点。 |
--[[用户:小趣木木|小趣木木]]（[[用户讨论:小趣木木|讨论]]）应该统一名词表达 node节点/顶点 上文出现顶点，应该全文一致 | --[[用户:小趣木木|小趣木木]]（[[用户讨论:小趣木木|讨论]]）应该统一名词表达 node节点/顶点 上文出现顶点，应该全文一致 | ||
| 第39行： | 第39行： | ||
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> 的'''<font color="#ff8000"> | + | 一个节点 < math > v </math > 的'''<font color="#ff8000"> 介数中心性Betweenness centrality</font>'''通过以下表达式给出: |
| 第45行： | 第45行： | ||
:<math>g(v)= \sum_{s \neq v \neq t}\frac{\sigma_{st}(v)}{\sigma_{st}}</math> | :<math>g(v)= \sum_{s \neq v \neq t}\frac{\sigma_{st}(v)}{\sigma_{st}}</math> | ||
| − | |||
| − | |||
| − | |||
| 第55行： | 第52行： | ||
where <math>\sigma_{st}</math> is the total number of shortest paths from node <math>s</math> to node <math>t</math> and <math>\sigma_{st}(v)</math> is the number of those paths that pass through <math>v</math>. | where <math>\sigma_{st}</math> is the total number of shortest paths from node <math>s</math> to node <math>t</math> and <math>\sigma_{st}(v)</math> is the number of those paths that pass through <math>v</math>. | ||
| − | 其中 <math> | + | 其中 < math > sigma { st } </math > 是从节点 < math > s </math > 到节点 < math > t </math >的最短路径总数， < math > sigma { st }(v) </math >是其中通过节点<math>v</math>的路径数量。 |
| 第63行： | 第60行： | ||
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 | ||
| − | + | 注意，如公式中求和指标所示，一个节点的'''<font color="#ff8000"> 介数中心性Betweenness centrality</font>'''与节点对的数量成比例缩放。因此，计算可以通过除以不包括 < math > v </math > 的节点对数来重新标定，使得<math>g \in [0,1]</math>。有向图是通过除以 < math > (N-1)(N-2) </math > 来实现的，而无向图是通过除以 < math > (N-1)(N-2)/2 </math >来实现的，其中 < math > n </math > 是巨组元中的节点数。请注意，当每一条最短路径都通过一个节点时，这个节点达到可以缩放的最大可能值。事实往往并非如此，可以在不损失精度的情况下执行标准化 | |
| + | --[[用户:小趣木木|小趣木木]]（[[用户讨论:小趣木木|讨论]]）有向图的除法是通过 < math > (N-1)(N-2) </math > 来完成的，而 < math > (N-1)(N-2)/2 </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> | ||
| − | |||
| − | |||
| − | |||
which results in: | which results in: | ||
| 第81行： | 第75行： | ||
:<math>\max(normal) = 1</math> | :<math>\max(normal) = 1</math> | ||
| − | |||
| − | |||
| − | |||
:<math>\min(normal) = 0</math> | :<math>\min(normal) = 0</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. | ||
| 第95行： | 第83行： | ||
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 真实网络和模型网络中的负荷分配== | ||
| 第117行： | 第102行： | ||
<!-- File seems to have never existed | <!-- File seems to have never existed | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | , Squares:<math>\gamma=2.5</math>, | + | [[File:Load Dist.png|thumb|400px|Plot showing the power law distribution of load in a scale free network for various values of <math>\gamma</math>.Circles: <math>\gamma=2.2</math>, Squares:<math>\gamma=2.5</math>, Diamonds:<math>\gamma=3.0</math>, X's:<math>\gamma=4.0</math>, Triangles:<math>\gamma= \infin </math> <ref name="Goh">K.-I. Goh, B. Kahng, and D. Kim PhysRevLett.87.278701</ref>]] |
| − | |||
| − | |||
| − | + | [[File:Load Dist.png|thumb|400px|<math>\gamma</math>为不同值时，无标度网络中负荷的幂律分布曲线.圆圈： <math>\gamma=2.2</math>，正方形：<math>\gamma=2.5</math>，钻石：<math>\gamma=3.0</math>，X：<math>\gamma=4.0</math>，三角形：<math>\gamma= \infin </math> <ref name="Goh">K.-I. Goh, B. Kahng, and D. Kim PhysRevLett.87.278701</ref>]] | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
--> | --> | ||
| − | |||
<!-- | <!-- | ||
| − | |||
| − | |||
| − | |||
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>,{{Sfnp|Goh|Kahng|Kim|2001}} | 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>,{{Sfnp|Goh|Kahng|Kim|2001}} | ||
| 第171行： | 第124行： | ||
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>\delta</math>所给出的[[幂律]]，{{Sfnp|Goh|Kahng|Kim|2001}} | |
| − | |||
:<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, | ||
| 第183行： | 第132行： | ||
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 <ref name="Bart">M. Barthélemy. Betweenness centrality in large complex networks. Eur. Phys. J. B 38, 163–168 (2004)</ref> | 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 <ref name="Bart">M. Barthélemy. Betweenness centrality in large complex networks. Eur. Phys. J. B 38, 163–168 (2004)</ref> | ||
| 第195行： | 第141行： | ||
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> | + | 其中 < 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> | ||
| − | |||
| − | |||
| − | |||
For large g, and therefore large k, the expression becomes | For large g, and therefore large k, the expression becomes | ||
| 第208行： | 第150行： | ||
对于大 g，也就是大 k，表达式变成 | 对于大 g，也就是大 k，表达式变成 | ||
| + | |||
| + | --[[用户:Zcy|Zcy]]（[[用户讨论:Zcy|讨论]]）For large g, and therefore large k, the expression becomes翻译不恰当 | ||
:<math>P(g\gg1)= \int k^{-\gamma} \delta (g-k^\eta) dk</math> | :<math>P(g\gg1)= \int k^{-\gamma} \delta (g-k^\eta) dk</math> | ||
| − | |||
| − | |||
| − | |||
| − | |||
:<math>\sim g^{-1-\frac{\gamma -1}{\eta}} </math> | :<math>\sim g^{-1-\frac{\gamma -1}{\eta}} </math> | ||
| − | |||
| − | |||
| − | |||
which proves the following equality: | which proves the following equality: | ||
| 第225行： | 第162行： | ||
which proves the following equality: | which proves the following equality: | ||
| − | + | 证明了如下等式： | |
:<math>\eta=\frac{\gamma -1}{\delta -1}</math> | :<math>\eta=\frac{\gamma -1}{\delta -1}</math> | ||
| − | |||
| − | |||
| − | |||
| 第239行： | 第173行： | ||
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 > ，它描述了'''<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. | ||
| 第251行： | 第182行： | ||
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 > 的最小值)为具有'''<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> | ||
| − | |||
| − | |||
| − | |||
In this case, the exponents <math>\delta , \eta </math> are not universal and depend on the different details (average connectivity, correlations, etc.) | In this case, the exponents <math>\delta , \eta </math> are not universal and depend on the different details (average connectivity, correlations, etc.) | ||
| 第263行： | 第191行： | ||
In this case, the exponents <math>\delta , \eta </math> are not universal and depend on the different details (average connectivity, correlations, etc.) | In this case, the exponents <math>\delta , \eta </math> are not universal and depend on the different details (average connectivity, correlations, etc.) | ||
| − | 在这种情况下，指数 < math > delta，eta </math > | + | 在这种情况下，指数 < math > delta，eta </math > 并不是通用的，取决于不同的细节（平均连接性、相关性等）。 |
| 第275行： | 第203行： | ||
Real world scale free networks, such as the internet, also follow a power law load distribution. This is an intuitive result. Scale free networks arrange themselves to create short path lengths across the network by creating a few hub nodes with much higher connectivity than the majority of the network. These hubs will naturally experience much higher loads because of this added connectivity. | Real world scale free networks, such as the internet, also follow a power law load distribution. This is an intuitive result. Scale free networks arrange themselves to create short path lengths across the network by creating a few hub nodes with much higher connectivity than the majority of the network. These hubs will naturally experience much higher loads because of this added connectivity. | ||
| − | 现实世界中的'''<font color="#ff8000"> 无标度网络Scale free networks</font>''' | + | 现实世界中的'''<font color="#ff8000"> 无标度网络Scale free networks</font>'''，如互联网，也遵循幂律负载分布。这是一个直观的结果。无标度网络通过创建一些比大多数网络具有更高连通性的枢纽节点，从而在网络中实现较短的路径长度。由于这种额外的连接，这些枢纽节点自然会承担更高的负载。 |
| − | |||
---> | ---> | ||
| 第282行： | 第209行： | ||
---> | ---> | ||
| + | |||
| + | |||
== Weighted networks 加权网络== | == Weighted networks 加权网络== | ||
| 第289行： | 第218行： | ||
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. | ||
| − | + | 在加权网络中，连接节点的链路不再被视为二元的相互作用，而是根据其容量、影响力、频率等按比例加权，这在拓扑效应之外增加了网络内另一个异质性的维度。一个加权网络中的节点的强度是由其相邻边的权重之和来表示的。 | |
:<math>s_{i} = \sum_{j=1}^{N} a_{ij}w_{ij}</math> | :<math>s_{i} = \sum_{j=1}^{N} a_{ij}w_{ij}</math> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| 第305行： | 第230行： | ||
With <math>a_{ij}</math> and <math>w_{ij}</math> being adjacency and weight matrices between nodes <math>i</math> and <math>j</math>, respectively. | With <math>a_{ij}</math> and <math>w_{ij}</math> being adjacency and weight matrices between nodes <math>i</math> and <math>j</math>, respectively. | ||
| − | 用 < math > a { ij } </math > 和 < math > w { ij } </math > 分别作为 < math > i </math > 和 < math > < j </math > | + | 用 < math > a { ij } </math > 和 < math > w { ij } </math > 分别作为 < math > i </math > 和 < math > < j </math > 节点之间的邻接矩阵和权值矩阵。 |
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. | ||
| 第311行： | 第236行： | ||
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. | ||
| − | 类似于'''<font color="#ff8000"> | + | 类似于'''<font color="#ff8000"> 无标度网络Scale free networks</font>'''中度的'''<font color="#ff8000"> 幂律分布Power law distribution</font>'''，节点的强度也服从'''<font color="#ff8000"> 幂律分布Power law distribution</font>'''。 |
| 第317行： | 第242行： | ||
:<math>s(k) \approx k^\beta </math> | :<math>s(k) \approx k^\beta </math> | ||
| − | |||
| − | |||
| − | |||
| 第327行： | 第249行： | ||
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>b</math>的节点强度的平均值<math>s(b)</math>的研究表明，功能行为可以用缩放形式来近似 | |
:<math>s(b)\approx b^{\alpha} </math> | :<math>s(b)\approx b^{\alpha} </math> | ||
| − | |||
| − | |||
| − | |||
: | : | ||
| 第343行： | 第262行： | ||
| − | =='''<font color="#ff8000"> Percolation | + | =='''<font color="#ff8000"> Percolation centrality渗流中心性</font>'''== |
| 第351行： | 第270行： | ||
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. | ||
| − | '''<font color="#ff8000"> Percolation | + | '''<font color="#ff8000"> Percolation centrality渗流中心性</font>'''是加权的'''<font color="#ff8000"> 介数中心性Betweenness centrality</font>'''的一种形式，但它在计算该权重时考虑了每条最短路径的源节点和目标节点的“状态”。在许多情况下，复杂网络中都会出现“传染”的渗流现象。例如，病毒或细菌感染可以通过人们的社交网络传播，也就是所谓的接触网络。还可以在更高的抽象层次上考虑疾病的传播问题，设想通过公路、铁路或空中连接起来的城镇或人口中心网络。计算机病毒可以通过计算机网络传播。关于商业活动和交易的谣言或新闻也可以通过人们的社交网络传播。在所有这些情况下，一种“传染病”在一个复杂网络的链接上传播，随着它的传播，无论是可恢复的还是不可恢复的，都会改变节点的“状态”。例如，在流行病学情况下，随着传染病的扩散，个体从“易感”状态转变为“感染”状态。在上面的例子中，随着传染病的传播，每个节点的状态可以是二元的（如接收/没有接收到一条信息）、离散的（易感/受感染/康复），甚至是连续的（如一个城镇中受感染的人群比例）。这些情景的共同特点是，传染病的传播导致网络中节点状态的改变。'''<font color="#ff8000"> Percolation centrality渗流中心性</font>'''(PC)就是基于这个思想而提出的，它衡量了节点在帮助网络渗流方面的重要性。这个测度是由 Piraveenan 等人提出的。<ref name="piraveenan2013">{{cite journal |last1 = Piraveenan |first1 = Mahendra | year=2013| title = Percolation Centrality: Quantifying Graph-Theoretic Impact of Nodes during Percolation in Networks | journal = PLOS ONE | volume=8 | issue=1 | doi=10.1371/journal.pone.0053095 | pages=e53095 | pmid=23349699 | pmc=3551907| bibcode=2013PLoSO...853095P }}</ref> |
| + | --[[用户:小趣木木|小趣木木]]（[[用户讨论:小趣木木|讨论]]）在所有这些情况下，一种“传染病”在一个复杂网络的链接上传播，随着它的传播，无论是可恢复的还是不可恢复的，都会改变节点的“状态”。例如，在流行病学方案中，随着感染扩散，个人从”易感”状态转变为”受感染”状态。 在上面的例子中，每个节点可以采取的状态可以是二进制的(例如接收/没有接收到一条新闻)、离散的(易感/受感染/康复) ，甚至是连续的(例如一个城镇中受感染的人的比例) ，随着传染的扩散。这些情景的共同特点是，传染的扩散导致网络中节点状态的改变。 该段还可以再精简优化一下。 | ||
| 第358行： | 第278行： | ||
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. | ||
| − | '''<font color="#ff8000"> | + | '''<font color="#ff8000"> Percolation centrality渗流中心性</font>'''定义了在给定时间内，通过一个给定节点的渗流路径的比例。“渗流路径”是一对节点之间的最短路径，其中源节点被渗流的（例如，被感染）。目标节点可以是渗流的或非渗流的，或处于部分渗流状态。 |
| 第364行： | 第284行： | ||
:<math>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}</math> | :<math>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}</math> | ||
| − | |||
| − | |||
| − | |||
| 第374行： | 第291行： | ||
where <math>\sigma_{sr}</math> is total number of shortest paths from node <math>s</math> to node <math>r</math> and <math>\sigma_{sr}(v)</math> is the number of those paths that pass through <math>v</math>. The percolation state of the node <math>i</math> at time <math>t</math> is denoted by <math>{x^t}_i</math> and two special cases are when <math>{x^t}_i=0</math> which indicates a non-percolated state at time <math>t</math> whereas when <math>{x^t}_i=1</math> which indicates a fully percolated state at time <math>t</math>. 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 <math>\sigma_{sr}</math> is total number of shortest paths from node <math>s</math> to node <math>r</math> and <math>\sigma_{sr}(v)</math> is the number of those paths that pass through <math>v</math>. The percolation state of the node <math>i</math> at time <math>t</math> is denoted by <math>{x^t}_i</math> and two special cases are when <math>{x^t}_i=0</math> which indicates a non-percolated state at time <math>t</math> whereas when <math>{x^t}_i=1</math> which indicates a fully percolated state at time <math>t</math>. 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). | ||
| − | + | 其中， < math >\sigma_{sr}</math > 是从节点 < math > s </math > 到节点 < math > r </math > 的最短路径的数量总数， < math > \sigma_{sr}(v) </math > 是其中通过节点 < math > v </math > 的路径总数。在时间 < math > t </math > 时，节点的渗流状态用 < math > {x^t}_i </math > 表示，两个特殊情况是当 < math > {x^t}_i=0</math >， 表示在时间<math>t</math>时是非渗流状态，而当 <math>{x^t}_i=1</math>时， 表示在时间<math>t</math>时是完全渗流状态。两者之间的值表示部分渗流状态（例如，在一个城镇网络中，这是该城镇感染者的百分比）。 | |
| 第382行： | 第299行： | ||
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 <math>O(NM)</math> 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 <math>O(N^3)</math>. | 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 <math>O(NM)</math> 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 <math>O(N^3)</math>. | ||
| − | + | 渗流路径的权重取决于分配给源节点的渗流水平，前提是源节点的渗流水平越高，源节点的路径就越重要。因此，位于源自高渗流节点的最短路径上的节点可能对渗流更为重要。PC 的定义也可以扩展到包括目标节点的权值。当采用Brandes的快速算法计算'''<font color="#ff8000"> Percolation centrality渗滤中心性</font>'''时，计算时间复杂度为 < math > O(NM) </math >，如果计算需要考虑目标节点的权值，最高的计算时间复杂度为 < math > O(N^3) </math > 。 | |
| 第392行： | 第309行： | ||
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)</math> 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 )</math> time. On unweighted graphs, calculating betweenness centrality takes )</math> time using Brandes' algorithm. | 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)</math> 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 )</math> time. On unweighted graphs, calculating betweenness centrality takes )</math> time using Brandes' algorithm. | ||
| − | + | 计算一个图中所有顶点的介数和'''<font color="#ff8000"> 紧密中心性Closeness centralities</font>'''涉及到计算图中所有节点对之间的最短路径，使用 Floyd-Warshall 算法时，这需要[[big theta|<math>\Theta(|V|^3)</math>]]的时间复杂度，改进后的算法不仅可以找到一条路径，还可以计算两个节点之间的所有最短路径。在稀疏图上，Johnson算法或Brandes算法可能更有效率，两者的时间复杂度为[[Big O notation|<math>O(|V|^2 \log |V| + |V| |E|)</math>]]。在未加权图上，使用 Brandes 算法计算'''<font color="#ff8000"> 介数中心性Betweenness centrality</font>'''需要的时间复杂度为[[Big O notation|<math>O(|V| |E|)</math>]]。{{Sfnp|Brandes|2001|p=1}} | |
| + | |||
| 第400行： | 第318行： | ||
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. | 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. | ||
| − | + | 在计算一个图的所有节点的介数和'''<font color="#ff8000"> 紧密中心性Closeness centralities</font>'''时，假定图是无向的，并且图在允许自环和多边时是连通的。当专门处理网络图时，图通常没有自环或多边来维持简单的关系（其中的边表示两个人或节点之间的联系）。在这种情况下，使用 Brandes 算法将最终的中心性除以2，因为每条最短路径被计算两次。 | |
| 第408行： | 第326行： | ||
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. | 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. | ||
| − | + | 另一个算法通过引入一个超参数来控制勘探和开发之间的平衡，将计算测地线的弗里曼（Freeman）介数和所有路径上计算纽曼（Newman）介数的结果进行了推广。时间复杂度是图中的边数乘以节点数。{{Sfnp|Mantrach|2010}} | |
| 第416行： | 第334行： | ||
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. | 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. | ||
| − | + | 中心性的概念也扩展到了群体层次。<ref name=group>Puzis, R., Yagil, D., Elovici, Y., Braha, D. (2009)[http://necsi.edu/affiliates/braha/Internet_Research_Anonimity.pdf Collaborative attack on Internet users’ anonymity] {{Webarchive|url=https://web.archive.org/web/20131207133417/http://necsi.edu/affiliates/braha/Internet_Research_Anonimity.pdf |date=2013-12-07 }}, ''Internet Research'' '''19'''(1)</ref>群体介数中心性反映了通过一组节点连接非组成员节点对的测地线所占的比例。修改了计算所有节点之间的介数中心性的Brandes算法，以计算具有相同渐近运行时间的一组节点之间的群体介数中心性。 | |
| 第426行： | 第344行： | ||
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) . | ||
| − | <font color="#ff8000"> | + | '''<font color="#ff8000"> 介数中心性Betweenness centrality</font>'''与网络的连通性有关，如果高介数顶点被移除，就有可能断开图的连接（参见割集）。 |
| − | |||
| − | == See | + | == See also另请参阅== |
* [[Centrality]] | * [[Centrality]] | ||
| 第453行： | 第370行： | ||
|last1 = Freeman | |last1 = Freeman | ||
| − | |||
1 = Freeman | 1 = Freeman | ||
| 第459行： | 第375行： | ||
|first1 = Linton | |first1 = Linton | ||
| − | |||
1 = Linton | 1 = Linton | ||
| 第465行： | 第380行： | ||
|authorlink = Linton Freeman | |authorlink = Linton Freeman | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| year=1977 | | year=1977 | ||
| − | |||
| title = A set of measures of centrality based on betweenness | | title = A set of measures of centrality based on betweenness | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| journal = Sociometry | | journal = Sociometry | ||
| − | |||
| volume=40 | | volume=40 | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
|issue = 1 | |issue = 1 | ||
| − | |||
| − | |||
| − | |||
| pages=35–41 | | pages=35–41 | ||
| − | |||
| − | |||
| − | |||
|doi=10.2307/3033543|ref=harv|jstor = 3033543 | |doi=10.2307/3033543|ref=harv|jstor = 3033543 | ||
| − | |||
| − | |||
| − | |||
}} | }} | ||
| − | |||
*{{cite journal | *{{cite journal | ||
| 第521行： | 第408行： | ||
|title=Universal Behavior of Load Distribution in Scale-Free Networks | |title=Universal Behavior of Load Distribution in Scale-Free Networks | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
|last1=Goh | |last1=Goh | ||
| − | |||
| − | |||
| − | |||
|first1=K. I. | |first1=K. I. | ||
| − | |||
| − | |||
| − | |||
|last2=Kahng | |last2=Kahng | ||
| − | |||
|first2=B. | |first2=B. | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
|last3=Kim | |last3=Kim | ||
| − | |||
| − | |||
| − | |||
|first3=D.|journal=Physical Review Letters | |first3=D.|journal=Physical Review Letters | ||
| − | |||
| − | |||
| − | |||
|volume=87 | |volume=87 | ||
| − | |||
|issue=27 | |issue=27 | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
|pages=278701 | |pages=278701 | ||
| − | |||
|date=2001 | |date=2001 | ||
| − | |||
| − | |||
| − | |||
|doi=10.1103/physrevlett.87.278701|ref=harv | |doi=10.1103/physrevlett.87.278701|ref=harv | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
|bibcode=2001PhRvL..87A8701G | |bibcode=2001PhRvL..87A8701G | ||
| − | |||
| − | |||
| − | |||
|arxiv=cond-mat/0106565 | |arxiv=cond-mat/0106565 | ||
| − | |||
}} | }} | ||
| − | |||
| − | |||
| − | |||
*{{cite journal |last1=Mantrach |first1=Amin | title = The sum-over-paths covariance kernel: A novel covariance measure between nodes of a directed graph|journal= IEEE Transactions on Pattern Analysis and Machine Intelligence |volume=32|issue=6|pages=1112–1126|year=2010 |display-authors=etal|ref=harv |doi=10.1109/tpami.2009.78}} | *{{cite journal |last1=Mantrach |first1=Amin | title = The sum-over-paths covariance kernel: A novel covariance measure between nodes of a directed graph|journal= IEEE Transactions on Pattern Analysis and Machine Intelligence |volume=32|issue=6|pages=1112–1126|year=2010 |display-authors=etal|ref=harv |doi=10.1109/tpami.2009.78}} | ||
| 第617行： | 第459行： | ||
|last1=Newman | |last1=Newman | ||
| − | |||
| − | |||
| − | |||
|first1= M. E. J. | |first1= M. E. J. | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
|year=2010 | |year=2010 | ||
| − | |||
| − | |||
| − | |||
|title=Networks: An Introduction | |title=Networks: An Introduction | ||
| − | |||
| − | |||
| − | |||
|place=Oxford, UK | |place=Oxford, UK | ||
| − | |||
| − | |||
| − | |||
|publisher=Oxford University Press | |publisher=Oxford University Press | ||
| − | |||
| − | |||
| − | |||
|isbn=978-0199206650 | |isbn=978-0199206650 | ||
| − | |||
|ref=harv | |ref=harv | ||
| − | |||
| − | |||
| − | |||
}} | }} | ||
| − | |||
| − | |||
| − | |||
*{{cite journal|last1=Dolev|first1=Shlomi|last2=Elovici|first2=Yuval|last3=Puzis|first3=Rami|title=Routing betweenness centrality|journal=J. ACM|date=2010|volume=57|issue=4|pages=25:1–25:27|doi=10.1145/1734213.1734219}} | *{{cite journal|last1=Dolev|first1=Shlomi|last2=Elovici|first2=Yuval|last3=Puzis|first3=Rami|title=Routing betweenness centrality|journal=J. ACM|date=2010|volume=57|issue=4|pages=25:1–25:27|doi=10.1145/1734213.1734219}} | ||
| 第677行： | 第492行： | ||
[[Category:Network theory]] | [[Category:Network theory]] | ||
| − | |||
| − | |||
| − | |||
[[Category:Graph invariants]] | [[Category:Graph invariants]] | ||
| − | |||
| − | |||
| − | |||
<noinclude> | <noinclude> | ||
2020年12月12日 (六) 01:52的版本
此词条暂由水流心不竞初译，未经审校，带来阅读不便，请见谅。已由Zcy初次审校
根据每个顶点的介数中心性从最小(红色)到最大(蓝色)着色的无向图。
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是基于最短路径的图中心性的一种度量。对于连通图中的每一对节点，在节点之间至少存在一条最短路径，使得路径通过的边数(对于未加权图)或者边权重的和(对于加权图)最小。节点的中心性是经过该节点的最短路径的数量。
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的第一个正式定义。
--小趣木木（讨论） 介数中心性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.
介数中心性Betweenness centrality在网络理论中有着广泛的应用，它代表了节点之间相互独立的程度。例如，在远程通信网络中，具有较高 介数中心性Betweenness centrality的节点将对网络有更多的控制，因为有更多的信息会通过该节点。
--小趣木木（讨论）应该统一名词表达 node节点/顶点 上文出现顶点，应该全文一致
Definition定义
The betweenness centrality of a node [math]\displaystyle{ v }[/math] is given by the expression:
The betweenness centrality of a node [math]\displaystyle{ v }[/math] is given by the expression:
一个节点 < math > v </math > 的 介数中心性Betweenness centrality通过以下表达式给出:
- [math]\displaystyle{ g(v)= \sum_{s \neq v \neq t}\frac{\sigma_{st}(v)}{\sigma_{st}} }[/math]
where [math]\displaystyle{ \sigma_{st} }[/math] is the total number of shortest paths from node [math]\displaystyle{ s }[/math] to node [math]\displaystyle{ t }[/math] and [math]\displaystyle{ \sigma_{st}(v) }[/math] is the number of those paths that pass through [math]\displaystyle{ v }[/math].
where [math]\displaystyle{ \sigma_{st} }[/math] is the total number of shortest paths from node [math]\displaystyle{ s }[/math] to node [math]\displaystyle{ t }[/math] and [math]\displaystyle{ \sigma_{st}(v) }[/math] is the number of those paths that pass through [math]\displaystyle{ v }[/math].
其中 < math > sigma { st } </math > 是从节点 < math > s </math > 到节点 < math > t </math >的最短路径总数， < math > sigma { st }(v) </math >是其中通过节点[math]\displaystyle{ v }[/math]的路径数量。
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]\displaystyle{ v }[/math], so that [math]\displaystyle{ g \in [0,1] }[/math]. The division is done by [math]\displaystyle{ (N-1)(N-2) }[/math] for directed graphs and [math]\displaystyle{ (N-1)(N-2)/2 }[/math] for undirected graphs, where [math]\displaystyle{ 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]\displaystyle{ v }[/math], so that [math]\displaystyle{ g \in [0,1] }[/math]. The division is done by [math]\displaystyle{ (N-1)(N-2) }[/math] for directed graphs and [math]\displaystyle{ (N-1)(N-2)/2 }[/math] for undirected graphs, where [math]\displaystyle{ 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
注意，如公式中求和指标所示，一个节点的 介数中心性Betweenness centrality与节点对的数量成比例缩放。因此，计算可以通过除以不包括 < math > v </math > 的节点对数来重新标定，使得[math]\displaystyle{ g \in [0,1] }[/math]。有向图是通过除以 < math > (N-1)(N-2) </math > 来实现的，而无向图是通过除以 < math > (N-1)(N-2)/2 </math >来实现的，其中 < math > n </math > 是巨组元中的节点数。请注意，当每一条最短路径都通过一个节点时，这个节点达到可以缩放的最大可能值。事实往往并非如此，可以在不损失精度的情况下执行标准化
--小趣木木（讨论）有向图的除法是通过 < math > (N-1)(N-2) </math > 来完成的，而 < math > (N-1)(N-2)/2 </math > 的除法是通过无向图来完成的， 两句可以采用相同的句式
- [math]\displaystyle{ \mbox{normal}(g(v)) = \frac{g(v) - \min(g)}{\max(g) - \min(g)} }[/math]
which results in:
which results in:
结果是:
- [math]\displaystyle{ \max(normal) = 1 }[/math]
- [math]\displaystyle{ \min(normal) = 0 }[/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.
请注意，这种方法将始终是从较小范围到较大范围的缩放，因此不会丢失精度。
-->
-->
--->
--->
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.
在加权网络中，连接节点的链路不再被视为二元的相互作用，而是根据其容量、影响力、频率等按比例加权，这在拓扑效应之外增加了网络内另一个异质性的维度。一个加权网络中的节点的强度是由其相邻边的权重之和来表示的。
- [math]\displaystyle{ s_{i} = \sum_{j=1}^{N} a_{ij}w_{ij} }[/math]
With [math]\displaystyle{ a_{ij} }[/math] and [math]\displaystyle{ w_{ij} }[/math] being adjacency and weight matrices between nodes [math]\displaystyle{ i }[/math] and [math]\displaystyle{ j }[/math], respectively.
With [math]\displaystyle{ a_{ij} }[/math] and [math]\displaystyle{ w_{ij} }[/math] being adjacency and weight matrices between nodes [math]\displaystyle{ i }[/math] and [math]\displaystyle{ j }[/math], respectively.
用 < math > a { ij } </math > 和 < math > w { ij } </math > 分别作为 < math > i </math > 和 < math > < j </math > 节点之间的邻接矩阵和权值矩阵。
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.
类似于 无标度网络Scale free networks中度的 幂律分布Power law distribution，节点的强度也服从 幂律分布Power law distribution。
- [math]\displaystyle{ s(k) \approx k^\beta }[/math]
A study of the average value [math]\displaystyle{ s(b) }[/math] of the strength for vertices with betweenness [math]\displaystyle{ b }[/math] shows that the functional behavior can be approximated by a scaling form [1]
A study of the average value [math]\displaystyle{ s(b) }[/math] of the strength for vertices with betweenness [math]\displaystyle{ b }[/math] shows that the functional behavior can be approximated by a scaling form
对具有介数[math]\displaystyle{ b }[/math]的节点强度的平均值[math]\displaystyle{ s(b) }[/math]的研究表明，功能行为可以用缩放形式来近似
- [math]\displaystyle{ s(b)\approx b^{\alpha} }[/math]
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渗流中心性定义了在给定时间内，通过一个给定节点的渗流路径的比例。“渗流路径”是一对节点之间的最短路径，其中源节点被渗流的（例如，被感染）。目标节点可以是渗流的或非渗流的，或处于部分渗流状态。
- [math]\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} }[/math]
where [math]\displaystyle{ \sigma_{sr} }[/math] is total number of shortest paths from node [math]\displaystyle{ s }[/math] to node [math]\displaystyle{ r }[/math] and [math]\displaystyle{ \sigma_{sr}(v) }[/math] is the number of those paths that pass through [math]\displaystyle{ v }[/math]. The percolation state of the node [math]\displaystyle{ i }[/math] at time [math]\displaystyle{ t }[/math] is denoted by [math]\displaystyle{ {x^t}_i }[/math] and two special cases are when [math]\displaystyle{ {x^t}_i=0 }[/math] which indicates a non-percolated state at time [math]\displaystyle{ t }[/math] whereas when [math]\displaystyle{ {x^t}_i=1 }[/math] which indicates a fully percolated state at time [math]\displaystyle{ t }[/math]. 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 [math]\displaystyle{ \sigma_{sr} }[/math] is total number of shortest paths from node [math]\displaystyle{ s }[/math] to node [math]\displaystyle{ r }[/math] and [math]\displaystyle{ \sigma_{sr}(v) }[/math] is the number of those paths that pass through [math]\displaystyle{ v }[/math]. The percolation state of the node [math]\displaystyle{ i }[/math] at time [math]\displaystyle{ t }[/math] is denoted by [math]\displaystyle{ {x^t}_i }[/math] and two special cases are when [math]\displaystyle{ {x^t}_i=0 }[/math] which indicates a non-percolated state at time [math]\displaystyle{ t }[/math] whereas when [math]\displaystyle{ {x^t}_i=1 }[/math] which indicates a fully percolated state at time [math]\displaystyle{ t }[/math]. 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).
其中， < math >\sigma_{sr}</math > 是从节点 < math > s </math > 到节点 < math > r </math > 的最短路径的数量总数， < math > \sigma_{sr}(v) </math > 是其中通过节点 < math > v </math > 的路径总数。在时间 < math > t </math > 时，节点的渗流状态用 < math > {x^t}_i </math > 表示，两个特殊情况是当 < math > {x^t}_i=0</math >， 表示在时间[math]\displaystyle{ t }[/math]时是非渗流状态，而当 [math]\displaystyle{ {x^t}_i=1 }[/math]时， 表示在时间[math]\displaystyle{ t }[/math]时是完全渗流状态。两者之间的值表示部分渗流状态（例如，在一个城镇网络中，这是该城镇感染者的百分比）。
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 [math]\displaystyle{ O(NM) }[/math] 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 [math]\displaystyle{ O(N^3) }[/math].
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 [math]\displaystyle{ O(NM) }[/math] 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 [math]\displaystyle{ O(N^3) }[/math].
渗流路径的权重取决于分配给源节点的渗流水平，前提是源节点的渗流水平越高，源节点的路径就越重要。因此，位于源自高渗流节点的最短路径上的节点可能对渗流更为重要。PC 的定义也可以扩展到包括目标节点的权值。当采用Brandes的快速算法计算 Percolation centrality渗滤中心性时，计算时间复杂度为 < math > O(NM) </math >，如果计算需要考虑目标节点的权值，最高的计算时间复杂度为 < math > O(N^3) </math > 。
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 [math]\displaystyle{ \Theta(|V|^3) }[/math] 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 [math]\displaystyle{ O(|V|^2 \log |V| + |V| |E|) }[/math] time. On unweighted graphs, calculating betweenness centrality takes [math]\displaystyle{ O(|V| |E|) }[/math] 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)</math> 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 )</math> time. On unweighted graphs, calculating betweenness centrality takes )</math> time using Brandes' algorithm.
计算一个图中所有顶点的介数和 紧密中心性Closeness centralities涉及到计算图中所有节点对之间的最短路径，使用 Floyd-Warshall 算法时，这需要[math]\displaystyle{ \Theta(|V|^3) }[/math]的时间复杂度，改进后的算法不仅可以找到一条路径，还可以计算两个节点之间的所有最短路径。在稀疏图上，Johnson算法或Brandes算法可能更有效率，两者的时间复杂度为[math]\displaystyle{ O(|V|^2 \log |V| + |V| |E|) }[/math]。在未加权图上，使用 Brandes 算法计算 介数中心性Betweenness centrality需要的时间复杂度为[math]\displaystyle{ O(|V| |E|) }[/math]。模板: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.模板: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.
在计算一个图的所有节点的介数和 紧密中心性Closeness centralities时，假定图是无向的，并且图在允许自环和多边时是连通的。当专门处理网络图时，图通常没有自环或多边来维持简单的关系（其中的边表示两个人或节点之间的联系）。在这种情况下，使用 Brandes 算法将最终的中心性除以2，因为每条最短路径被计算两次。
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.
另一个算法通过引入一个超参数来控制勘探和开发之间的平衡，将计算测地线的弗里曼（Freeman）介数和所有路径上计算纽曼（Newman）介数的结果进行了推广。时间复杂度是图中的边数乘以节点数。模板:Sfnp
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.
中心性的概念也扩展到了群体层次。[3]群体介数中心性反映了通过一组节点连接非组成员节点对的测地线所占的比例。修改了计算所有节点之间的介数中心性的Brandes算法，以计算具有相同渐近运行时间的一组节点之间的群体介数中心性。
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) .
介数中心性Betweenness centrality与网络的连通性有关，如果高介数顶点被移除，就有可能断开图的连接（参见割集）。
See also另请参阅
Notes 备注
- ↑ A. Barrat, M. Barthelemy, R. Pastor-Satorras, and A. Vespignani. The architecture of complex weighted networks. PNAS (2004) vol. 101 no. 11
- ↑ 2.0 2.1 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.0 3.1 3.2 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 参考文献
- Brandes, Ulrik (2001). "A faster algorithm for betweenness centrality" (PDF). Journal of Mathematical Sociology. 25 (2): 163–177. CiteSeerX 10.1.1.11.2024. doi:10.1080/0022250x.2001.9990249. Archived from the original (PDF) on 2017-10-13. Retrieved 2018-11-18.
{{cite journal}}: Invalid|ref=harv(help)
- Freeman
1 = Freeman, Linton
1 = Linton (1977). "A set of measures of centrality based on betweenness". Sociometry. 40 (1): 35–41. doi:10.2307/3033543. JSTOR 3033543.
{{cite journal}}: Invalid|ref=harv(help); line feed character in|first1=at position 7 (help); line feed character in|last1=at position 8 (help)
- Goh, K. I.; Kahng, B.; Kim, D. (2001). "Universal Behavior of Load Distribution in Scale-Free Networks". Physical Review Letters. 87 (27): 278701. arXiv:cond-mat/0106565. Bibcode:2001PhRvL..87A8701G. doi:10.1103/physrevlett.87.278701.
{{cite journal}}: Invalid|ref=harv(help)
- 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.
{{cite journal}}: Invalid|ref=harv(help)
- 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.
{{cite journal}}: Invalid|ref=harv(help)
- 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