更改

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"> Percolation centrality渗流中心性</font>'''==

=='''<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.

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

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

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"> Percolation centrality渗滤中心性</font>'''定义为在给定时间内一个给定节点的过滤路径的比例。“渗滤路径”是一对节点之间的最短路径，其中源节点被渗滤(例如，被感染)。目标节点可以是过滤的或非过滤的，或处于部分过滤状态。

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 的定义也可以扩展到包括目标节点的权重。逾渗中心性计算运行在 < math > o (NM) </math > 时间，采用了 Brandes 快速算法的有效实现，如果计算需要考虑目标节点的权重，最坏情况下时间为 < math > o (n ^ 3) </math > 。

渗流路径的权重取决于分配给源节点的渗流水平，前提是源节点的渗流水平越高，源节点的路径就越重要。因此，位于源自高渗滤节点的最短路径上的节点可能对渗滤更为重要。PC 的定义也可以扩展到包括目标节点的权重。'''<font color="#ff8000"> Percolation centrality渗滤中心性</font>'''计算运行在 < math > o (NM) </math > 时间，采用了 Brandes 快速算法的有效实现，如果计算需要考虑目标节点的权重，最坏情况下时间为 < math > o (n ^ 3) </math > 。

== Algorithms ==

== Algorithms 算法==

Calculating the betweenness and closeness centralities of all the [[Vertex (graph theory)|vertices]] in a graph involves calculating the shortest paths between all pairs of vertices on a graph, which takes [[big theta|<math>\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 [[Big O notation|<math>O(|V|^2 \log |V| + |V| |E|)</math>]] time. On unweighted graphs, calculating betweenness centrality takes [[Big O notation|<math>O(|V| |E|)</math>]] time using Brandes' algorithm.{{Sfnp|Brandes|2001|p=1}}

Calculating the betweenness and closeness centralities of all the [[Vertex (graph theory)|vertices]] in a graph involves calculating the shortest paths between all pairs of vertices on a graph, which takes [[big theta|<math>\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 [[Big O notation|<math>O(|V|^2 \log |V| + |V| |E|)</math>]] time. On unweighted graphs, calculating betweenness centrality takes [[Big O notation|<math>O(|V| |E|)</math>]] time using Brandes' algorithm.{{Sfnp|Brandes|2001|p=1}}

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.

计算一个图中所有顶点的中间性和贴近度中心涉及到计算一个图中所有顶点对之间的最短路径，这需要 ^ 3) </math > 时间，使用 Floyd-Warshall 算法，修改后不仅可以找到一个，而且可以计算两个节点之间的所有最短路径。在稀疏图上，约翰逊算法或布兰德斯算法可能更有效率，两者都占用时间。在未加权图上，使用 Brandes 算法计算中间集中度需要 </math > 时间。

计算一个图中所有顶点的中间性和'''<font color="#ff8000"> 紧密中心性Closeness centralities</font>'''涉及到计算一个图中所有顶点对之间的最短路径，这需要 ^ 3) </math > 时间，使用 Floyd-Warshall 算法，修改后不仅可以找到一个，而且可以计算两个节点之间的所有最短路径。在稀疏图上，约翰逊算法或布兰德斯算法可能更有效率，两者都占用时间。在未加权图上，使用 Brandes 算法计算'''<font color="#ff8000"> 介数中心性Betweenness centrality</font>'''需要 </math > 时间。

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.

在计算一个图的所有顶点的中间性和贴近中心时，假定图是无向的，并且图是连通的。当专门处理网络图时，图通常没有环或多条边来维持简单的关系(其中的边表示两个人或顶点之间的联系)。在这种情况下，使用 Brandes 的算法将最终的中心性分数除以2来计算每条被重复计算的最短路径。

在计算一个图的所有顶点的中间性和'''<font color="#ff8000"> 紧密中心性Closeness centralities</font>'''时，假定图是无向的，并且图是连通的。当专门处理网络图时，图通常没有环或多条边来维持简单的关系(其中的边表示两个人或顶点之间的联系)。在这种情况下，使用 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.

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 介数和所有路径上纽曼介数的计算结果进行了推广。时间复杂度是图中的边数乘以节点数。

另一个算法通过引入一个超参数来控制勘探和开发之间的平衡，将大地测量学上计算的 Freeman（弗里曼） 介数和所有路径上纽曼介数的计算结果进行了推广。时间复杂度是图中的边数乘以节点数。

== Related concepts ==

== Related concepts相关概念 ==

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

''Betweenness centrality'' is related to a network's [[Connectivity (graph theory)|connectivity]], in so much as high betweenness vertices have the potential to disconnect graphs if removed (see [[Cut (graph theory)|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 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"> 介数中心性Betweenness centrality</font>'''与网络的连通性有关，在如此多的高中间性顶点中，如果移除了中断图(见割集)的可能性。

== See also ==

== See also 又及==

* [[Centrality]]

* [[Centrality]]

 

== Notes 备注==

== Notes ==

{{Reflist}}

{{Reflist}}

== References ==

== References 参考文献==

{{Refbegin|40em}}

{{Refbegin|40em}}