Research map / Learning theory and algorithms / Sample complexity
Bounds and Complexity Results for Learning Coalition-Based Interaction Functions in Networked Social Systems
Abhijin Adiga, Chris Kuhlman, Madhav Marathe, S. Ravi, Daniel Rosenkranz, Richard Stearns, Anil Vullikanti
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| increase number of blocks b from 2 to 50 (ablation) | active query algorithm · mined and synthetic networks | number of queries | Hurt |
| scale-free/skewed-degree networks versus random regular networks | active query algorithm · normalized #queries vs Theorem 3 bound | normalized number of queries | Improved |
| increase edge density / network size | active query algorithm · NRV vs CoAstro | normalized number of queries | No clear effect |
| b exceeds maximum degree (ablation) | active query algorithm · mined and synthetic networks | number of queries | No clear effect |
| increase number of inputs q from 10 to 20 (ablation) | ILP PAC algorithm · uniform distribution, p = 0.5 | Rand index vs examples | Hurt |
| increase number of true blocks (ablation) | ILP PAC algorithm · uniform distribution | examples needed | Improved |
| increase p from 0.25/0.5 to 0.75 (ablation) | ILP PAC algorithm · Rand index | Rand index | Mixed |
| increase number of examples (ablation) | ILP PAC algorithm · Rand index | Rand index | Improved |
| increase number of examples (ablation) | ILP PAC algorithm · running time | running time | Hurt |
Closest papers by meaning
- Learning the Behavior of a Dynamical System Via a “20 Questions” Approach (AAAI 2018 · similarity 0.91)
- Learning the Topology and Behavior of Discrete Dynamical Systems (AAAI 2024 · similarity 0.86)
- Efficient PAC Learnability of Dynamical Systems Over Multilayer Networks (ICML 2024 · similarity 0.86)
- Sample Complexity of Linear Regression Models for Opinion Formation in Networks (AAAI 2025 · similarity 0.84)
- Deviate or Not: Learning Coalition Structures with Multiple-bit Observations in Games (AAAI 2025 · similarity 0.84)
- Learning Distributions from Multiple Data Providers (NeurIPS 2026 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
