Better Bounds on the Adaptivity Gap of Influence Maximization under Full-adoption Feedback
Authors: Gianlorenzo D'Angelo, Debashmita Poddar, Cosimo Vinci12069-12077
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main result is the first sub-linear upper bound that holds for any graph. Specifically, we show that the adaptivity gap is upper-bounded by 3 n+ 1, where n is the number of nodes in the graph. Moreover we improve over the known upper bound for in-arborescences from 2e/(e − 1) ≈ 3.16 to 2e2/(e2 − 1) ≈ 2.31. Finally, we study α-bounded graphs, a class of undirected graphs in which the sum of node degrees higher than two is at most α, and show that the adaptivity gap is upper-bounded by α+ O(1). Moreover, we show that in 0-bounded graphs, i.e. undirected graphs in which each connected component is a path or a cycle, the adaptivity gap is at most 3e3/(e3 − 1) ≈ 3.16. To prove our bounds, we introduce new techniques to relate adaptive policies with non-adaptive ones that might be of their own interest. |
| Researcher Affiliation | Academia | Gianlorenzo D Angelo, Debashmita Poddar, and Cosimo Vinci Gran Sasso Science Institute, L Aquila, Italy {gianlorenzo.dangelo, debashmita.poddar, cosimo.vinci}@gssi.it |
| Pseudocode | Yes | Algorithm 1 Adaptive algorithm Require: an influence graph 퐺and an adaptive policy 휋; Ensure: a partial realisation; 1: let 퐿be the live-edge graph; 2: let 휓:= (i.e., 휓is the empty partial realisation); 3: while 휋(휓) 푆푇푂푃do 4: 푣:= 휋(휓); 5: 휓:= 휓 {(푣, 푅({푣}, 퐿))}; 6: end while 7: return 휓휋,퐿:= 휓; |
| Open Source Code | No | The paper does not provide any concrete access information (specific repository link, explicit code release statement, or code in supplementary materials) for the methodology's source code. |
| Open Datasets | No | This paper is theoretical and focuses on mathematical proofs and bounds for influence maximization. It does not describe experiments with datasets, thus no dataset is mentioned as publicly available or open. |
| Dataset Splits | No | This paper is theoretical and focuses on mathematical proofs and bounds. It does not describe empirical experiments with datasets, and therefore no training/validation/test dataset splits are provided. |
| Hardware Specification | No | This is a theoretical paper that focuses on mathematical proofs and algorithms. It does not describe any computational experiments that would require specific hardware specifications. |
| Software Dependencies | No | This is a theoretical paper that focuses on mathematical proofs and algorithms. It does not describe any computational experiments that would involve specific software dependencies with version numbers. |
| Experiment Setup | No | This is a theoretical paper that focuses on mathematical proofs and algorithms. It does not describe any empirical experiments that would require an experimental setup with hyperparameters or training settings. |