Betweenness centrality measure assesses the importance of nodes in a graph and has been used in a variety of contexts. Betweenness centrality has also been extended to temporal graphs. Temporal graphs have edges that bear labels according to the time of the interactions between the nodes. Betweenness centrality has been extended to the temporal graph settings, and the notion of paths has been extended to temporal paths. Recent results by Bu{\ss} et al. and Rymar et al. showed that the betweenness centrality of all nodes in a temporal graph can be computed in O(n^3 T^2) or O(n^2 m T^2 ), where T is the number of time units, m the number of temporal edges and n the number of nodes. In this paper, we improve the running time analysis of these previous approaches to compute the betweenness centrality of all nodes in a temporal graph. We give an algorithm that runs in O(n m T + n^2 T ).
翻译：时间介数中心性测量评估图中节点的重要性，并且已被用于各种背景下。介数中心性也已被扩展到了时间图上。时间图拥有边缘会根据节点之间的交互时间而带有标签。介数中心性已经被扩展到时间图的设定，而路径概念也被扩展到时间路径上。Bu\{ss\}等人和Rymar等人的最近结果表明，所有节点在时间图中的介数中心性可以计算为O（n ^ 3 T ^ 2）或O（n ^ 2 m T ^ 2），其中T是时间单位数，m是时态边数，n是节点数。在本文中，我们改进了这些先前方法的运行时间分析，以计算时间图中所有节点的介数中心性。我们给出的算法运行时间为O（n m T + n ^ 2 T）。
相关内容
微信扫码咨询专知VIP会员