Maximum betweenness centrality: approximability and tractable cases

DOI10.1007/978-3-642-19094-0_4MaRDI QIDQ3078375zbMATH OpenOpenAlexFDO

Authors Martin Fink, Joachim Spoerhase

Publication date 20 February 2011

Published in WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1008.3503

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Abstract: The Maximum Betweenness Centrality problem (MBC) can be defined as follows. Given a graph find a $k$-element node set $C$ that maximizes the probability of detecting communication between a pair of nodes $s$ and $t$ chosen uniformly at random. It is assumed that the communication between $s$ and $t$ is realized along a shortest $s$--$t$ path which is, again, selected uniformly at random. The communication is detected if the communication path contains a node of $C$. Recently, Dolev et al. (2009) showed that MBC is NP-hard and gave a $(1-1/e)$-approximation using a greedy approach. We provide a reduction of MBC to Maximum Coverage that simplifies the analysis of the algorithm of Dolev et al. considerably. Our reduction allows us to obtain a new algorithm with the same approximation ratio for a (generalized) budgeted version of MBC. We provide tight examples showing that the analyses of both algorithms are best possible. Moreover, we prove that MBC is APX-complete and provide an exact polynomial-time algorithm for MBC on tree graphs.

Recommendations

• On the maximum betweenness improvement problem
• Improving the betweenness centrality of a node by adding links
• Approximating Betweenness Centrality
• Better approximation of betweenness centrality
• scientific article; zbMATH DE number 7075920

Cites work

• scientific article; zbMATH DE number 1342117 (Why is no real title available?)
• scientific article; zbMATH DE number 5663542 (Why is no real title available?)
• A faster algorithm for betweenness centrality*
• A note on maximizing a submodular set function subject to a knapsack constraint
• A threshold of ln n for approximating set cover
• Incremental deployment of network monitors based on Group Betweenness Centrality
• The budgeted maximum coverage problem
• The centrality of groups and classes
• The hardness of approximation: Gap location

Cited in

(9)

• Decremental All-Pairs ALL Shortest Paths and Betweenness Centrality
• On the maximum connectivity improvement problem
• Finding groups with maximum betweenness centrality
• Finding groups with maximum betweenness centrality via integer programming with random path sampling
• scientific article; zbMATH DE number 7075920 (Why is no real title available?)
• An integer programming approach for finding the most and the least central cliques
• The parameterized complexity of maximum betweenness centrality
• A survey on optimization studies of group centrality metrics
• Betweenness estimation in OLSR-based multi-hop networks for distributed filtering

This page was built for publication: Maximum betweenness centrality: approximability and tractable cases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3078375)