更改

删除8字节 、 2021年8月21日 (六) 11:33
第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)介数的结果进行了推广。时间复杂度是图中的边数乘以节点数。
 
另一个算法通过引入一个超参数来控制勘探和开发之间的平衡,将计算测地线的弗里曼(Freeman)介数和所有路径上计算纽曼(Newman)介数的结果进行了推广。时间复杂度是图中的边数乘以节点数。
863

个编辑