Efficient algorithms for updating betweenness centrality in fully dynamic graphs

DOI10.1016/j.ins.2015.07.053zbMath1390.05226OpenAlexW1439932879MaRDI QIDQ1750422

Chin-Wan Chung, Min-Joong Lee, Sung Hee Choi

Publication date: 22 May 2018

Published in: Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ins.2015.07.053

zbMATH Keywords

community detectionbiconnected componentbetweenness centralitydynamic graphupdate algorithm

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

On the connectivity and the diameter of betweenness-uniform graphs ⋮ Compressive sensing of high betweenness centrality nodes in networks ⋮ Improving the Betweenness Centrality of a Node by Adding Links ⋮ Scalable Katz Ranking Computation in Large Static and Dynamic Graphs ⋮ Efficient approaches for attaining epidemic-free networks with minimum edge removal set ⋮ Boosting the Exploration of Huge Dynamic Graphs ⋮ On the connectivity and the diameter of betweenness-uniform graphs ⋮ Optimizing node infiltrations in complex networks by a local search based heuristic ⋮ Scalable Katz Ranking Computation in Large Static and Dynamic Graphs

Uses Software

• Algorithm 447

Cites Work

• Polygonal approximation of digital planar curves through vertex betweenness
• A faster algorithm for betweenness centrality*
• A Faster Algorithm to Update Betweenness Centrality after Node Alteration
• Experimental analysis of dynamic all pairs shortest path algorithms
• The university of Florida sparse matrix collection
• Routing betweenness centrality
• Worst-case update times for fully-dynamic all-pairs shortest paths
• Fibonacci heaps and their uses in improved network optimization algorithms
• Better Approximation of Betweenness Centrality
• A new approach to dynamic all pairs shortest paths
• Approximating Betweenness Centrality
• CONGESTION AND CENTRALITY IN TRAFFIC FLOW ON COMPLEX NETWORKS
• Network Analysis
• CENTRALITY ESTIMATION IN LARGE NETWORKS

This page was built for publication: Efficient algorithms for updating betweenness centrality in fully dynamic graphs