Seeding with Costly Network Information
Provide a draft "referee" report on the paper
AI: Draft referee report: The paper presents a novel approximation algorithm for k-influence maximization problem that achieves guarantees that match hardness lower bounds. The authors also propose a probing procedure to sequentially reveal random neighborhoods of the nodes that results in a snowball-like sampling of the network edges. The paper provides several theorems and detailed comparisons with related works, and presents formal proofs in appendices. Overall, the paper is well-written and technically sound. However, the referee notes that some parts of the paper require further clarification. Specifically, the referee notes that it is not immediately clear how the results might generalize to other input graphs beyond the hard input graph constructed using the specific random process described in the paper. The referee suggests that the authors could provide more insight into how the hard input graph relates to other graph models and why the specific random process used is interesting or relevant. Additionally, the referee suggests that the authors could provide more details on the evaluation of the algorithm, such as the specific datasets used and how they were obtained. The referee also notes that some parts of the paper lack details or provide incomplete information, and suggests that the authors make an effort to address those issues. In summary, the paper presents an interesting algorithm and analysis for k-influence maximization problem but requires further clarification and improvement in some areas.
The article addresses a fundamental problem in network science: how to target interventions in a social network to maximize the spread of, e.g., adoption of a product. The computational and algorithmic foundations of this problem are well studied when the network structure is known, but it often is not and is expensive or impractical to measure. Here we analyze the case when the network structure is not available but can be acquired through costly actions.