Generalized Nonbacktracking Bounds on the Influence
Authors: Emmanuel Abbe, Sanjeev Kulkarni, Eun Jee Lee
JMLR 2020 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In this section, we evaluate NB-UB and NB-LB in independent cascade models on a variety of classical synthetic networks. Network Generation. We consider 4 classical random graph models with the parameters shown as follows: Erdos Renyi random graphs with ER(n = 1000, p = 0.003), scale-free networks SF(n = 1000, α = 2.5), random regular graphs Reg(n = 1000, d = 3), and random tree graphs with power-law degree distributions T(n = 1000, α = 3). For each graph model, we generate 100 networks IC(G, p A) and a seed as follows. The bidirected graph G is defined on the largest connected component of a graph drawn from the graph model, the seed node s is a randomly selected vertex, and A is the adjacency matrix of G. The corresponding IC model has the same transmission probability p for every edge. Evaluation of Bounds. For each generated network, we compute the following quantities for each p {0.1, 0.2, . . . , 0.9}. σmc: the estimation of the influence with 106 Monte Carlo simulations. σ+: the upper bound obtained by NB-UB. σ+ spec: the spectral upper bound by (Lemonnier et al., 2014). σ : the lower bound obtained by NB-LB. σ prob: the probabilistic lower bound obtained by 10 Monte Carlo simulations. In Figure 6, we compare the average relative gap of the bounds for every network model and for each transmission probability, where the true value is assumed to be σmc. |
| Researcher Affiliation | Academia | Emmanuel Abbe EMAIL Program in Applied and Computational Mathematics and Department of Electrical Engineering Princeton University Princeton, NJ 08540, USA Sanjeev Kulkarni EMAIL Department of Electrical Engineering Princeton University Princeton, NJ 08540, USA Eun Jee Lee EMAIL Program in Applied and Computational Mathematics Princeton University Princeton, NJ 08540, USA |
| Pseudocode | Yes | Algorithm 1 Nonbacktracking Upper Bound (NB-UB) ... Algorithm 2 Tunable nonbacktracking upper bound (t NB-UB) ... Algorithm 3 r-nonbacktracking upper bound (r NB-UB) ... Algorithm 4 Nonbacktracking Lower Bound (NB-LB) ... Algorithm 5 Tunable nonbacktracking lower bound (t NB-LB) |
| Open Source Code | No | The paper does not contain any explicit statement about releasing source code or a link to a code repository. The license information provided is for the paper itself, not for the underlying code. |
| Open Datasets | No | The paper describes generating synthetic networks based on classical random graph models (Erdos Renyi, scale-free, random regular, random tree graphs) with specific parameters. It states, "For each graph model, we generate 100 networks IC(G, p A)." This indicates that data is generated for the experiments rather than using a pre-existing, publicly available dataset with a direct link or citation. |
| Dataset Splits | No | The paper generates synthetic networks and uses Monte Carlo simulations for influence estimation. There is no mention of training/test/validation splits, as the experimental setup does not involve traditional supervised learning on a fixed dataset. |
| Hardware Specification | No | The paper does not provide any specific details about the hardware used to run the experiments, such as CPU or GPU models, or memory specifications. It focuses on computational complexity but not the physical machines used. |
| Software Dependencies | No | The paper mentions Monte Carlo simulations and message passing algorithms but does not specify any particular software libraries, frameworks, or their version numbers (e.g., Python, PyTorch, TensorFlow, specific solvers) that were used for implementation. |
| Experiment Setup | Yes | Network Generation. We consider 4 classical random graph models with the parameters shown as follows: Erdos Renyi random graphs with ER(n = 1000, p = 0.003), scale-free networks SF(n = 1000, α = 2.5), random regular graphs Reg(n = 1000, d = 3), and random tree graphs with power-law degree distributions T(n = 1000, α = 3). For each graph model, we generate 100 networks IC(G, p A) and a seed as follows. ... For each generated network, we compute the following quantities for each p {0.1, 0.2, . . . , 0.9}. σmc: the estimation of the influence with 106 Monte Carlo simulations. ... The MC upper bounds are computed with the various sample sizes N {5, 10, 30, 300, 3000}. |