<p>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.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Historical betweenness centrality and its computation

  • Zhenyu Mao,
  • Ming Zhong,
  • Yuanyuan Zhu,
  • Tieyun Qian,
  • Mengchi Liu,
  • Jeffrey Xu Yu

摘要

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.