Biharmonic Distance Related Centrality for Edges in Weighted Networks
Authors: Yuhao Yi, Liren Shan, Huan Li, Zhongzhi Zhang
IJCAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In this section, we experimentally evaluate the efficiency and accuracy of our approximation algorithm. We evaluate the algorithm on a large set of real-world networks from different domains. The data of these networks are taken from the Koblenz Network Collection [Kunegis, 2013]. We run our experiments on the largest connected components (LCC) of these networks, related information of which is shown in Table 2. |
| Researcher Affiliation | Academia | 1Shanghai Key Laboratory of Intelligent Information Processing, Fudan University, China 2School of Computer Science, Fudan University, China {yhyi15, 13307130150, huanli16, zhangzz}@fudan.edu.cn |
| Pseudocode | Yes | Algorithm 1: Appx BDRC(G, ϵ) Input : G: a connected undirected graph. ϵ: approximation parameter of edge centrality Output : ˆC = {e, ˆc(e)|e E}: ˆc is an approximation of C(e), the BDRC of e. 1 L = Laplacian of G, ˆc(e)=0 for all e E 2 k = 24 log n/ϵ2 3 for i = 1 to k do 4 Construct a 1/ k random vector q i of size n 1 5 z i = Lapl Solve(L, q i, δ) where δ is given by (8) 6 for each e E do 7 ˆc(e) = ˆc(e) + nw2 e| z i,u z i,v|2 8 return ˆC = {e, ˆc(e)|e E} |
| Open Source Code | No | The paper mentions that a component it uses, Lapl Solve, is implemented in Julia and accessible online ("Julia language implementation of which is accessible on the website2."), but it does not state that the authors' own code for the described methodology is open-source or provide a link to it. |
| Open Datasets | Yes | The data of these networks are taken from the Koblenz Network Collection [Kunegis, 2013]. All data can be found at http://wwwpersonal.umich.edu/ mejn/netdata/ |
| Dataset Splits | No | The paper evaluates an approximation algorithm for a graph centrality measure by comparing its approximate results to exact results on real-world networks. It does not involve training a model or using training/validation/test splits as typically understood in supervised machine learning contexts, so the concept of a validation set is not applicable here. |
| Hardware Specification | Yes | We run all the experiments on a Linux box with an Intel i7-7700K @ 4.2-GHz (4 Cores) and with 32GB memory. |
| Software Dependencies | Yes | We implement the algorithm Appx BDRC in Julia v0.6.0, where the Lapl Solve is from [Kyng and Sachdeva, 2016], the Julia language implementation of which is accessible on the website2. |
| Experiment Setup | Yes | Algorithm 1: Appx BDRC(G, ϵ) Input : G: a connected undirected graph. ϵ: approximation parameter of edge centrality... k = 24 log n/ϵ2... z i = Lapl Solve(L, q i, δ) where δ is given by (8). |