561
个编辑
更改
→Betweenness centrality
==Betweenness centrality==
==Betweenness centrality==
=='''<font color="#ff8000"> 中介中心性Betweenness centrality</font>'''==
{{Main|Betweenness centrality}}
{{Main|Betweenness centrality}}
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 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 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 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.
中介性是图中顶点的中心性度量(也有边中介性，这里没有讨论)。'''<font color="#ff8000"> 中介中心性Betweenness centrality</font>'''量化了一个节点沿着其他两个节点之间的最短路径充当桥梁的次数。在林顿 · 弗里曼的概念中，在两个随机选择的顶点之间随机选择的最短路径上出现概率高的顶点具有很高的中介性。
where <math>\sigma_{st}</math> is 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>. The betweenness may be normalised by dividing through the number of pairs of vertices not including v, which for directed graphs is <math>(n-1)(n-2)</math> and for undirected graphs is <math>(n-1)(n-2)/2</math>. For example, in an undirected star graph, the center vertex (which is contained in every possible shortest path) would have a betweenness of <math>(n-1)(n-2)/2</math> (1, if normalised) while the leaves (which are contained in no shortest paths) would have a betweenness of 0.
where <math>\sigma_{st}</math> is 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>. The betweenness may be normalised by dividing through the number of pairs of vertices not including v, which for directed graphs is <math>(n-1)(n-2)</math> and for undirected graphs is <math>(n-1)(n-2)/2</math>. For example, in an undirected star graph, the center vertex (which is contained in every possible shortest path) would have a betweenness of <math>(n-1)(n-2)/2</math> (1, if normalised) while the leaves (which are contained in no shortest paths) would have a betweenness of 0.
其中 < math > sigma { st } </math > 是从节点 < math > s </math > 到节点 < math > t </math > 和 < math > sigma { st }(v) </math > 是通过 < math > v </math > 的路径数。有向图是 < math > (n-1)(n-2) </math > ，无向图是 < math > (n-1)(n-2)/2 </math > 。例如，在一个无向星图中，中心顶点(包含在每个可能的最短路径中)的中间性为 < math > (n-1)(n-2)/2 </math > (1，如果标准化) ，而叶子(包含在没有最短路径中)的中间性为0。
其中 < math > sigma { st } </math > 是从节点 < math > s </math > 到节点 < math > t </math > 和 < math > sigma { st }(v) </math > 是通过 < math > v </math > 的路径数。有向图是 < math > (n-1)(n-2) </math > ，无向图是 < math > (n-1)(n-2)/2 </math > 。例如，在一个无向星图中，中心顶点(包含在每个可能的最短路径中)的中介性为 < math > (n-1)(n-2)/2 </math > (1，如果标准化) ，而叶子(包含在没有最短路径中)的中介性为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 <math>O(V^3)</math> time with the Floyd–Warshall algorithm. However, on sparse graphs, Johnson's algorithm may be more efficient, taking <math>O(V^2 \log V + V E)</math> time. In the case of unweighted graphs the calculations can be done with Brandes' algorithm which takes <math>O(V E)</math> 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.
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 <math>O(V^3)</math> time with the Floyd–Warshall algorithm. However, on sparse graphs, Johnson's algorithm may be more efficient, taking <math>O(V^2 \log V + V E)</math> time. In the case of unweighted graphs the calculations can be done with Brandes' algorithm which takes <math>O(V E)</math> 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.
从计算的角度来看，图中所有顶点的'''<font color="#ff8000"> 中介和紧密中心性Betweenness and Closeness centralities</font>'''都涉及到计算图中所有顶点对之间的最短路径，这就需要用 Floyd-Warshall 算法计算时间。然而，对于稀疏图，约翰逊算法的效率可能更高，采用 < math > o (v ^ 2 log v + v e) </math > 时间。在不加权图的情况下，可以用 Brandes 的算法进行计算，该算法需要 < math > o (v e) </math > 时间。一般情况下，这些算法假定图是无向的，并且连通图中允许有圈和多条边。当专门处理网络图时，图通常没有环或多条边来维持简单的关系(其中的边表示两个人或顶点之间的联系)。在这种情况下，使用 Brandes 的算法将最终的中心性分数除以2来计算每条被重复计算的最短路径。
==Eigenvector centrality==
==Eigenvector centrality==