更改
跳到导航
跳到搜索
第117行：
第117行： − + − + − The betweenness of a vertex + − v+ − v in a graph − G − := − ( − V − , − E − ) − G:=(V,E) with − V − V vertices is computed as follows: − − For each pair of vertices (s,t), compute the shortest paths between them. − For each pair of vertices (s,t), determine the fraction of shortest paths that pass through the vertex in question (here, vertex v). − Sum this fraction over all pairs of vertices (s,t). − More compactly the betweenness can be represented as:[22] − − C − B − ( − v − ) − = − ∑ − s − ≠ − v − ≠ − t − ∈ − V − σ − s − t − ( − v − ) − σ − s − t − C_B(v)= \sum_{s \neq v \neq t \in V}\frac{\sigma_{st}(v)}{\sigma_{st}} − where − σ − s − t − \sigma_{st} is total number of shortest paths from node − s − s to node − t − t and − σ − s − t − ( − v − ) − \sigma_{st}(v) is the number of those paths that pass through − v − v. The betweenness may be normalised by dividing through the number of pairs of vertices not including v, which for directed graphs is − ( − n − − − − ) − ( − n − − − 2 − ) − (n-1)(n-2) and for undirected graphs is − ( − n − − − 1 − ) − ( − n − − − 2 − ) − / − 2 − (n-1)(n-2)/2. For example, in an undirected star graph, the center vertex (which is contained in every possible shortest path) would have a betweenness of − ( − n − − − 1 − ) − ( − n − − − 2 − ) − / − 2 − (n-1)(n-2)/2 (1, if normalised) while the leaves (which are contained in no shortest paths) would have a betweenness of 0. − − From a calculation aspect, both betweenness and closeness centralities of all vertices in a graph involve calculating the shortest paths between all pairs of vertices on a graph, which requires − O − ( − V − 3 − ) − {\displaystyle O(V^{3})} time with the Floyd–Warshall algorithm. However, on sparse graphs, Johnson's algorithm may be more efficient, taking − O − ( − V − 2 − log − − V − + − V − E − ) − O(V^2 \log V + V E) time. In the case of unweighted graphs the calculations can be done with Brandes' algorithm[22] which takes − O − ( − V − E − ) − O(V E) time. Normally, these algorithms assume 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.[22]
→中介中心性/中间中心性
和谐中心度是Marchiori 和 Latora (2000)<ref name="marchiorilatora2000">{{citation| journal = Physica A: Statistical Mechanics and its Applications | last1 = Marchiori | first1 = Massimo | last2 = Latora | first2 = Vito | year = 2000 | volume = 285 | issue = 3–4 | pages = 539–546 | title = Harmony in the small-world | doi=10.1016/s0378-4371(00)00311-3| arxiv = cond-mat/0008357 | bibcode = 2000PhyA..285..539M }}</ref>提出的，随后 Dekker (2005)取名为“价值中心度” （"valued centrality"<ref>{{cite journal|first1=Anthony|last1=Dekker|title=Conceptual Distance in Social Network Analysis|journal=Journal of Social Structure|volume=6|issue=3|year=2005|url=http://www.cmu.edu/joss/content/articles/volume6/dekker/index.html}}</ref>）， Rochat (2009)也提出过类似的概念.<ref>{{cite conference | author = Yannick Rochat | title = Closeness centrality extended to unconnected graphs: The harmonic centrality index | conference = Applications of Social Network Analysis, ASNA 2009 | url = http://infoscience.epfl.ch/record/200525/files/%5bEN%5dASNA09.pdf }}</ref>
和谐中心度是Marchiori 和 Latora (2000)<ref name="marchiorilatora2000">{{citation| journal = Physica A: Statistical Mechanics and its Applications | last1 = Marchiori | first1 = Massimo | last2 = Latora | first2 = Vito | year = 2000 | volume = 285 | issue = 3–4 | pages = 539–546 | title = Harmony in the small-world | doi=10.1016/s0378-4371(00)00311-3| arxiv = cond-mat/0008357 | bibcode = 2000PhyA..285..539M }}</ref>提出的，随后 Dekker (2005)取名为“价值中心度” （"valued centrality"<ref>{{cite journal|first1=Anthony|last1=Dekker|title=Conceptual Distance in Social Network Analysis|journal=Journal of Social Structure|volume=6|issue=3|year=2005|url=http://www.cmu.edu/joss/content/articles/volume6/dekker/index.html}}</ref>）， Rochat (2009)也提出过类似的概念.<ref>{{cite conference | author = Yannick Rochat | title = Closeness centrality extended to unconnected graphs: The harmonic centrality index | conference = Applications of Social Network Analysis, ASNA 2009 | url = http://infoscience.epfl.ch/record/200525/files/%5bEN%5dASNA09.pdf }}</ref>
===中介中心性/中间中心性===
===介数中心性===
Betweenness is a centrality measure of a vertex within a graph (there is also edge betweenness, which is not discussed here). Betweenness centrality quantifies the number of times a node acts as a bridge along the shortest path between two other nodes. It was introduced as a measure for quantifying the control of a human on the communication between other humans in a social network by Linton Freeman[21] In his conception, vertices that have a high probability to occur on a randomly chosen shortest path between two randomly chosen vertices have a high betweenness.
在图论中，介数中心性 Betweenness Centrality是基于最短路径针对网络图中心性的衡量标准之一。针对全连接网络图，其中任意两个节点均至少存在一个最短路径，在无权重网络图中该最短路径是路径包含边的数量求和，加权网络图中该最短路径则是路径包含边的权重求和。每个节点的介数中心性即为这些最短路径穿过该节点的次数。
介数中心性在网络理论中有广泛的应用：它代表了某节点与其他节点之间的互动程度。 例如，在通信网络中，一个有更高介数中心性的节点在网络中有更强的控制能力，因为更多的信息传递时将通过该节点。 介数中心性被用作为对中心性的一种常见测量方式:[1] 它适用于解决网络理论中的许多问题，包括与社会网络、生物、运输和科学合作等方面相关的问题。
虽然早期的研究人员曾直观地描述了介数的中心性，但Freeman在1977年给了第一个介数中心性的正式定义。
1
===特征向量中心性===
===特征向量中心性===