Coverage Centrality Maximization in Undirected Networks
Authors: Gianlorenzo D’Angelo, Martin Olsen, Lorenzo Severini501-508
AAAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We experimentally compare the solutions provided by our approximation algorithm with optimal solutions computed by means of an exact IP formulation. We show that our algorithm produces solutions that are very close to the optimum.In this section, we study the algorithms GREEDY1 and GREEDY2 from an experimental point of view. First, we compare the solutions of the greedy algorithms with optimal solutions computed by using an integer program formulation of MCP in order to assess the real performance in terms of solution quality (see (D Angelo, Olsen, and Severini 2018) for the detailed implementation of the IP formulation). Then, we focus on the MCI problem and compare GREEDY1 and GREEDY2 with the natural algorithm that adds k random edges. |
| Researcher Affiliation | Academia | Gianlorenzo D Angelo Gran Sasso Science Institute L Aquila, Italy gianlorenzo.dangelo@gssi.itMartin Olsen Department of Business Development and Technology Aarhus University, Denmark martino@btech.au.dkLorenzo Severini ISI Foundation Turin, Italy lorenzo.severini@isi.it |
| Pseudocode | Yes | Algorithm 1: Procedure GREEDY1, Algorithm 2: Procedure GREEDY2 |
| Open Source Code | No | The paper does not provide an explicit statement or link for open-source code for the methodology described. |
| Open Datasets | Yes | We execute our experiments on two popular model networks, the Barabasi-Albert (BA) network (Barabasi and Albert 1999) and the Configuration Model (CM) network (Bender and Canfield 1978; Molloy and Reed 1995), and on real-world networks extracted from human activities3. The sizes of the networks are reported in Table 2. 3http://konect.uni-koblenz.de/ |
| Dataset Splits | No | The paper does not provide specific details on dataset splits (e.g., train/validation/test percentages or counts) needed to reproduce the data partitioning. The experimental setup focuses on comparing algorithm performance against optimal solutions and a baseline on entire networks, rather than using explicit dataset splits for model training and evaluation. |
| Hardware Specification | Yes | All our experiments have been performed on a computer equipped with an Intel Xeon E5-2643 CPU clocked at 3.4GHz and 128GB of main memory, and our programs have been implemented in C++. |
| Software Dependencies | No | The paper states that programs were "implemented in C++" but does not provide specific version numbers for the C++ compiler or any other software dependencies, libraries, or solvers used. |
| Experiment Setup | Yes | For each network, we randomly choose 10 target nodes and, for each target node v, we add k nonexistent edges incident to v for k = 1, 2, . . . , 10. Then, we plot the average coverage centrality of the 10 target nodes for each k.GREEDY1 (with t = 2, 3) |