Network Inference and Influence Maximization from Samples
Authors: Wei Chen, Xiaoming Sun, Jialin Zhang, Zhijie Zhang
ICML 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we consider the more realistic sampling setting where the network is unknown and we only have a set of passively observed cascades that record the set of activated nodes at each diffusion step. We study the task of influence maximization from these cascade samples (IMS), and present constant approximation algorithms for this task under mild conditions on the seed set distribution. To achieve the optimization goal, we also provide a novel solution to the network inference problem, that is, learning diffusion parameters and the network structure from the cascade data. Comparing with prior solutions, our network inference algorithm requires weaker assumptions and does not rely on maximum-likelihood estimation and convex programming. Our IMS algorithms enhance the learning-and-then-optimization approach by allowing a constant approximation ratio even when the diffusion parameters are hard to learn, and we do not need any assumption related to the network structure or diffusion parameters. |
| Researcher Affiliation | Collaboration | 1Microsoft Research Asia, Beijing, China. 2Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China. 3School of Computer Science and Technology, University of Chinese Academy of Sciences, Beijing, China. |
| Pseudocode | Yes | Algorithm 1 Estimate Edge Probabilities; Algorithm 2 Recover Network Structure; Algorithm 3 Influence Maximization from Samples under Assumption 1; Algorithm 4 Influence Maximization from Samples under Assumption 2; Algorithm 5 Influence Maximization from Samples under Assumption 2 with c = ε |
| Open Source Code | No | The paper does not provide any statement or link indicating that the source code for the described methodology is publicly available. |
| Open Datasets | No | The paper is theoretical and discusses "samples" abstractly, defining them as "a set of t independent cascades". It does not use or provide access information for any specific public dataset. |
| Dataset Splits | No | The paper is theoretical and does not conduct empirical evaluations on specific datasets, therefore, it does not provide dataset split information. |
| Hardware Specification | No | The paper is theoretical and does not report on empirical experiments, therefore no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and does not report on empirical experiments, therefore no software dependencies with version numbers are provided. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and proofs, not empirical experiments. Therefore, no experimental setup details such as hyperparameters or training configurations are provided. |