Keyword-based Betweenness Centrality Maximization in Attributed Graphs

RAIDS Lab Authors

Zhengyi Yang

Director

Details

Research Area

Tags

Resources

Abstract

Betweenness centrality is a key concept in graph analysis that measures the significance of a node by counting how often it appears in the shortest paths between other nodes. The task of betweenness centrality maximization, which seeks to identify a set of nodes with the highest centrality scores, is crucial in various real-world applications. Most existing studies about betweenness centrality focus on general graphs. However, in reality, users in networks are usually associated with attributes such as preferences, which play an essential role in analyzing the properties of networks. Therefore, the traditional betweenness centrality is not applicable to the attribute graphs. Motivated by this, we propose a novel concept called Keyword-based Betweenness Centrality (KBC), which quantifies the number of times each node acts as the midpoint of shortest paths between nodes having one of the given attributes. Given an attribute graph G, a query attribute set Q, and a positive integer k, in this paper, we aim to find a node set of size no larger than k so that its KBC value based on Q is maximized. To address this problem, we propose a keyword-based hyper-edge sampler and devise an algorithm achieving the approximation guarantee of (1 - 1/e - epsilon) with at least 1 - delta probability. Extensive experiments on four real networks demonstrate the efficiency and effectiveness of our proposed algorithms.

Author Affiliations

@inproceedings{li2024keyword,
  title = {Keyword-Based Betweenness Centrality Maximization in Attributed Graphs},
  author = {Li, Xiao and Wu, Yanping and Wang, Xiaoyang and Yang, Zhengyi and Zhang, Wenjie and Zhang, Ying},
  editor = {Chen, Tong and Cao, Yang and Nguyen, Quoc Viet Hung and Nguyen, Thanh Tam},
  booktitle = {Databases Theory and Applications},
  year = {2025},
  publisher = {Springer Nature Singapore},
  address = {Singapore},
  pages = {209--223},
  isbn = {978-981-96-1242-0}
}