Seeding with Costly Network Information
summary
Problem: maximize cascade size with limited, costly network measurements. Proposes spread queries (seed a node, observe its entire cascade) and edge queries (reveal random neighbors like RDS), run a greedy optimizer on sampled subgraphs, and prove polynomial-time worst‑case approximations that incur an unavoidable order-n loss in extreme graphs. Empirically, under 30 spread queries recovers near‑full‑graph greedy for k=2 on a Facebook100 network. Gives a cost tradeoff example (revenue 0.01 per adoption, query cost 0.1, seed cost 1) showing interior optima between querying and adding seeds.
AI-written summary · about
chapters (13)
- 0:00Intro
- 0:55Influence maximization
- 3:38Seeding and measuring the network
- 5:19One-hop seeding
- 16:00Two query frameworks
- 24:40Approximation guarantee: Spreading queries
- 25:27Hardness: spreading queries
- 33:59Approximation guarantees: Edge queries
- 34:56Hardness: Edge Queries
- 40:35University of Pennsylvania social network
- 41:10Trading off seed nodes for more queries
- 42:58Optimum number of queries
- 44:15Conclusions
related talks
27mSampling Algorithms to Count Frequent Patterns in Graphs
16mUsing Network Analysis to Detect Kickback Schemes Among Medical Providers
01h 03mSimons Institute Live Stream
43mInformation-Theoretic Bounds and Phase Transitions in Community Detection and High-Dimensional Clust
55mDistribution-Free Models of Social and Information Networks
10mNetwork Structure and Privacy: The Re-Identification Risk in Graph Data
44mScalable Algorithmic Primitives for Data Science
32mAdventures with Randomized Algebra for Extreme-Scale Signal Processing