arxiv: 2605.11337 · v1 · submitted 2026-05-11 · 💻 cs.GT

Recognition: no theorem link

Optimal Interventions on the Linear Threshold Model in Large-Scale Networks

Fabio Fagnani, Giacomo Como, Leonardo Cianfanelli, Sebastiano Messina

Authors on Pith no claims yet

Pith reviewed 2026-05-13 01:31 UTC · model grok-4.3

classification 💻 cs.GT

keywords linear threshold modeloptimal interventionmean-field approximationlinear programminginfluence maximizationnetwork diffusionsocial networks

0 comments

The pith

A local mean-field approximation reformulates optimal threshold interventions on the linear threshold model as an infinite linear program that finite programs can approximate.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper addresses how a social planner can make the cheapest possible changes to agents' activation thresholds in a network so that a preset fraction of agents end up in a target state after a limited number of steps. Exact solutions are known to be NP-hard and demand complete knowledge of every connection, which is rarely available at scale. The authors use a local mean-field approximation that holds for large random networks to rewrite the design task as a linear program whose constraints are infinite in number. They then show that this program can be solved to good accuracy by ordinary linear programs that use only a finite collection of constraints. The resulting method works when the planner knows only statistical properties of the network and is tested on real-world examples against seeding and other influence algorithms.

Core claim

We build on a local mean-field approximation of the LTM that is known to hold true on large-scale random networks, and reformulate the optimal intervention problem as a linear program with an infinite set of constraints. We then show how to approximate the solutions of the latter problem by standard linear programs with finitely many constraints.

What carries the argument

The local mean-field approximation of the linear threshold model on large random networks, which converts the minimal-cost intervention task into a linear program whose constraints are indexed over all possible network realizations.

If this is right

Low-cost threshold modifications that meet the adoption target can be computed without knowing the exact network edges.
The finite linear programs remain tractable as network size grows because they depend only on degree distributions and other aggregate statistics.
The same framework directly yields comparisons with optimal seeding and with existing least-cost influence algorithms on real networks.
The method respects the finite-horizon constraint and the requirement that only a statistical description of the network is supplied to the planner.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same mean-field route may render other diffusion-control problems on large networks computationally tractable whenever analogous local approximations exist.
Planners could therefore design interventions using only publicly observable network statistics rather than private link data.
If the finite approximations can be recomputed periodically, the approach could support adaptive policies that respond to observed adoption rates.

Load-bearing premise

The local mean-field approximation of the linear threshold model holds with sufficient accuracy on large-scale random networks.

What would settle it

Generate a large random network, compute the finite linear-program solution for a chosen target fraction, apply the resulting threshold changes to the actual linear threshold model dynamics, and check whether the realized fraction of activated agents falls materially below the target.

Figures

Figures reproduced from arXiv: 2605.11337 by Fabio Fagnani, Giacomo Como, Leonardo Cianfanelli, Sebastiano Messina.

**Figure 2.** Figure 2: Evolution function for the fraction of links pointing [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

read the original abstract

We study an optimal intervention problem on the linear threshold model (LTM) in which a social planner aims to design minimal-cost interventions that modify the agents' thresholds, under the constraint that at least a predefined fraction of agents reaches a given state after a finite number of iterations. While this problem is known to be NP-hard and its exact solution requires full knowledge of the network structure, we focus on approximate solutions for large-scale networks and assume that the planner has only statistical knowledge of the network. In particular, we build on a local mean-field approximation of the LTM that is known to hold true on large-scale random networks, and reformulate the optimal intervention problem as a linear program with an infinite set of constraints. We then show how to approximate the solutions of the latter problem by standard linear programs with finitely many constraints. Finally, our approach is validated through numerical experiments on real-world networks and compared both with optimal seeding and state-of-the-art algorithms for the least-cost influence.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Scalable mean-field LP for LTM interventions, but real-network validation misses error bounds.

read the letter

The main point is that this paper gives a scalable LP approximation for choosing which thresholds to change in the linear threshold model on large networks, when you only know the degree distribution or similar stats rather than the full graph. They take the local mean-field equations that are known to work for LTM on big random networks, and recast the min-cost intervention problem as a linear program with infinitely many constraints. They then show how to get good finite approximations to that LP. The numerical tests on real networks compare favorably to seeding and other algorithms. This is new in the way they combine the mean-field with the infinite LP and the finite approximation scheme. It handles the partial information setting nicely, which is a step up from methods that need the exact network. The experiments are a plus, as they use actual data and show practical performance. The weaker part is the lack of guarantees when moving from random graphs to real ones. Real networks often have more structure, so the mean-field error could be larger, but there's no analysis or even simple bounds provided on the objective gap or the activation error. The paper reports the achieved fractions but doesn't compare against exact optima on small instances or estimate the approximation quality. That makes the claims a bit harder to assess for non-random cases. This paper is for researchers in algorithmic game theory or network science who deal with influence or intervention problems and want something that works with statistical network models. It would be useful to someone looking for polynomial-time heuristics with some theoretical backing. It deserves a serious referee. The core construction is interesting and the problem is relevant, so review would help sort out the validation details. I would recommend sending it to peer review.

Referee Report

2 major / 2 minor

Summary. The paper studies the optimal intervention problem on the linear threshold model (LTM) where a planner designs minimal-cost threshold modifications to ensure a target fraction of agents activate after finite iterations. With only statistical network knowledge, it builds on the known local mean-field approximation for large random networks to recast the problem as an infinite-constraint linear program, shows how to approximate the latter by standard finite LPs, and validates the pipeline numerically on real-world networks against optimal seeding and state-of-the-art least-cost influence algorithms.

Significance. If the finite-LP solutions remain near-optimal under the mean-field approximation when transferred to empirical graphs, the work supplies a scalable, LP-based method for threshold-model interventions under partial information. This is valuable for applications in social networks and contagion control. The reformulation itself is a clean use of mean-field limits and LP duality, and the numerical comparisons to external benchmarks are a positive feature.

major comments (2)

[Numerical Experiments] Numerical Experiments section: the reported activation fractions on real-world networks are compared only to seeding baselines and prior heuristics; no quantitative bound (e.g., total-variation distance or objective gap) is given between the mean-field LP solution and the true cascade on the realized graph. Since the mean-field concentration is proved only for configuration-model random graphs, the absence of such a bound makes it impossible to certify that the finite-LP interventions are near-optimal on the empirical instances.
[Section 4] Section 4 (Approximation of the infinite LP): the discretization or sampling procedure that replaces the infinite constraint set is presented without a convergence rate or an a-priori error bound in terms of the number of sampled constraints or the accuracy of the estimated degree distribution. This gap is load-bearing because the central claim is that the finite LP yields near-optimal interventions.

minor comments (2)

[Model and LP reformulation] The notation distinguishing the planner’s per-agent cost function from the aggregate objective could be introduced earlier and used consistently in the LP formulation.
[Introduction] A short remark on how the statistical network knowledge (e.g., empirical degree distribution) is obtained in practice would clarify the setting for readers.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback on our manuscript. We address the two major comments point by point below, clarifying the scope of our theoretical results and the practical validation of the proposed method.

read point-by-point responses

Referee: [Numerical Experiments] Numerical Experiments section: the reported activation fractions on real-world networks are compared only to seeding baselines and prior heuristics; no quantitative bound (e.g., total-variation distance or objective gap) is given between the mean-field LP solution and the true cascade on the realized graph. Since the mean-field concentration is proved only for configuration-model random graphs, the absence of such a bound makes it impossible to certify that the finite-LP interventions are near-optimal on the empirical instances.

Authors: We thank the referee for this observation. Our concentration results for the mean-field approximation are indeed established only for large configuration-model random graphs, as stated in the paper. On empirical networks we do not claim theoretical near-optimality; instead, we report that the finite-LP interventions achieve activation fractions competitive with or superior to optimal seeding and state-of-the-art least-cost influence algorithms. This empirical evidence is intended to illustrate practical utility under statistical network knowledge rather than to certify optimality on arbitrary graphs. We agree that a quantitative bound for general networks would be valuable, but deriving one lies outside the present scope. In the revision we will add an explicit statement in the Numerical Experiments section acknowledging the limitation of the mean-field guarantee when applied to non-random graphs. revision: partial
Referee: [Section 4] Section 4 (Approximation of the infinite LP): the discretization or sampling procedure that replaces the infinite constraint set is presented without a convergence rate or an a-priori error bound in terms of the number of sampled constraints or the accuracy of the estimated degree distribution. This gap is load-bearing because the central claim is that the finite LP yields near-optimal interventions.

Authors: We appreciate the referee’s point on the approximation analysis. Section 4 presents a sampling-based procedure to obtain a finite LP from the infinite-constraint formulation; the procedure uses Monte Carlo sampling of the degree distribution and the constraint space. While we do not supply a formal a-priori convergence rate, the manuscript contains numerical illustrations showing that the objective value and the resulting interventions stabilize as the number of samples grows. In the revision we will add a short paragraph in Section 4 discussing this observed empirical convergence and noting that a rigorous rate analysis remains an open question for future work. This addition clarifies the practical reliability of the finite-LP solutions without changing the core claims. revision: partial

Circularity Check

0 steps flagged

No significant circularity; derivation relies on external mean-field result and standard LP techniques

full rationale

The central steps are: (1) invocation of a local mean-field approximation for LTM on large random networks, presented as previously known rather than derived here; (2) direct substitution of those equations into the intervention objective and constraints to obtain an infinite LP; (3) replacement of the infinite constraint set by a finite discretization or sampling scheme, which is a standard approximation method without parameter fitting to the target outputs. No equation reduces to another by definition or renaming, no fitted input is relabeled as a prediction, and no load-bearing uniqueness theorem or ansatz is imported via self-citation. The numerical experiments compare against external baselines on real networks, without the claimed solutions being forced by the inputs. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the validity of the local mean-field approximation for LTM on large random networks (cited as known) and the ability to approximate the infinite LP without losing the target adoption guarantee.

axioms (1)

domain assumption Local mean-field approximation holds for the LTM on large-scale random networks
Invoked to reformulate the intervention problem as an infinite LP; stated as known to hold true in the abstract.

pith-pipeline@v0.9.0 · 5472 in / 1286 out tokens · 33932 ms · 2026-05-13T01:31:04.865751+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages

[1]

and Hajiaghayi, MohammadTaghi and Mahini, Hamid and Malec, David L

Demaine, Erik D. and Hajiaghayi, MohammadTaghi and Mahini, Hamid and Malec, David L. and Raghavan, S. and Sawant, Anshul and Zadimoghadam, Morteza , booktitle =. How to influence people with partial incentives , year =

work page
[2]

, booktitle =

Goyal, Amit and Lu, Wei and Lakshmanan, Laks V.S. , booktitle =. 2011 , bdsk-url-1 =

work page 2011
[3]

and Vaccaro, Ugo , booktitle =

Cordasco, Gennaro and Gargano, Luisa and Rescigno, Adele A. and Vaccaro, Ugo , booktitle =. Optimizing Spread of Influence in Social Networks via Partial Incentives , year =

work page
[4]

Integrating Social Network Effects in Product Design and Diffusion , year =

G. Integrating Social Network Effects in Product Design and Diffusion , year =

work page
[5]

D. M. Topkins , date-added =. Equilibrium points in nonzero-sum n-person submodular games , url =. SIAM Journal on Control and Optimization , number =. 1979 , bdsk-url-1 =

work page 1979
[6]

Arditti and G

L. Arditti and G. Como and F. Fagnani , date-added =. IEEE Transactions on Control of Network Systems , title =

work page
[7]

Ravazzi and G

C. Ravazzi and G. Como and M. Garetto and E. Leonardi and A. Tarable , date-added =. Asynchronous Semianonymous Dynamics over Large-Scale Networks , volume =. SIAM Journal on Applied Dynamical Systems , number =

work page
[8]

M. O. Jackson , date-added =. Social and Economic Networks , year =

work page
[9]

van der Hofstad , date-added =

R. van der Hofstad , date-added =. Random Graphs and Complex Networks , year =

work page
[10]

Damonte and G

L. Damonte and G. Como and F. Fagnani , date-added =. Systemic risk and network intervention , volume =. IFAC PapersOnLine , number =

work page
[11]

Parise and A

F. Parise and A. Ozdaglar , date-added =. Graphon games: A statistical framework for network games and interventions , volume =. Econometrica , number =

work page
[12]

On the approximability of influence in social networks , volume =

Chen, Ning , journal =. On the approximability of influence in social networks , volume =

work page
[13]

Information and influence propagation in social networks , year =

Chen, Wei and Castillo, Carlos and Lakshmanan, Laks VS , publisher =. Information and influence propagation in social networks , year =

work page
[14]

A branch-and-cut approach for the weighted target set selection problem on social networks , volume =

Raghavan, Subramanian and Zhang, Rui , journal =. A branch-and-cut approach for the weighted target set selection problem on social networks , volume =

work page
[15]

Galeotti and S

A. Galeotti and S. Goyal and M.O. Jackson and F. Vega-Redondo and L. Yariv , date-added =. Network Games , volume =. The Review of Economic Studies , number =

work page
[16]

Optimal pricing in networks with externalities , volume =

Candogan, O and Bimpikis, K and Ozdaglar, A , date-added =. Optimal pricing in networks with externalities , volume =. Operations Research , pages =

work page
[17]

Ballester and A

C. Ballester and A. Calv. Who's Who in Networks. Wanted: The Key Player , volume =. Econometrica , number =

work page
[18]

Parise and A

F. Parise and A. Ozdaglar , date-added =. Analysis and Interventions in Large Network Games , volume =. Annual Review of Control, Robotics, and Autonomous Systems , pages =

work page
[19]

Kempe and J

D. Kempe and J. Kleinberg and \'. Maximizing the Spread of Influence Through a Social Network , year =. Proceedings of the Ninth ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining , date-added =

work page
[20]

Kempe and J

D. Kempe and J. Kleinberg and \'. Maximizing the Spread of Influence through a Social Network , volume =. Theory of Computing , number =. 2015 , bdsk-url-1 =

work page 2015
[21]

and Golub, B

Galeotti, A. and Golub, B. and Goyal, S. , date-added =. Targeting Interventions in Networks , volume =. Econometrica , number =. 2020 , bdsk-url-1 =

work page 2020
[22]

Arditti and G

L. Arditti and G. Como and F. Fagnani and M. Vanelli , date-added =. IEEE Transactions on Automatic Control , title =

work page
[23]

Como and S

G. Como and S. Durand and F. Fagnani , date-added =. Optimal Targeting in Supermodular Games , volume =. IEEE Transactions on Automatic Control , number =

work page
[24]

Messina and G

S. Messina and G. Como and S. Durand and F. Fagnani , date-added =. Optimal Intervention in Non-Binary Super-Modular Games , volume =. IEEE Control Systems Letters , pages =

work page
[25]

Threshold models of collective behavior , volume =

Granovetter, Mark , date-modified =. Threshold models of collective behavior , volume =. American

work page
[26]

Contagion , volume =

Morris, Stephen , date-modified =. Contagion , volume =. The Review of Economic Studies , number =

work page
[27]

Threshold models of cascades in large-scale networks , volume =

Rossi, Wilbert Samuel and Como, Giacomo and Fagnani, Fabio , date-modified =. Threshold models of cascades in large-scale networks , volume =. IEEE Transactions on Network Science and Engineering , number =

work page
[28]

Least-cost influence maximization on social networks , volume =

G. Least-cost influence maximization on social networks , volume =. INFORMS Journal on Computing , number =

work page
[29]

Scalable influence maximization in social networks under the linear threshold model , year =

Chen, Wei and Yuan, Yifei and Zhang, Li , booktitle =. Scalable influence maximization in social networks under the linear threshold model , year =

work page
[30]

Optimal Seeding in Large-Scale Super-Modular Network Games , volume =

Messina, Sebastiano and Cianfanelli, Leonardo and Como, Giacomo and Fagnani, Fabio , journal =. Optimal Seeding in Large-Scale Super-Modular Network Games , volume =

work page
[31]

Optimal interventions in opinion dynamics on large-scale, time-varying, random networks , year =

Cianfanelli, Leonardo and Como, Giacomo and Fagnani, Fabio and Ozdaglar, Asuman and Parise, Francesca , booktitle =. Optimal interventions in opinion dynamics on large-scale, time-varying, random networks , year =

work page
[32]

Networks , volume=

A branch-and-cut approach for the least cost influence problem on social networks , author=. Networks , volume=. 2020 , publisher=

work page 2020