Efficient Algorithms for Spanning Tree Centrality
Authors: Takanori Hayashi, Takuya Akiba, Yuichi Yoshida
IJCAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | 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. |
| Researcher Affiliation | Collaboration | Takanori Hayashi, , Takuya Akiba, ,#, Yuichi Yoshida , The University of Tokyo National Institute of Informatics #CIT STAIR Lab JST, ERATO, Kawarabayashi Large Graph Project JST, PRESTO Preferred Infrastructure, Inc. |
| Pseudocode | Yes | Algorithm 1 Wilson s algorithm 1: procedure WILSON(G, r) 2: T the tree consisting of a single vertex r. 3: Let v1, . . . , vn 1 be an arbitrary ordering of V \{r}. 4: for i = 1 to n 1 do 5: Let P be a random walk from vi to T. 6: Add the loop erasure LE(P) to T. 7: return T. Algorithm 2 Spanning Tree Centrality for Edges 1: procedure ST-EDGE(G, r, , δ) 2: q dlog(2m/δ)/(2 2)e. 3: for i = 1 to q do 4: Ti WILSON(G, r). 5: for each e 2 E do 6: est(e) 1 i2[q][e 2 Ti]. 7: return {est(e)}e2E. Algorithm 3 Spanning Tree Centrality for Vertices 1: procedure ST-VERTEX(G, r, , δ) 2: q dlog(2n/δ)/(2 2)e. 3: for i = 1 to q do 4: Ti WILSON(G, r). 5: for each u 2 V do 6: est(u) 1 i2[q][d Ti(u) 2]. 7: return {est(u)}u2V . Algorithm 4 Aggregated Spanning Tree Centrality 1: procedure AST-VERTEX(G, r, , δ) 2: 0 e ( / log(n/δ)). (e ( ) hides the log factor.) 3: q e (log(n/δ)/ 02). 4: for i = 1 to q do 5: Ti WILSON(G, r). 6: for each u 2 V do 7: f ast(u) 1 i2[q] d Ti(u). 8: return {f ast(u)}u2V . |
| Open Source Code | No | The paper states: "The implementation of the algorithm proposed by [Mavroforakis et al., 2015], which we refer to the MGKT algorithm, was obtained from authors website1." and provides footnote 1 with a URL. This refers to the code for a baseline method, not the authors' own implementation of their proposed methods. No statement about releasing their own code was found. |
| Open Datasets | Yes | All datasets used in our experiments can be downloaded from Stanford Network Analysis Project [Leskovec and Krevl, 2014]. http://snap.stanford.edu/data |
| Dataset Splits | No | The paper does not provide specific details on training, validation, and test dataset splits (e.g., percentages, sample counts, or explicit instructions for creating splits). |
| Hardware Specification | Yes | All experiments were conducted with a single thread on a Linux server with Intel Xeon X5675 3.07GHz CPU and 288GB Memory. |
| Software Dependencies | No | The paper states: "All the proposed methods were implemented in C++11 and compiled with gcc 4.8.3 with -O3 option." While compiler and language versions are given, no specific software libraries or frameworks with version numbers, which would be considered key dependencies for reproducibility, are mentioned. |
| Experiment Setup | Yes | Unless stated otherwise, we used biconnected-component decomposition and Distance strategy for vertex ordering. The choice of the root r and the vertex ordering v1, . . . , vn 1 much affect the practical performance. We consider the following strategies for the vertex ordering strategies used in Wilson s algorithm: Random, Degree, Distance, and Reverse. In the first three strategies, we choose a vertex with the highest degree as the root. Other vertices are randomly shuffled, sorted in decreasing order of degrees, and sorted in increasing order of distances from the root in Random, Degree, and Distance, respectively. In Reverse, a vertex with the lowest degree is chosen as the root and other vertices are sorted in increasing order of degrees. For an error parameter , our method samples dlog(2m/δ)/(2 2)e spanning trees and guarantees est(e) = st(e) for every edge with probability at least 1 δ and the MGKT algorithm guarantees (1 )2st(e) est(e) (1+ )2st(e) for every edge with probability at least 1 δ. We chose the failure probability δ = 1/n. We sampled 1,000 spanning trees in total. |