介数中心性 - 版本历史

薄荷：/* 加权网络 */

2022-02-28T14:27:20Z

加权网络

薄荷：/* 另请参阅 */

2022-02-28T14:27:02Z

另请参阅

薄荷：/* 模型网络 */

2022-02-28T14:23:56Z

模型网络

薄荷：/* 定义 */

2022-02-28T14:22:14Z

定义

薄荷：/* 参考文献 */

2021-10-25T13:36:37Z

参考文献

2021年10月25日 (一) 13:36 薄荷

2021-10-25T13:36:00Z

不是海绵宝宝：/* 定义 */

2021-08-21T03:35:14Z

定义

不是海绵宝宝：/* 模型网络 */

2021-08-21T03:34:55Z

模型网络

不是海绵宝宝：/* 算法 */

2021-08-21T03:33:05Z

算法

不是海绵宝宝：/* 相关概念 */

2021-08-21T03:32:19Z

←上一版本		2022年2月28日 (一) 14:27的版本
第80行：		第80行：


−	类似于''' 无标度网络Scale free networks'''中度的[[~~幂律分布Power~~ law distribution]]，节点的强度也服从''' 幂律分布Power law distribution'''。	+	类似于''' 无标度网络Scale free networks'''中度的[[幂律分布 Power law distribution]]，节点的强度也服从''' 幂律分布Power law distribution'''。

	:<math>s(k) \approx k^\beta </math>		:<math>s(k) \approx k^\beta </math>

@@ 第115行： / 第115行： @@
 == 另请参阅==
-* [[Centrality]]
+</br>
 ==备注==

@@ 第45行： / 第45行： @@
 :<math>g(k) \approx k^\eta</math>.
-其中 <mat > g (k) </math> 是度为 <math> k </math> 的节点的平均负载。指数 <mat > delta </math> 和 <mat > eta </math> 不是独立的，因为方程(1)指出<ref name="Bart">M. Barthélemy. Betweenness centrality in large complex networks. Eur. Phys. J. B 38, 163–168 (2004)</ref>
+其中 <math> g (k) </math> 是度为 <math> k </math> 的节点的平均负载。指数 <math> delta </math> 和 <math> eta </math> 不是独立的，因为方程(1)指出<ref name="Bart">M. Barthélemy. Betweenness centrality in large complex networks. Eur. Phys. J. B 38, 163–168 (2004)</ref>
 :<math>P(g)= \int P(k) \delta (g-k^\eta) dk</math>
@@ 第58行： / 第58行： @@
 :<math>\eta=\frac{\gamma -1}{\delta -1}</math>
-重要的指数是 <mat > eta </math> ，它描述了介数中心性Betweenness centrality如何依赖于连通性。当所有的最短路径都经过一个节点时，这种情况使节点的介数中心性Betweenness centrality最大化，这对应于一个树结构(一个没有分簇的网络)。在树形网络的情况下，达到了 <mat > 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 </math> 的最大值(也是 <mat > delta </math> 的最小值)为具有''' 非零分簇Non-vanishing clustering'''的网络的负载指数设置了界限。
+<math> eta </math> 的最大值(也是 <mat > delta </math> 的最小值)为具有''' 非零分簇 Non-vanishing clustering'''的网络的负载指数设置了界限。
 :<math>\eta \le 2 \rarr \delta \ge \frac{\gamma +1}{2} </math>

@@ 第15行： / 第15行： @@
 == 定义 ==
-一个节点 < math > v </math > 的''' 介数中心性Betweenness centrality'''通过以下表达式给出:
+一个节点 <math> v </math> 的''' 介数中心性Betweenness centrality'''通过以下表达式给出:
 :<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>的路径数量。
-注意，如公式中求和指标所示，一个节点的介数中心性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 > 是巨组元中的节点数。请注意，当每一条最短路径都通过一个节点时，这个节点达到可以缩放的最大可能值。事实往往并非如此，可以在不损失精度的情况下执行标准化
+注意，如公式中求和指标所示，一个节点的介数中心性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>

@@ 第130行： / 第130行： @@
 *{{cite journal | last1=Brandes | first1=Ulrik | year=2001 | journal=Journal of Mathematical Sociology | volume=25 | issue=2 | pages=163&ndash;177 | title=A faster algorithm for betweenness centrality | url=https://algo.uni-konstanz.de/publications/b-fabc-01.pdf | ref=harv | doi=10.1080/0022250x.2001.9990249 | citeseerx=10.1.1.11.2024 | access-date=2018-11-18 | archive-url=https://web.archive.org/web/20171013152036/http://algo.uni-konstanz.de/publications/b-fabc-01.pdf | archive-date=2017-10-13 | url-status=dead }}
-*{{cite journal
+*{{cite journal |last1 = Freeman |first1 = Linton| year=1977| title = A set of measures of centrality based on betweenness
 | journal = Sociometry
 | volume=40
@@ 第174行： / 第167行： @@
 *{{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&ndash;25:27|doi=10.1145/1734213.1734219}}
 {{Refend}}
 ==编者推荐==

@@ 第9行： / 第9行： @@
 在图论中，'''介数中心性Betweenness centrality'''是基于最短路径的图中心性的一种度量。对于连通图中的每一对节点，在节点之间至少存在一条最短路径，使得路径通过的边数(对于未加权图)或者边权重的和(对于加权图)最小。节点的中心性是经过该节点的最短路径的数量。
- 介数中心性Betweenness centrality的提出为中心性的衡量提供了一般的标准: 它适用于网络理论中广泛的问题，包括与社会网络、生物学、交通和科学合作有关的问题。尽管早期的学者直观地将中心性描述为基于介数，但是给出了 介数中心性Betweenness centrality的第一个正式定义。
+介数中心性Betweenness centrality的提出为中心性的衡量提供了一般的标准: 它适用于网络理论中广泛的问题，包括与社会网络、生物学、交通和科学合作有关的问题。尽管早期的学者直观地将中心性描述为基于介数，但是给出了 介数中心性Betweenness centrality的第一个正式定义。
- 介数中心性Betweenness centrality在网络理论中有着广泛的应用，它代表了节点之间相互独立的程度。例如，在远程通信网络中，具有较高 介数中心性Betweenness centrality的节点将对网络有更多的控制，因为有更多的信息会通过该节点。
+介数中心性Betweenness centrality在网络理论中有着广泛的应用，它代表了节点之间相互独立的程度。例如，在远程通信网络中，具有较高 介数中心性Betweenness centrality的节点将对网络有更多的控制，因为有更多的信息会通过该节点。
 == 定义 ==

@@ 第102行： / 第102行： @@
 == 算法==
-计算一个图中所有顶点的介数和''' 紧密中心性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>'''。
+计算一个图中所有顶点的'''介数和紧密中心性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>'''。
-在计算一个图的所有节点的介数和''' 紧密中心性Closeness centralities'''时，假定图是无向的，并且图在允许自环和多边时是连通的。当专门处理网络图时，图通常没有自环或多边来维持简单的关系（其中的边表示两个人或节点之间的联系）。在这种情况下，使用 Brandes 算法将最终的中心性除以2，因为每条最短路径被计算两次。
+在计算一个图的所有节点的介数和紧密中心性Closeness centralities时，假定图是无向的，并且图在允许自环和多边时是连通的。当专门处理网络图时，图通常没有自环或多边来维持简单的关系（其中的边表示两个人或节点之间的联系）。在这种情况下，使用 Brandes 算法将最终的中心性除以2，因为每条最短路径被计算两次。
 另一个算法通过引入一个超参数来控制勘探和开发之间的平衡，将计算测地线的弗里曼（Freeman）介数和所有路径上计算纽曼（Newman）介数的结果进行了推广。时间复杂度是图中的边数乘以节点数。

@@ 第112行： / 第112行： @@
 == 相关概念 ==
-''' 介数中心性Betweenness centrality'''与网络的连通性有关，如果高介数顶点被移除，就有可能断开图的连接（参见割集）。
+介数中心性Betweenness centrality 与网络的连通性有关，如果高介数顶点被移除，就有可能断开图的连接（参见割集）。
 == 另请参阅==