863
个编辑
更改
跳到导航
跳到搜索
第7行：
第7行： − + − + − + − + 第21行：
第21行： − + 第58行：
第58行： − + − + 第70行：
第70行： − + 第81行：
第81行： − + 第91行：
第91行： − + − + 第99行：
第99行： − + − + − + 第113行：
第113行： − +
无编辑摘要
根据每个顶点的介数中心性从最小(红色)到最大(蓝色)着色的无向图。
根据每个顶点的介数中心性从最小(红色)到最大(蓝色)着色的无向图。
在图论中，'''<font color="#ff8000"> 介数中心性Betweenness centrality</font>'''是基于最短路径的图中心性的一种度量。对于连通图中的每一对节点，在节点之间至少存在一条最短路径，使得路径通过的边数(对于未加权图)或者边权重的和(对于加权图)最小。节点的中心性是经过该节点的最短路径的数量。
在图论中，''' 介数中心性Betweenness centrality'''是基于最短路径的图中心性的一种度量。对于连通图中的每一对节点，在节点之间至少存在一条最短路径，使得路径通过的边数(对于未加权图)或者边权重的和(对于加权图)最小。节点的中心性是经过该节点的最短路径的数量。
'''<font color="#ff8000"> 介数中心性Betweenness centrality</font>'''的提出为中心性的衡量提供了一般的标准: 它适用于网络理论中广泛的问题，包括与社会网络、生物学、交通和科学合作有关的问题。尽管早期的学者直观地将中心性描述为基于介数，但是给出了'''<font color="#ff8000"> 介数中心性Betweenness centrality</font>'''的第一个正式定义。
''' 介数中心性Betweenness centrality'''的提出为中心性的衡量提供了一般的标准: 它适用于网络理论中广泛的问题，包括与社会网络、生物学、交通和科学合作有关的问题。尽管早期的学者直观地将中心性描述为基于介数，但是给出了''' 介数中心性Betweenness centrality'''的第一个正式定义。
'''<font color="#ff8000"> 介数中心性Betweenness centrality</font>'''在网络理论中有着广泛的应用，它代表了节点之间相互独立的程度。例如，在远程通信网络中，具有较高'''<font color="#ff8000"> 介数中心性Betweenness centrality</font>'''的节点将对网络有更多的控制，因为有更多的信息会通过该节点。
''' 介数中心性Betweenness centrality'''在网络理论中有着广泛的应用，它代表了节点之间相互独立的程度。例如，在远程通信网络中，具有较高''' 介数中心性Betweenness centrality'''的节点将对网络有更多的控制，因为有更多的信息会通过该节点。
== 定义 ==
== 定义 ==
一个节点 < math > v </math > 的'''<font color="#ff8000"> 介数中心性Betweenness centrality</font>'''通过以下表达式给出:
一个节点 < math > v </math > 的''' 介数中心性Betweenness centrality'''通过以下表达式给出:
:<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>
其中 < math > sigma { st } </math > 是从节点 < math > s </math > 到节点 < math > t </math >的最短路径总数， < math > sigma { st }(v) </math >是其中通过节点<math>v</math>的路径数量。
其中 < math > sigma { st } </math > 是从节点 < math > s </math > 到节点 < math > t </math >的最短路径总数， < math > sigma { st }(v) </math >是其中通过节点<math>v</math>的路径数量。
注意，如公式中求和指标所示，一个节点的'''<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 > 是巨组元中的节点数。请注意，当每一条最短路径都通过一个节点时，这个节点达到可以缩放的最大可能值。事实往往并非如此，可以在不损失精度的情况下执行标准化
注意，如公式中求和指标所示，一个节点的''' 介数中心性Betweenness centrality'''与节点对的数量成比例缩放。因此，计算可以通过除以不包括 < 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>\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>
:<math>\eta=\frac{\gamma -1}{\delta -1}</math>
:<math>\eta=\frac{\gamma -1}{\delta -1}</math>
重要的指数是 < math > eta </math > ，它描述了'''<font color="#ff8000"> 介数中心性Betweenness centrality</font>'''如何依赖于连通性。当所有的最短路径都经过一个节点时，这种情况使节点的'''<font color="#ff8000"> 介数中心性Betweenness centrality</font>'''最大化，这对应于一个树结构(一个没有分簇的网络)。在树形网络的情况下，达到了 < math > eta = 2 </math > 的最大值。
重要的指数是 < math > eta </math > ，它描述了''' 介数中心性Betweenness centrality'''如何依赖于连通性。当所有的最短路径都经过一个节点时，这种情况使节点的''' 介数中心性Betweenness centrality'''最大化，这对应于一个树结构(一个没有分簇的网络)。在树形网络的情况下，达到了 < math > eta = 2 </math > 的最大值。
:<math>\eta = 2 \rarr \delta = \frac{\gamma +1}{2} </math>
:<math>\eta = 2 \rarr \delta = \frac{\gamma +1}{2} </math>
< math > eta </math > 的最大值(也是 < math > delta </math > 的最小值)为具有'''<font color="#32CD32"> 非零分簇Non-vanishing clustering</font>'''的网络的负载指数设置了界限。
< math > eta </math > 的最大值(也是 < math > delta </math > 的最小值)为具有'''<font color="#32CD32"> 非零分簇Non-vanishing clustering'''的网络的负载指数设置了界限。
:<math>\eta \le 2 \rarr \delta \ge \frac{\gamma +1}{2} </math>
:<math>\eta \le 2 \rarr \delta \ge \frac{\gamma +1}{2} </math>
===真实网络===
===真实网络===
现实世界中的'''<font color="#ff8000"> 无标度网络Scale free networks</font>'''，如互联网，也遵循幂律负载分布。<ref name="Goh2">Kwang-Il Goh, Eulsik Oh, Hawoong Jeong, Byungnam Kahng, and Doochul Kim. Classification of scale-free networks. PNAS (2002) vol. 99 no. 2</ref> 这是一个直观的结果。无标度网络通过创建一些比大多数网络具有更高连通性的枢纽节点，从而在网络中实现较短的路径长度。由于这种额外的连接，这些枢纽节点自然会承担更高的负载。
现实世界中的''' 无标度网络Scale free networks'''，如互联网，也遵循幂律负载分布。<ref name="Goh2">Kwang-Il Goh, Eulsik Oh, Hawoong Jeong, Byungnam Kahng, and Doochul Kim. Classification of scale-free networks. PNAS (2002) vol. 99 no. 2</ref> 这是一个直观的结果。无标度网络通过创建一些比大多数网络具有更高连通性的枢纽节点，从而在网络中实现较短的路径长度。由于这种额外的连接，这些枢纽节点自然会承担更高的负载。
==加权网络==
==加权网络==
类似于'''<font color="#ff8000"> 无标度网络Scale free networks</font>'''中度的'''<font color="#ff8000"> 幂律分布Power law distribution</font>'''，节点的强度也服从'''<font color="#ff8000"> 幂律分布Power law distribution</font>'''。
类似于''' 无标度网络Scale free networks'''中度的''' 幂律分布Power law distribution'''，节点的强度也服从''' 幂律分布Power law distribution'''。
:<math>s(k) \approx k^\beta </math>
:<math>s(k) \approx k^\beta </math>
=='''渗流中心性'''==
=='''渗流中心性'''==
'''<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>
''' Percolation centrality渗流中心性'''是加权的''' 介数中心性Betweenness centrality'''的一种形式，但它在计算该权重时考虑了每条最短路径的源节点和目标节点的“状态”。在许多情况下，复杂网络中都会出现“传染”的渗流现象。例如，病毒或细菌感染可以通过人们的社交网络传播，也就是所谓的接触网络。还可以在更高的抽象层次上考虑疾病的传播问题，设想通过公路、铁路或空中连接起来的城镇或人口中心网络。计算机病毒可以通过计算机网络传播。关于商业活动和交易的谣言或新闻也可以通过人们的社交网络传播。在所有这些情况下，一种“传染病”在一个复杂网络的链接上传播，随着它的传播，无论是可恢复的还是不可恢复的，都会改变节点的“状态”。例如，在流行病学情况下，随着传染病的扩散，个体从“易感”状态转变为“感染”状态。在上面的例子中，随着传染病的传播，每个节点的状态可以是二元的（如接收/没有接收到一条信息）、离散的（易感/受感染/康复），甚至是连续的（如一个城镇中受感染的人群比例）。这些情景的共同特点是，传染病的传播导致网络中节点状态的改变。''' Percolation centrality渗流中心性'''(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>
'''<font color="#ff8000"> Percolation centrality渗流中心性</font>'''定义了在给定时间内，通过一个给定节点的渗流路径的比例。“渗流路径”是一对节点之间的最短路径，其中源节点被渗流的（例如，被感染）。目标节点可以是渗流的或非渗流的，或处于部分渗流状态。
''' Percolation centrality渗流中心性'''定义了在给定时间内，通过一个给定节点的渗流路径的比例。“渗流路径”是一对节点之间的最短路径，其中源节点被渗流的（例如，被感染）。目标节点可以是渗流的或非渗流的，或处于部分渗流状态。
:<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>
其中， < 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>时是完全渗流状态。两者之间的值表示部分渗流状态（例如，在一个城镇网络中，这是该城镇感染者的百分比）。
其中， < 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>时是完全渗流状态。两者之间的值表示部分渗流状态（例如，在一个城镇网络中，这是该城镇感染者的百分比）。
渗流路径的权重取决于分配给源节点的渗流水平，前提是源节点的渗流水平越高，源节点的路径就越重要。因此，位于源自高渗流节点的最短路径上的节点可能对渗流更为重要。PC 的定义也可以扩展到包括目标节点的权值。当采用Brandes的快速算法计算'''<font color="#ff8000"> Percolation centrality渗滤中心性</font>'''时，计算时间复杂度为 < math > O(NM) </math >，如果计算需要考虑目标节点的权值，最高的计算时间复杂度为 < math > O(N^3) </math > 。
渗流路径的权重取决于分配给源节点的渗流水平，前提是源节点的渗流水平越高，源节点的路径就越重要。因此，位于源自高渗流节点的最短路径上的节点可能对渗流更为重要。PC 的定义也可以扩展到包括目标节点的权值。当采用Brandes的快速算法计算''' Percolation centrality渗滤中心性'''时，计算时间复杂度为 < math > O(NM) </math >，如果计算需要考虑目标节点的权值，最高的计算时间复杂度为 < math > O(N^3) </math > 。
== 算法==
== 算法==
计算一个图中所有顶点的介数和'''<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}}
计算一个图中所有顶点的介数和''' 紧密中心性Closeness centralities'''涉及到计算图中所有节点对之间的最短路径，使用 Floyd-Warshall 算法时，这需要[[big theta|<math>\Theta(|V|^3)</math>]]的时间复杂度，改进后的算法不仅可以找到一条路径，还可以计算两个节点之间的所有最短路径。在稀疏图上，Johnson算法或Brandes算法可能更有效率，两者的时间复杂度为[[Big O notation|<math>O(|V|^2 \log |V| + |V| |E|)</math>]]。在未加权图上，使用 Brandes 算法计算''' 介数中心性Betweenness centrality'''需要的时间复杂度为[[Big O notation|<math>O(|V| |E|)</math>]]。{{Sfnp|Brandes|2001|p=1}}
在计算一个图的所有节点的介数和'''<font color="#ff8000"> 紧密中心性Closeness centralities</font>'''时，假定图是无向的，并且图在允许自环和多边时是连通的。当专门处理网络图时，图通常没有自环或多边来维持简单的关系（其中的边表示两个人或节点之间的联系）。在这种情况下，使用 Brandes 算法将最终的中心性除以2，因为每条最短路径被计算两次。
在计算一个图的所有节点的介数和''' 紧密中心性Closeness centralities'''时，假定图是无向的，并且图在允许自环和多边时是连通的。当专门处理网络图时，图通常没有自环或多边来维持简单的关系（其中的边表示两个人或节点之间的联系）。在这种情况下，使用 Brandes 算法将最终的中心性除以2，因为每条最短路径被计算两次。
另一个算法通过引入一个超参数来控制勘探和开发之间的平衡，将计算测地线的弗里曼（Freeman）介数和所有路径上计算纽曼（Newman）介数的结果进行了推广。时间复杂度是图中的边数乘以节点数。{{Sfnp|Mantrach|2010}}
另一个算法通过引入一个超参数来控制勘探和开发之间的平衡，将计算测地线的弗里曼（Freeman）介数和所有路径上计算纽曼（Newman）介数的结果进行了推广。时间复杂度是图中的边数乘以节点数。{{Sfnp|Mantrach|2010}}
== 相关概念 ==
== 相关概念 ==
'''<font color="#ff8000"> 介数中心性Betweenness centrality</font>'''与网络的连通性有关，如果高介数顶点被移除，就有可能断开图的连接（参见割集）。
''' 介数中心性Betweenness centrality'''与网络的连通性有关，如果高介数顶点被移除，就有可能断开图的连接（参见割集）。
== 另请参阅==
== 另请参阅==