Historical betweenness centrality and its computation
摘要
In network analysis, the betweenness centrality is a fundamental metric for identifying the critical intermediary nodes. Since most real-world networks carry temporal information on edges, recent studies have proposed a variety of temporal betweenness centralities (TBCs). They require chronologically increasing timestamps along paths, making them ideal for propagation scenarios such as disease spreading. However, there are also many scenarios that involve a number of discrete sub-networks called snapshots at each timestamp. Research in this domain is still rather lacking. To bridge this gap, we propose historical betweenness centrality (HBC) for temporal networks, the first centrality metric designed to identify nodes that exhibit strong intermediation capabilities persistently within a given historical period. To compute HBC, we propose a novel temporal dependency accumulation theory and develop an efficient exact algorithm based on that. Since it is still theoretically complex for large-scale snapshots, we further design a more scalable approximate algorithm with probabilistic guaranty of deviation. Extensive experiments on real-world temporal networks demonstrate that HBC is an effective and insightful measurement which is inherently different from TBC. Meanwhile, our algorithms achieve significant improvements on efficiency and scalability.