Computing and maximizing influence in linear threshold and triggering models
Authors: Justin T. Khim, Varun Jog, Po-Ling Loh
NeurIPS 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In this section, we report the results of various simulations. In the first set of simulations, we generated an Erdös-Renyi graph with 900 vertices and edge probability 2 n; a preferential attachment graph with 900 vertices, 10 initial vertices, and 3 edges for each added vertex; and a 30 30 grid. We generated 33 instances of edge probabilities for each graph, as follows: For each instance and each vertex i, we chose γ(i) uniformly in [γmin, 0.8], where γmin ranged from 0.0075 to 0.75 in increments of 0.0075. The probability that the incoming edge was chosen was 1 γ d(i) , where d(i) is the degree of i. An initial infection set A of size 10 was chosen at random, and 50 simulations of the infection process were run to estimate the true influence. The upper and lower bounds and value of I(A) computed via simulations are shown in Figure 1. |
| Researcher Affiliation | Academia | Justin Khim Department of Statistics The Wharton School University of Pennsylvania Philadelphia, PA 19104 jkhim@wharton.upenn.edu Varun Jog Electrical & Computer Engineering Department University of Wisconsin Madison Madison, WI 53706 vjog@wisc.edu Po-Ling Loh Electrical & Computer Engineering Department University of Wisconsin Madison Madison, WI 53706 loh@ece.wisc.edu |
| Pseudocode | No | The paper describes algorithms and derivations in prose and mathematical notation but does not include any clearly labeled "Pseudocode" or "Algorithm" blocks or structured algorithmic steps. |
| Open Source Code | No | The paper does not contain any statement about releasing source code for the methodology or provide a direct link to a code repository. |
| Open Datasets | No | The paper describes the generation of graph instances for simulations, but it does not provide concrete access information (e.g., specific link, DOI, repository name, or formal citation) for these generated instances or any other publicly available datasets used for training. |
| Dataset Splits | No | The paper describes simulation setups and estimations of influence, but it does not specify any distinct validation dataset splits or procedures used for model tuning or selection in the context of machine learning. |
| Hardware Specification | No | The paper describes the simulation setup and graph generation but does not provide specific details about the hardware (e.g., CPU/GPU models, memory) used to run the experiments. |
| Software Dependencies | No | The paper describes the models and theoretical bounds but does not list any specific software dependencies with version numbers (e.g., programming languages, libraries, or solvers) used for implementing or running the experiments. |
| Experiment Setup | Yes | In the first set of simulations, we generated an Erdös-Renyi graph with 900 vertices and edge probability 2 n; a preferential attachment graph with 900 vertices, 10 initial vertices, and 3 edges for each added vertex; and a 30 30 grid. We generated 33 instances of edge probabilities for each graph, as follows: For each instance and each vertex i, we chose γ(i) uniformly in [γmin, 0.8], where γmin ranged from 0.0075 to 0.75 in increments of 0.0075. The probability that the incoming edge was chosen was 1 γ d(i) , where d(i) is the degree of i. An initial infection set A of size 10 was chosen at random, and 50 simulations of the infection process were run to estimate the true influence. For the second set of simulations, we generated 10 of each of the following graphs: an Erdös-Renyi graph with 100 vertices and edge probability 2 n; a preferential attachment graph with 100 vertices, 10 initial vertices, and 3 additional edges for each added vertex; and a grid graph with 100 vertices. For each of the 10 realizations, we also picked a value of γ(i) for each vertex i uniformly in [0.075, 0.8]. The corresponding edge probabilities were assigned as before. We then selected sets A of size 10 using greedy algorithms to maximize LB1, LB2, and UB, as well as the estimated influence based on 50 simulated infections. Finally, we used 200 simulations to approximate the actual influence of each resulting set. |