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.

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

Keyword-Based Betweenness Centrality Maximization in Attributed Graphs

  • Xiao Li,
  • Yanping Wu,
  • Xiaoyang Wang,
  • Zhengyi Yang,
  • Wenjie Zhang,
  • Ying Zhang

摘要

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.