Improving the Betweenness Centrality of a Node by Adding Links

DOI10.1145/3166071zbMath1446.68111arXiv1702.05284OpenAlexW2592818482MaRDI QIDQ4555544

Pierluigi Crescenzi, Elisabetta Bergamini, Lorenzo Severini, Henning Meyerhenke, Yllka Velaj, Gianlorenzo D'Angelo

Publication date: 20 November 2018

Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

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

zbMATH Keywords

graph augmentationgreedy algorithmsnetwork analysisbetweenness centrality

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (6)

Compressive sensing of high betweenness centrality nodes in networks ⋮ On the fixed-parameter tractability of the maximum connectivity improvement problem ⋮ Hardness of bounding influence via graph modification ⋮ Unnamed Item ⋮ Optimizing node infiltrations in complex networks by a local search based heuristic ⋮ Exact and Approximate Algorithms for Computing Betweenness Centrality in Directed Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the approximability of the link building problem
• Augmenting graphs to minimize the diameter
• On the maximum betweenness improvement problem
• Improved approximability and non-approximability results for graph diameter decreasing problems
• On the computational complexity of dynamic graph problems
• Fast approximation of betweenness centrality through sampling
• Efficient algorithms for updating betweenness centrality in fully dynamic graphs
• Using shortcut edges to maximize the number of triangles in graphs
• A faster algorithm for betweenness centrality*
• Betweenness Centrality – Incremental and Faster
• The Design of Approximation Algorithms
• The Shortcut Problem - Complexity and Algorithms
• A threshold of ln n for approximating set cover
• Branching and bounds tighteningtechniques for non-convex MINLP
• Fully Dynamic Betweenness Centrality
• Minimizing the Diameter of a Network Using Shortcut Edges
• Minimizing Average Shortest Path Distances via Shortcut Edge Addition
• An analysis of approximations for maximizing submodular set functions—I
• Models for the Compressible Web
• Approximating Betweenness Centrality in Large Evolving Networks
• Computing Top-k Closeness Centrality Faster in Unweighted Graphs
• Better Approximation of Betweenness Centrality
• The Effect of New Links on Google Pagerank
• Approximating Betweenness Centrality in Fully Dynamic Networks

This page was built for publication: Improving the Betweenness Centrality of a Node by Adding Links