Maximum betweenness centrality: approximability and tractable cases

DOI10.1007/978-3-642-19094-0_4zbMATH Open1317.68277arXiv1008.3503OpenAlexW1873406145MaRDI QIDQ3078375FDOQ3078375

Authors: Martin Fink, Joachim Spoerhase 

Publication date: 20 February 2011

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

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.

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

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

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)

Cites Work

• A threshold of ln n for approximating set cover
• The centrality of groups and classes
• The hardness of approximation: Gap location
• A faster algorithm for betweenness centrality*
• The budgeted maximum coverage problem
• A note on maximizing a submodular set function subject to a knapsack constraint
• Title not available (Why is that?)
• Title not available (Why is that?)
• Incremental deployment of network monitors based on Group Betweenness Centrality

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
• Title not available (Why is that?)
• 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)