Influence Maximization with $\varepsilon$-Almost Submodular Threshold Functions
Authors: Qiang Li, Wei Chen, Institute of Computing Xiaoming Sun, Institute of Computing Jialin Zhang
NeurIPS 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Finally, we conduct experiments on a number of real-world datasets, and the results demonstrate that our approximation algorithms outperform other baseline algorithms. |
| Researcher Affiliation | Collaboration | CAS Key Lab of Network Data Science and Technology, Institute of Computing Technology, Chinese Academy of Sciences University of Chinese Academy of Sciences Microsoft Research |
| Pseudocode | Yes | Algorithm 1 Galg-L algorithm for Influence Maximization Input: G = (V, E), A, {fv}, {f v}, k Output: Seed set S 1: set S = 2: replace each nodes v s threshold function fv with f v 3: run algorithm A on G with {f v} and obtain S 4: return S |
| Open Source Code | No | The paper states, “All algorithms tested in this paper are written in C++ and compiled with g++ 4.8.4. Some algorithms are implemented with multi-thread to decrease the running time.” However, it does not provide any link or explicit statement about making the source code publicly available. |
| Open Datasets | No | The paper mentions “The first network is Net HEPT, an academic collaboration network extracted from “High Energy Physics Theory” section of ar Xiv (http://www.ar Xiv.org) used by many works [7, 14, 15, 19, 20]. The second one is Flixster... The last one is the DBLP dataset...” While these are well-known datasets, the paper does not provide direct download links, DOIs, or specific dataset repository information for them, other than a general arXiv link for Net HEPT. |
| Dataset Splits | No | The paper does not provide specific information regarding the dataset splits (e.g., percentages or counts) for training, validation, or testing. It mentions “train”, “validation”, and “test” as categories in the output schema definition for the prompt, but no such details are provided within the paper’s content itself. |
| Hardware Specification | Yes | Our experiments run on a machine with two 2.4GHz Intel(R) Xeon(R) E5-2620 CPUs, 4 processors (24 cores), 128GB memory and 64bit Ubuntu 14.04.1. |
| Software Dependencies | Yes | All algorithms tested in this paper are written in C++ and compiled with g++ 4.8.4. |
| Experiment Setup | Yes | We adapt general threshold model in this paper. Our Galg-U,Galg-L are designed on submodular upper and lower bounds, respectively. Since directly applying greedy scheme on graphs with submodular threshold function is time-consuming, we assign the submodular threshold function and submodular upper bound of ε-AS function as linear function here: fv(S) = |S|/d(v), where d(v) is the in-degree of v. This makes the corresponding model an instance of the linearthreshold model, and thus the greedy algorithm can be accelerated with Reverse Reachable Set (RRset) technique [17]. We construct two different ε-almost submodular threshold functions in this paper: (1) a power function β with β satisfying 1 d(v) β = 1 d(v)(1 ε); (2) fv(S) = |S| d(v)(1 ε) for |S| 2 and |S|/d(v) otherwise. |