Found Graph Data and Planted Vertex Covers
Authors: Austin R. Benson, Jon Kleinberg
NeurIPS 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We pair our theoretical guarantees with experiments showing the efficacy of these methods on real-world networks with core-fringe structure. Our algorithms are fast, simple to implement, and out-perform several baselines based on core-periphery structure on various real-world datasets. |
| Researcher Affiliation | Academia | Austin R. Benson Cornell University arb@cs.cornell.edu Jon Kleinberg Cornell University kleinber@cs.cornell.edu |
| Pseudocode | Yes | Figure 3: Complete implementation of our union of minimal vertex covers (UMVC) algorithm in 26 lines of Julia code. |
| Open Source Code | Yes | Code on the left is available at https://gist.github.com/arbenson/27c6d9ef2871a31cbdbba33239ea60d0. Code and data accompanying the experiments in this paper are available at https://github.com/arbenson/FGDn PVC. |
| Open Datasets | Yes | We use 5 datasets: (1) email-Enron [35]; (2) email-W3C [14, 50, 61]; (3) email-Eu [42, 62]; (4) call-Reality and (5) text-Reality [22] come from phone calls and text messages involving a set of students and faculty at MIT participating in the reality mining project. |
| Dataset Splits | Yes | We divide the temporal edges of each dataset into 10-day increments and construct an undirected, unweighted, simple graph for the first 10r days of activity, r = 1, 2, . . . , T/10 , where T is the number of days spanned by the dataset. |
| Hardware Specification | No | No specific hardware details (e.g., exact GPU/CPU models, processor types with speeds, memory amounts, or detailed computer specifications) are provided for running experiments. |
| Software Dependencies | No | The paper mentions 'implemented in Julia', 'computed with the Light Graphs.jl Julia package', 'Python s Network X', and 'C++' but does not provide specific version numbers for these software components or libraries. |
| Experiment Setup | Yes | The nodes in this union are ordered by degree first and the nodes not appearing in any minimal cover are ordered by degree after. The minimal covers are constructed by first finding a 2-approximate solution to the minimum vertex cover problem using Algorithm 1 (which takes linear time in the size of the data) and then pruning the resulting cover to be minimal. We randomly order the edges for processing in order to capture different minimal covers (we use 300 covers in our experiments). |