863
个编辑
更改
跳到导航
跳到搜索
第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，因为每条最短路径被计算两次。