Random-Radius Ball Method for Estimating Closeness Centrality
Authors: Wataru Inariba, Takuya Akiba, Yuichi Yoshida
AAAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | The effectiveness of the RRB method over existing algorithms is demonstrated through experiments on real-world networks. |
| Researcher Affiliation | Collaboration | Wataru Inariba The University of Tokyo and JST, ERATO, Kawarabayashi Large Graph Project oinari17@gmail.com Takuya Akiba Preferred Networks, Inc. akiba@preferred.jp Yuichi Yoshida National Institute of Informatics and Preferred Infrastructure, Inc. yyoshida@nii.ac.jp |
| Pseudocode | Yes | Algorithm 1: Random-radius ball (RRB) method. Algorithm 2: Random-radius ball (RRB) method with bootstrapping. |
| Open Source Code | No | The paper does not provide an explicit statement or link for the open-sourcing of the RRB method code. It mentions using a third-party framework: "For HB, we used the Web Graph framework, which is the Java program provided by the authors (Boldi and Vigna 2004)." |
| Open Datasets | Yes | Networks. All of the networks were collected from the Stanford Large Network Dataset Collection (Leskovec and Krevl 2014) and Laboratory for Web Algorithms (Boldi and Vigna 2004; Boldi et al. 2011). |
| Dataset Splits | No | The paper does not explicitly state the training, validation, or test dataset splits. It mentions using various networks for experiments, but no details on how these were partitioned for evaluation. |
| Hardware Specification | Yes | All of the experiments were conducted on a machine with two Intel Xeon E5540 processors and 48 Gi B of main memory. |
| Software Dependencies | Yes | We implemented RRB, RRB-BS, and ADS in C++11 and compiled them with gcc 4.8.2. For HB, we used the Web Graph framework, which is the Java program provided by the authors (Boldi and Vigna 2004). |
| Experiment Setup | Yes | For RRB-BS, we set s = 3. For all of these methods, we can control the trade-off between the time complexity and accuracy by varying select parameters. Throughout all of the experiments, we estimated the harmonic centrality of the vertices, i.e., the distance-decay function α(x) was set to 1/x. To evaluate the (normalized) RMSE of an estimate, we ran an algorithm 100 times with different random seeds and then took the average. |