Improving the betweenness centrality of a node by adding links

DOI10.1145/3166071MaRDI QIDQ4555544zbMATH OpenOpenAlexFDO

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

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

betweenness centralitygraph augmentationgreedy algorithmsnetwork analysis

Mathematics Subject Classification ID

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

Abstract: Betweenness is a well-known centrality measure that ranks the nodes according to their participation in the shortest paths of a network. In several scenarios, having a high betweenness can have a positive impact on the node itself. Hence, in this paper we consider the problem of determining how much a vertex can increase its centrality by creating a limited amount of new edges incident to it. In particular, we study the problem of maximizing the betweenness score of a given node -- Maximum Betweenness Improvement (MBI) -- and that of maximizing the ranking of a given node -- Maximum Ranking Improvement (MRI). We show that MBI cannot be approximated in polynomial-time within a factor $(1-frac12e)$ and that MRI does not admit any polynomial-time constant factor approximation algorithm, both unless $P=NP$. We then propose a simple greedy approximation algorithm for MBI with an almost tight approximation ratio and we test its performance on several real-world networks. We experimentally show that our algorithm highly increases both the betweenness score and the ranking of a given node ant that it outperforms several competitive baselines. To speed up the computation of our greedy algorithm, we also propose a new dynamic algorithm for updating the betweenness of one node after an edge insertion, which might be of independent interest. Using the dynamic algorithm, we are now able to compute an approximation of MBI on networks with up to $10^5$ edges in most cases in a matter of seconds or a few minutes.

Recommendations

• On the maximum betweenness improvement problem
• Approximating betweenness centrality in large evolving networks
• scientific article; zbMATH DE number 7075920
• Approximating Betweenness Centrality in Fully Dynamic Networks
• Betweenness centrality -- incremental and faster

Cites work

• A faster algorithm for betweenness centrality*
• A threshold of ln n for approximating set cover
• An analysis of approximations for maximizing submodular set functions—I
• Approximating Betweenness Centrality in Fully Dynamic Networks
• Approximating betweenness centrality in large evolving networks
• Better approximation of betweenness centrality
• Betweenness centrality -- incremental and faster
• Branching and bounds tighteningtechniques for non-convex MINLP
• Computing top-k closeness centrality faster in unweighted graphs
• Directed scale-free graphs
• Efficient algorithms for updating betweenness centrality in fully dynamic graphs
• Fast approximation of betweenness centrality through sampling
• Fully dynamic betweenness centrality
• scientific article; zbMATH DE number 3580314 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 6917138 (Why is no real title available?)
• Improved approximability and non-approximability results for graph diameter decreasing problems
• KADABRA is an adaptive algorithm for betweenness via random approximation
• Minimizing Average Shortest Path Distances via Shortcut Edge Addition
• Minimizing the diameter of a network using shortcut edges
• Models for the Compressible Web
• On the approximability of the link building problem
• On the computational complexity of dynamic graph problems
• On the maximum betweenness improvement problem
• The design of approximation algorithms
• The Effect of New Links on Google Pagerank
• The shortcut problem - complexity and algorithms
• Using shortcut edges to maximize the number of triangles in graphs

Cited in

(10)

• Compressive sensing of high betweenness centrality nodes in networks
• On the fixed-parameter tractability of the maximum connectivity improvement problem
• Optimizing node infiltrations in complex networks by a local search based heuristic
• A Faster Algorithm to Update Betweenness Centrality after Node Alteration
• Maximum betweenness centrality: approximability and tractable cases
• Exact and approximate algorithms for computing betweenness centrality in directed graphs
• The parameterized complexity of centrality improvement in networks
• scientific article; zbMATH DE number 7708854 (Why is no real title available?)
• Hardness of bounding influence via graph modification
• Adversarial analysis of similarity-based sign prediction

This page was built for publication: Improving the betweenness centrality of a node by adding links

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