Efficient algorithms for updating betweenness centrality in fully dynamic graphs

DOI10.1016/J.INS.2015.07.053MaRDI QIDQ1750422zbMATH OpenOpenAlexFDO

Authors Min-Joong Lee, Chin-Wan Chung, 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

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

Recommendations

• A faster algorithm to update betweenness centrality after node alteration
• A Faster Algorithm to Update Betweenness Centrality after Node Alteration
• Fully-dynamic approximation of betweenness centrality
• Approximating Betweenness Centrality in Fully Dynamic Networks
• scientific article; zbMATH DE number 6917138
• Computing Top-k Closeness Centrality in Fully-dynamic Graphs
• Community based node betweenness centrality updating algorithms in dynamic networks
• scientific article; zbMATH DE number 3900809
• A faster algorithm for betweenness centrality*
• Exact and approximate algorithms for computing betweenness centrality in directed graphs

Cites work

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

Cited in

(18)

• Computing Top-k Closeness Centrality in Fully-dynamic Graphs
• Betweenness centrality -- incremental and faster
• A faster algorithm to update betweenness centrality after node alteration
• On the connectivity and the diameter of betweenness-uniform graphs
• Scalable Katz ranking computation in large static and dynamic graphs
• Community based node betweenness centrality updating algorithms in dynamic networks
• On the connectivity and the diameter of betweenness-uniform graphs
• Improving the betweenness centrality of a node by adding links
• Efficient approaches for attaining epidemic-free networks with minimum edge removal set
• Compressive sensing of high betweenness centrality nodes in networks
• Local community detection in dynamic graphs using personalized centrality
• Optimizing node infiltrations in complex networks by a local search based heuristic
• A Faster Algorithm to Update Betweenness Centrality after Node Alteration
• Approximating Betweenness Centrality in Fully Dynamic Networks
• Scalable Katz Ranking Computation in Large Static and Dynamic Graphs
• Fully dynamic betweenness centrality
• Boosting the exploration of huge dynamic graphs
• scientific article; zbMATH DE number 6917138 (Why is no real title available?)

Describes a project that uses

Uses Software

• Algorithm 447

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

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