Efficient Algorithms for Spanning Tree Centrality
Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 3733-3738.
Abstract
In a connected graph, spanning tree centralities of a vertex and an edge measure how crucial they are for the graph to be connected. In this paper, we propose efficient algorithms for estimating spanning tree centralities with theoretical guarantees on their accuracy. We experimentally demonstrate that our methods are orders of magnitude faster than previous methods. Then, we propose a novel centrality notion of a vertex, called aggregated spanning tree centrality, which also considers the number of connected components obtained by removing the vertex. We also give an efficient algorithm for estimating aggregated spanning tree centrality. Finally, we experimentally show that those spanning tree centralities are useful to identify vulnerable edges and vertices in infrastructure networks.
@inproceedings{ijcai2016p525,
title = {Efficient Algorithms for Spanning Tree Centrality},
author = {Hayashi, Takanori and Akiba, Takuya and Yoshida, Yuichi},
booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
Artificial Intelligence, {IJCAI-16}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Subbarao Kambhampati},
pages = {3733--3738},
year = {2016},
month = {7},
url = {https://ijcai.org/proceedings/2016/525},
}
TY - CPAPER TI - Efficient Algorithms for Spanning Tree Centrality AU - Hayashi, Takanori AU - Akiba, Takuya AU - Yoshida, Yuichi T2 - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2016 SP - 3733 EP - 3738 UR - https://ijcai.org/proceedings/2016/525 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
